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.
The paper elaborates on Emil Post's productive sets, which are not even semi-computable, and builds formal grammars that emulate their construction over natural numbers. The resulting languages are shown to be essentially undecidable, placing them beyond Turing decidability. This is pure computability and formal language theory with limited direct security relevance.
- Constructs grammars emulating productive (non-semi-computable) sets
- Resulting languages are essentially undecidable
- Pure computability theory; limited direct security impact
Full article64 words · extracted from arxiv.org · click to collapse
Emil Post's productive sets are not even semi-computable, let alone computable, being thus essentially incomputable. Accordingly, formal languages whose set of words is a (completely) productive set are essentially undecidable. In this article, I elaborate on Post productivity from the viewpoint of formal language theory: I design formal grammars that emulate the construction of productive sets of natural numbers and are thus beyond Turing-decidability.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.11385