PaperlayerView exact revision on arXiv

Source-linked AI summary

A 120-State Binary Turing Machine Equivalent to the Riemann Hypothesis

Joseph M. Shunia

arXiv:2609.30306v1cs.FL

TL;DR

The paper addresses how to construct a smaller explicit blank-tape machine encoding the Riemann hypothesis. It reformulates the arithmetic search and compiles it into a 120-state machine; that machine halts exactly when RH is false, with its state-count claim subject to independent verification.

  • Problem

    An explicit machine encoding RH had been constructed with 744 working states, and the paper seeks a substantially smaller construction in the same model.

    Source: §1 · p. 1

  • Method

    The authors reformulate the arithmetic search and compile it through a five-register program into a specialized binary one-tape machine.

    Source: §1 · p. 1, §12 · p. 17

  • Results

    The explicit 120-state machine halts if and only if RH is false.

    Source: §1 · p. 1, §1.1 · p. 2, §5.4 · p. 11

  • Takeaways & Limitations

    The construction gives a smaller explicit machine for the RH-equivalent counterexample search, rather than a proof of RH.

    Source: §1.1 · p. 2, §12 · p. 17

    The source-to-tape machinery is not formalized in a proof assistant, so independent audit of the compiler path, dispatcher specialization, and reachability certificate is appropriate.

    Source: §12 · p. 18

Abstract

from arXiv · show

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.

1 Introduction

The paper constructs an explicit 120-working-state machine in the binary blank-tape model that halts if and only if RH is false. It presents the construction as a candidate reduction of the 744-state benchmark and outlines the mathematical and tape-level reductions.

1 Introduction

  • The construction reaches 120 states primarily by reformulating the arithmetic search, then compiling and specializing its five-register program.The final reduction from 121 to 120 states uses a local reachability invariant.Source: §1 · p. 1

1.1 Machine model and main theorem

  • The 120-state machine halts if and only if RH is false; this equivalence is not a proof of RH.If RH is false, it eventually finds a concrete failure of the integer inequality; if RH is true, it runs forever.Source: §1.1 · p. 2

1.2 Comparison with the 744-state benchmark

  • 120 working states versus 744 reduces the count by 83.87%; the paper calls this a candidate record, subject to independent audit.The comparison uses the same binary blank-tape model and counting convention.Source: §1.2 · p. 2

1.3 Structure of the proof

  • The proof proceeds through arithmetic, analytic compression, register programming, and tape compression, with explicit certificates and a full transition table.The finite compilation is computer-assisted, not formalized in a proof assistant.Source: §1.3 · p. 2

2 A self-sieving arithmetic sequence

The arithmetic search uses a recurrence whose current value detects whether the next index is prime, avoiding a separate primality test. An offset representation then makes the initial value representable by zero.

2 A self-sieving arithmetic sequence

  • For each J ≥ 2, J is prime exactly when J does not divide A_(J−1), so the current product supplies the next primality test.This recurrence avoids a separate primality routine.Source: §2 · p. 3
  • The recurrence maintains A_J = J!P(J), adding the new factor in P(J) exactly when J is prime.The composite case follows because every composite J divides A_(J−1).Source: §2 · p. 3
  • Storing an offset coordinate makes zero represent the initial value A_1 = 1.The offset is chosen for the tape implementation.Source: §2 · p. 3

3 Offset digit counts and factorial centering

The section replaces explicit logarithmic evaluation with an integer digit-count loop and relates that count to the analytic scale of the search. Its offset count differs from ordinary digit length by at most one.

3 Offset digit counts and factorial centering

  • The offset count β_b(B) is the number of repeated-division iterations performed while B > 0, with β_b(0) = 0.It is deliberately distinct from ordinary digit length ℓ_b(B).Source: §3 · pp. 3–4
  • For B > 0, the offset count is either the ordinary base-b digit length or one less.This bound follows from the terminating-iteration bounds in the section.Source: §3 · p. 4
  • For n ≥ 3, A_n is not a power of n, so subtracting one does not cross a base-n digit boundary.The section uses this fact in relating the integer statistic to the Chebyshev error.Source: §3 · p. 4

4 An RH-equivalent scaling criterion

The criterion replaces the RH-scale threshold with an integer deficit bound that can be tested by a scaling clock. Its RH equivalence follows from a conditional forward estimate and a one-sided converse.

