Beyond the Turing threshold: Productive grammars generate essentially undecidable languages
cs.FL, cs.CR
Submitted: 2026-09-10
Updated: 2026-09-10
Comments: Key words: Post productivity; Completely productive set; Turing-decidability; Essential undecidability; Productive grammar; Productive grammar. This work will be developed from the viewpoint of theoretical computer virology
License: http://creativecommons.org/licenses/by-sa/4.0/
The gist: Emil Post's productive sets are not even semi-computable, let alone computable, being thus essentially incomputable.
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.