Learning Shuffle Ideals with Membership Queries and Contrastive Examples
Paper shows many shuffle ideals are not efficiently learnable from membership or contrastive queries.
Stories per day · 30 days
2 stories, newest first · one card per story
Stories tagged #formal-languages
Beyond the Turing threshold: Productive grammars generate essentially undecidable languages
A theoretical paper designs formal grammars that emulate Post's productive sets, generating languages that are provably beyond Turing decidability.