4 An RH-equivalent scaling criterion

  • The section’s RH-equivalent threshold is tested using division by two and four rather than explicit exponential and logarithmic evaluation.Quartering one counter sets the power-of-four scale while parallel halving of the deficit supplies the corresponding power-of-two scale.Source: §4 · p. 4, §4.1 · p. 5

4.1 The scaling clock

  • The quartering clock runs exactly ⌊log4(3n)⌋ iterations and halves a second counter once per iteration.The final counter is ⌊f0/2^qn⌋.Source: §4.1 · p. 5

4.2 Forward implication under RH

  • Under RH, the integer criterion holds for every n ≥2657, using Schoenfeld’s explicit estimate followed by integer bounds.The estimate is applied only for x ≥2657, and the remaining argument is integer bookkeeping.Source: §4.2 · p. 5

4.3 Small arguments without a prime table

  • The integer criterion holds for every 2 ≤ n ≤2656 without assuming RH or using a table of prime values.The same factorial term supplies a crude bound for this finite range, avoiding hard-coded cases or a prime table.Source: §4.3 · p. 6

4.4 The one-sided converse

  • A one-sided lower bound on the Chebyshev error for all sufficiently large x implies RH, completing the converse for the integer criterion.The proof uses positivity of a Mellin-transform integral to exclude zeta zeros to the right of the critical line; the functional equation excludes zeros to the left.Source: §4.4 · pp. 6–7

5 Five-register implementation of the criterion

A five-register counter program implements the integer criterion through reusable arithmetic macros and staged product, deficit, and scaling operations. Its source halts exactly when the criterion fails, and continuation sharing reduces the compiled state count.

5 Five-register implementation of the criterion

  • The implementation uses five registers, (m, j, x, f, v), with counters reused across phases when their lifetimes do not overlap.At a main-stage call boundary, the invariant is (m, j, x, f, v) = (M, 0, 0, 0, 0).Source: §5 · p. 8

5.1 Primitive counter macros

  • The primitive counter macros reduce arithmetic to increment and conditional decrement, with division and transform operations providing compatible quotient/reconstruction behavior.The split division output can be passed to transform() to reconstruct the original value.Source: §5.1 · pp. 8–9

5.2 One exact product step

  • Each product step uses division to test divisibility and retain quotient/remainder information, then updates the represented product by J for composites or J² for primes.The resulting invariant is j = J −1 and x = A_J −1.Source: §5.2 · p. 9

5.3 Stage construction and the offset digit deficit

  • The product phase performs exactly n −1 steps to reach A_n, after which the digit phase computes the offset deficit.A split-divisor deficit seed initializes the digit phase while preserving the represented divisor n.Source: §5.3 · pp. 9–10

5.4 Scaling and comparison

  • The source tests endpoints n = 2, 3, 4, … in order and halts exactly when the integer criterion fails, hence if and only if RH is false.Passing comparisons advance the next endpoint by one.Source: §5.4 · p. 11

5.5 Sharing the scaling-loop continuation

  • Regrouping the scaling-loop continuation lets the compiler share a fragment already used by transform(), reducing the decision DAG from 64 states to 63.The revised and original loops preserve the same primitive operation sequence and termination behavior; the resulting machine has 120 states after local reachability projection.Source: §5.5 · p. 11

6 Tape implementation and dispatcher specialization

The section establishes how the register backend simulates the source program, then specializes dispatch and verifies the resulting 121-state table. Its proof combines a finite blank-tape bootstrap with uniform register and control semantics.

6 Tape implementation and dispatcher specialization

  • The section separates source semantics, register-level execution, and tape-level dispatch, proving both generic-backend claims before specializing the dispatcher.The two claims are that the backend implements the source operations and the specialized dispatcher matches the generic one on post-bootstrap normal forms.Source: §6 · pp. 11–12

6.1 Normal form and bootstrap

  • Normal form stores the control word, auxiliary marker, and five unary registers; 89,775,610 transitions bootstrap all five logical registers to zero.A literal replay checker verifies the transition count and complete finite tape support.Source: §6.1 · p. 12

6.2 Primitive register operations

  • Increment changes only the selected register; conditional decrement branches on zero and otherwise decrements it, with each operation restoring normal form.The implementation shifts the selected unary block’s terminating delimiter and leaves unselected logical registers unchanged.Source: §6.2 · pp. 12–13

