A 120-State Binary Turing Machine Equivalent to the Riemann Hypothesis
In the authors' words
We construct an explicit deterministic one-tape, two-symbol Turing machine with 120 working states whose blank-tape computation halts if and only if the Riemann hypothesis is false. The machine uses the same binary blank-tape model and state-counting convention as the widely cited 744-state Matiyasevich-O'Rear-Aaronson construction. The reduction from 744 to 120 working states removes 624 states, or 83.87%. Subject to independent end-to-end verification, our machine is a new state-count record for the Riemann hypothesis.
Main resultLimitation the authors admit
Appeared: Monday, September 28. arXiv. Preprint, not yet peer-reviewed.