Beyond the Turing threshold: Productive grammars generate essentially undecidable languages

2026-10-23来源 arXiv cs.CREnglish
arXiv:2609.11385v2 Announce Type: replace-cross Abstract: 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.

原文：https://www.a8q9.cn/en/article/beyond-the-turing-threshold-productive-grammars-generate-essentially-undecidable-bbb5d6.html

相关文章