6.3 Control-DAG semantics

  • The binary control DAG preserves sequential, conditional, and loop semantics, while backend simulation reaches each next source boundary in finitely many tape steps.After main returns, the root protocol invokes it again without changing the logical register file.Source: §6.3 · pp. 13–14

6.4 Program-specific dispatcher

  • A four-zero scanner replaces generic dispatch; certificates verify that no live control word or return suffix contains four consecutive zeros, preserving each source boundary.The bootstrap is verified separately on the specialized table.Source: §6.4 · p. 14

6.5 All-tapes minimization to 121 states

  • The all-tapes strong-bisimulation quotient has 121 states and simulates the five-register source on blank tape, halting exactly on the first failure of the inequality.The quotient preserves every tape trajectory, not only the blank-tape run.Source: §6.5 · p. 15

7 Reachability-restricted reduction from 121 to 120 states

A five-cell local-window invariant certifies which state/read pairs occur in the 121-state machine’s blank-tape run. That reachability information permits a projection to 120 states with identical blank-tape halting behavior.

7 Reachability-restricted reduction from 121 to 120 states

  • The 121-to-120 reduction merges states 32 and 97 despite their differing read-zero actions, because the disagreeing pair is unreachable from the blank initial configuration.The projection preserves the complete blank-tape trajectory.Source: §7 · p. 15, §7.1 · p. 15, §7.2 · p. 16

7.1 Five-cell window invariant

  • 1,621 admitted state-window pairs and 3,218 successor obligations certify a five-cell invariant that allows either value for each newly exposed edge cell.The invariant contains every state/window pair occurring at any finite time in the actual blank-tape run.Source: §7.1 · p. 15

7.2 Projection theorem

  • The certificate excludes (97, 0), the pair responsible for a differing read-zero action; merging states 32 and 97 therefore preserves identical blank-tape halting behavior.The projection verifier checks its equations on all 240 admitted state/read pairs.Source: §7.1 · p. 15, §7.2 · p. 16

8 Proof of the main theorem

The proof links the RH-equivalent universal inequality to the source program’s halt condition, then carries that behavior through the revised loop and tape-machine reductions. It concludes that M120 halts exactly when RH is false.

8 Proof of the main theorem

  • The Riemann hypothesis holds exactly when the integer inequality (16) holds for every n ≥ 2.Source: §8 · p. 16
  • The five-register source halts exactly on the first failure of inequality (16), and revised scaling-loop grouping preserves those source semantics.Source: §8 · p. 16
  • The 121-state table and its 120-state projection preserve the source’s blank-tape halting behavior, so M120 halts exactly when RH is false.Source: §8 · p. 16

9 Computational verification

The verification checks finite construction artifacts with literal runners, certificates, and integer tests. The infinite-run conclusion instead follows from the analytic criterion and uniform semantic proofs.

9 Computational verification

  • 122 reachable named states yield a 121-state, 242-transition ordinary-bisimulation quotient before the final reduction.Source: §9 · p. 16
  • Certificates check 84 control-boundary pairs, 125 outcome edges, all 121 dispatcher paths, and the five-cell invariant and projection obligations.The invariant has 1,621 admitted pairs and 3,218 closure obligations; projection is verified on 240 admitted state/read pairs.Source: §9 · p. 16
  • The final table has 120 working states and 240 transitions, and its 2,140-bit reversible transition integer decodes to every transition.Source: §9 · p. 16
  • A literal tape runner checks the bootstrap and completed endpoints 2, 3, and 4 at their reported transition counts and expected live-register tuples.Source: §9 · p. 16
  • Host-integer checks cover stages through n = 256 and scaling cases using proved counter contracts; these checks are distinct from literal tape executions.The reported coverage includes 32,640 intermediate product identities and 100,000 scaling-clock inputs.Source: §9 · p. 16
  • Finite computations verify implementation claims; the infinite-run statement follows from the analytic criterion, uniform register and control semantics, and inductive state projection.Source: §9 · p. 16

10 Separate NQL implementation

A conventional NQL implementation provides a separate execution path for the same mathematical search, while the specialized 120-state construction uses additional program-specific reductions. The NQL check supports the arithmetic search but does not establish step-for-step equivalence between the two machines.

