Summary
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.
What this means in practice
- •For programming language designers: Recognize limits on what formal grammar-based language features can guarantee decidable parsing and analysis.
- •For compiler builders: Avoid creating grammar rules that lead to undecidable language recognition problems, guiding reliable compiler design.
A theory result. No direct application yet.
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.