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
From the original article
1 min read at arxiv.orgEmil 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.
By Luis M. Augusto · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.