10 Separate NQL implementation

  • The independent NQL implementation computes the same quantities and simultaneous-scaling test as the specialized search, using an unmodified compiler.Its compiler produces 1,102 raw reachable states, 601 after compression, and 1,202 transitions; strong bisimulation does not further reduce the 601-state count.Source: §10 · p. 17
  • 601 states (plain NQL) versus 120 states (specialized construction) illustrates the difference between conventional compilation and program-specific state reductions.The NQL implementation uses the same stopping criterion, not a different search.Source: §10 · p. 17
  • Against a sieve-based oracle, the NQL source passed all 255 stages from n = 2 through 256 and 32,640 intermediate product-identity checks.Separate compiled helper programs also executed successfully for n = 2, 3, 4, and 5, including the exceptional composite and following prime update.Source: §10 · p. 17
  • The separate implementation checks the mathematical search, not step-for-step equivalence with the 120-state table, whose specialized path is justified by invariants and certificates.The two verification routes are complementary.Source: §10 · p. 17

11 Reproducibility

The paper provides source and finite artifacts for reproducing and inspecting its principal checks, along with commands for running them.

11 Reproducibility

  • The appendices and accompanying directory provide the complete source needed to regenerate and verify the principal finite artifacts.The text lists the principal shell commands for reproduction and checking.Source: §11 · p. 17
  • The listed commands run the reproduction tests, certificate verifier, bootstrap checker, and stage checker against the named transition table.The commands include compiling the C++ checkers and executing them.Source: §11 · p. 17
  • The exact transition table is independently inspectable, and the directory includes the generator, tables, certificates, and literal tape checkers.The separate NQL results concern the unchanged arithmetic criterion and come from preceding verification work.Source: §11 · p. 17

12 Discussion and limitations

The construction combines an RH-equivalent arithmetic reformulation with compact register and tape-level implementations to obtain an explicit 120-state machine. The paper presents this as a candidate state-count record, while noting that the theorem does not prove RH and that independent audit remains appropriate.

12 Discussion and limitations

  • The construction combines factorial growth and prime information, self-sieving, offset digit counting, repeated halving, and program-specific tape reductions to reach 120 states.A dispatcher and reachability-restricted projection reduce tape-level control overhead.Source: §12 · p. 17
  • 601 states in the conventional NQL implementation versus 120 in the specialized construction reflects representation and implementation choices, not a different stopping criterion.The NQL version executes the same mathematical search without the specialized state reductions.Source: §12 · p. 17
  • The equivalence theorem does not prove RH, and the paper proves no lower bound showing that 120 states is near-optimal.The 120-state construction is a candidate new record, subject to independent verification.Source: §12 · p. 18
  • The finite compilation layer is explicit but not proof-assistant formalized, so the compiler path, dispatcher specialization, and reachability certificate warrant independent audit.The analytic directions use Schoenfeld’s RH-conditional estimate and, for the converse, analytic continuation and the functional equation.Source: §12 · p. 18

A Final high-level source

This section presents the implementation artifacts and source tools for generating and minimizing the finite construction, including a final source variant, the dispatcher and register-machine backend, and certificate and bisimulation checks. It describes the verification scope and assumptions, along with finite checks of control-transducer equivalence, bootstrap computation, completed-stage register values, and reproducible construction of the 120-state machine, including rejection of deliberately corrupted data.

A Final high-level source

  • The appendices reproduce the baseline five-register program and two subclasses verbatim for line-by-line comparison with the preceding proofs.The subclasses modify deficit seeding and then share the scaling-loop continuation.Source: A Final high-level source · p. 19

A.1 Baseline source

  • The baseline source specifies blank-tape execution without uncounted arithmetic, tape input, or an infinite background; each passing stage tests n=M+2 and returns with m=n-1.At main entry m=M and all other registers are zero; the inherited root restarts main.Source: §A.1 · p. 19

A.2 Split-divisor source specialization

  • The split-divisor specialization preserves the mathematical criterion and endpoint order, retaining divisor j+v+1 in split form for the next division.Its inherited source/backend and dispatcher are in baseline_source.py and vendor/.Source: §A.2 · p. 20

A.3 Scaling-loop specialization

  • The final 120-state subclass changes only the scaling loop’s binary grouping, sharing its increment/continue tail to remove one decision state while preserving counter operations and the tested RH criterion.The complete generated control graph has one fewer decision state than the preceding split-divisor subclass.Source: §A.3 · p. 21

B Program-specific dispatcher

  • The program-specific dispatcher replaces the read-only scan under the compiled source’s live control-word language, but is not an all-tapes bisimulation.Its certificate describes a language- and invariant-based scanner replacement, not an all-tapes state merge.Source: B Program-specific dispatcher · p. 21

