Diagonalization and Undecidability in Semi-Thue Systems
cs.CC
Submitted: 2026-10-29
Updated: 2026-10-29
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
The gist: We revisit classical diagonalization argument in the setting of semi-Thue systems, viewing computation as nondeterministic rewriting rather than sequential machine execution.
Abstract
We revisit classical diagonalization argument in the setting of semi-Thue systems, viewing computation as nondeterministic rewriting rather than sequential machine execution. Semi-Thue systems naturally generate derivation trees, making existential acceptance, reachability, and infinite derivations fundamental computational notions. We formulate acceptance and decision directly in terms of derivation trees and study the associated assertion, word, and infiniteness problems. We prove that the complements of the assertion and word problems are not recursively enumerable by direct Post-style diagonal arguments. For the infiniteness problem, we give a constructive diagonalization based on a fixed universal semi-Thue system. Unlike the classical approach, the diagonal construction is carried out entirely within the rewriting formalism: the universal system remains an ordinary nondeterministic semi-Thue system while simulating encoded semi-Thue computations, including self-reference. These results show that undecidability in semi-Thue systems arises naturally from universality and self-reference in nondeterministic rewriting, rather than from machine states or control mechanisms. This perspective clarifies the relationship between rewriting systems, recursive enumerability, and classical diagonal arguments originating in the work of Post and Turing.
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?