Source-linked AI summary
Beyond the Turing threshold: Productive grammars generate essentially undecidable languages
Luis M. Augusto
TL;DR
The paper addresses how formal language theory can represent productive sets that exceed Turing recognition. It designs productive grammars that emulate their construction and concludes constructively that uncountably many undecidable languages exist.
Problem
Productive sets are not even semi-computable, raising the question of what formal grammars can generate languages beyond Turing recognition.
Method
The paper designs formal grammars whose languages emulate the construction of productive sets of natural numbers.
Results
Constructively, the class of productive languages has cardinality at least |ω|, and there are uncountably infinitely many undecidable languages.
Takeaways & Limitations
Productive grammars provide a formal-language framework for studying languages that are not Turing-recognizable, let alone Turing-decidable.
Takeaways & Limitations
It is not known whether there is a productive set that is not completely productive, and one discussed grammar would generate the empty language under Chomsky grammar restrictions.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper situates productive languages beyond the Chomsky hierarchy and asks what formal grammars can generate languages beyond Turing recognition. It develops this perspective from Post’s essentially incomputable productive sets.
- The extended Chomsky hierarchy distinguishes Turing-decidable languages from those that are only Turing-recognizable, while leaving languages beyond Turing-machine powers outside its ordinary classifications.The paper frames this boundary through the Church-Turing Thesis.
- Post’s productive sets are not even semi-computable, making them essentially incomputable objects for studying set construction.The paper treats productive sets per se rather than only as complements of creative sets.
- Productive word sets are not Turing-recognizable, so grammars generating them lie outside the Chomsky hierarchy and its extensions.The paper uses such grammars to study essentially undecidable languages.
- The paper asks what formal systems and grammar classes can generate productive languages that behave like productive sets of natural numbers.Its stated aim is to reduce ignorance about languages beyond Turing recognition or decision.
- The polynomial example illustrates semi-computation: testing integer roots eventually terminates for membership but has no termination guarantee otherwise.Values are evaluated successively at 0, 1, -1, 2, -2, and so on.
2 Post's Productive Sets
The section develops Post's framework for productive sets, distinguishing computability from semi-computability and establishing that productive sets are essentially incomputable. It then derives structural results about their infinite semi-computable subsets, productive centers, and induced productive sets.
- Recursiveness and computability: A set is computable when both it and its complement are effectively decidable, whereas semi-computability requires an effective method only for membership.The section uses characteristic and semi-characteristic functions to distinguish the two notions.
- Recursiveness and computability: Rice's theorem frames nontrivial properties of partial recursive functions as undecidable through the scarcity of computable index sets.Only the empty set and the full set are identified as computable index sets.
- Productive Sets: Every productive set contains an infinite semi-computable subset, so essential incomputability does not preclude effectively enumerable structure.The subset is constructed from generated elements and remains a proper subset of the productive set.
- Productive sets are incomputable and not semi-computable, making them essentially incomputable.The section states this directly through the characterization of essential incomputability and the corollary for productive sets.
- Productive Sets: Productive centers can be nested with countably infinite differences, and every productive set has exactly countably many productive centers and productive functions.The section also states that productive centers inherit productivity and that every productive set induces exactly k productive sets.
3 Productive Grammars and Essentially Undecidable Languages
This section introduces formal languages, word structure, prefix closure, and the hierarchy connecting grammar classes with Turing-decidability. It then shows that productive languages exceed the Chomsky hierarchy and can be essentially undecidable.
- 3.1.2 Turing-decidability for languages: A language is Turing-decidable when a machine enumerates its elements in canonical order, equivalently when it is prefix-closed under the stated characterization.
- 3.1.2 Turing-decidability for languages: Type-0 grammars can generate semi-decidable languages whose parsers accept members but may not halt on nonmembers.The parser enters infinite node generation when it cannot construct a parse tree for a word outside the language.
- 3.2 Productive grammars and productive languages: Productive-language construction yields languages that are not merely undecidable but essentially undecidable, with no Turing machine deciding membership extensionally.
- 3 Productive Grammars and Essentially Undecidable Languages: Productive languages are outside the Chomsky hierarchy.
- 3.2 Productive grammars and productive languages: For the constructed language, an infinite semi-computable set W_n is not equal to any subset W_n of the language, so the language is not prefix-closed and is undecidable.
- 3.2 Productive grammars and productive languages: The example grammar generates a semi-computable productive language, while no machine can enumerate it in canonical order because proper prefixes cannot be effectively distinguished from excluded terminal words.
4 Conclusions
The paper situates productive languages within the broader landscape of undecidable languages and connects their unrecognizability to the countability of Turing machines. It concludes that uncountably many undecidable languages exist, with productive languages providing a constructive route to this result.
- The conclusion builds on the countability of recursive functions and Turing machines, contrasted with the uncountability of the power set of the natural numbers.The paper explicitly converts the countability result for recursive functions into a countability result for Turing machines.
- Uncountably many languages are undecidable, as the power set of the natural numbers is uncountable while Turing machines are only countably infinite.The paper frames productive languages as a constructive demonstration of this broader computability-theoretic fact.
- The class of productive languages is itself sufficiently large to support the conclusion that uncountably many undecidable languages exist.The paper states constructively that the class of productive languages has cardinality at least that of the natural-number power set.