C Register-machine backend

  • The selected source uses a complete operational builder that adapts Andrew J. Wade’s MIT-0 TMBuilder, retaining its operational framework and intermediate representation.The builder replaces the naming/debugger layer.Source: C Register-machine backend · p. 22
  • The backend transcribes the operational framework and generates reachable machine states, dispatch transitions, and decision-DAG transitions.It counts framework and decision-DAG states separately and reports their total.Source: C Register-machine backend · pp. 23–24

D.1 Strong-bisimulation minimizer

  • The minimizer uses strong bisimulation to preserve every tape trajectory, without deleting transitions or relying on heuristic halting assumptions or finite-run equivalence.It iteratively groups states by their transition actions and successor groups.Source: §D.1 · p. 24

D.2 Canonical table utilities

  • The canonical-table utilities validate transitions, assign state labels from the start state, and serialize tables with a SHA-256 hash.They also check that a binary table has two defined transitions per state.Source: §D.2 · pp. 24–25

E.1 Window invariant generator and verifier

  • The window certificate represents reachable state-window pairs as an inductive overapproximation, allowing either symbol in each newly exposed cell.Its standalone verifier checks closure obligations and can verify that a projected machine matches the original on overapproximated reachable reads.Source: §E.1 · pp. 25–26

E.2 Compatible merge search and quotient

  • The compatible-merge search uses a proven reachable-read set, but its greedy state-selection heuristic is checked separately for correctness.Unreachable reads are completed arbitrarily and are never used on actual runs.Source: §E.2 · p. 26

E.3 Standalone certificate checker

  • The standalone checker validates delivered tables and certificates without importing the compiler and rejects negative controls that alter the initial window, reachable windows, transitions, or projection.Its certificate is finite and inductive, allows both symbols in unknown neighboring cells, and assumes neither RH nor nonhalting.Source: §E.3 · p. 27

F Control-transducer bisimulation

  • The control-transducer bisimulation checks generated dispatch, decision-DAG, and jump transitions literally, using register contracts and exploring every possible conditional-decrement outcome.It assumes no concrete counter range; increment always succeeds.Source: F Control-transducer bisimulation · p. 27
  • The control-transducer certificate pairs old and new operation-boundary states and checks every decrement outcome, while treating increments as always successful.Its checker verifies corresponding successors and records the number of operation-boundary pairs, outcome edges, and halting pairs.Source: F Control-transducer bisimulation · p. 28

G Literal bootstrap replay checker

  • 89,775,610 steps reach state N54 at head position -3818, with the asserted tape contents, and the literal bootstrap checker verifies the certificate.The checker reads the generated named transition table directly, without importing the source compiler or an arithmetic routine.Source: G Literal bootstrap replay checker · p. 28

G.1 Literal completed-stage checker

  • The completed-stage checker detects returns from the main source routine and validates live-register tuples at endpoints 2, 3, and 4.For each endpoint, its assertions require the tuple (m, 0, 0, 0, 0).Source: §G.1 · p. 29

H.1 Reproduction driver

  • The reproduction driver builds a 120-state machine from a 121-state predecessor, reproduces the original 121-state machine exactly, and rejects two deliberate corruptions.It checks projection and control certificates and records the final machine’s SHA-256 hash.Source: §H.1 · pp. 29–30

H.2 Exact host-integer checks

H.2 reports exact host-integer and isolated scanner checks while distinguishing them from binary-tape execution and formal verification. H.3 gives reversible transition-table coding, and Section I supplies the exact 120-state table.

H.2 Exact host-integer checks

  • The checks cover exact host-integer stages and isolated scanner runs, but full arithmetic stages use kernel contracts rather than binary-tape execution or AST formal verification.The report also identifies the inherited tape-layout invariant as an additional semantic premise.Source: §H.2 · p. 31

H.3 Reversible Gödel coding

  • The reversible Gödel coding encodes and decodes a complete binary transition table as an integer representation.The encoding returns n, G, and (1<<n)*(2*G+1).Source: §H.3 · pp. 31–32

I Exact 120-state transition table

  • Section I provides the exact 120-state transition table in machines/RH_120.tm, using state-read-write-direction-target syntax and an uncounted halting target H.The stated syntax and halting-target convention are specified in the passage.Source: I Exact 120-state transition table · p. 32
Loading 2609.30306v1…