Papers for

compiler builders

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Formal grammars generate languages beyond Turing machine limits

Beyond the Turing threshold: Productive grammars generate essentially undecidable languages

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.

Thu 10 SeptFormal Languages and Automata TheoryCryptography and Security
The gist
Some problems or languages cannot be decided or solved by traditional computers called Turing machines. The authors focused on special sets of numbers known as productive sets, which are even more complex and undecidable than usual. They showed how to build formal grammars—rules for generating words—that mimic these complex sets. This means the languages created by these grammars cannot be decided by any computer, going beyond standard computability limits.
Open → 2609.11385v1