This library contains formally verified 2-symbol Turing machines and Lean 4 semantics proofs for Goldbach's Conjecture, ZF Set Theory Consistency, and the Riemann Hypothesis, developed by Maxence Faldor and Moritz Firsching using Gemini Argon. The erdos_ternary_15 and erdos_ternary_14 formalizations (Erdős's ternary conjecture) and the brocard_28 machine and proofs (Brocard's problem) are by Daniel Veljjanoski, with Claude (Anthropic) as assistant.
| Conjecture | Machine | States | Source / Provenance | Proved Halting Condition (Halts M ↔ ...) |
Lean 4 Proofs |
|---|---|---|---|---|---|
| Goldbach's Conjecture | goldbach_21 |
21 |
Reduced from goldbach_25 (25 states, Yao / Leng 2024) |
¬ GoldbachConjecture |
Goldbach21.lean, Semantics/Goldbach.lean |
| ZF Consistency | zf_380 |
380 |
Reduced from zf_393 (393 states, Wade Aug 2026) |
ZFInconsistent (¬ Halts candidate proved) |
Zf380.lean, Semantics/Zf393.lean |
| ZF Consistency | zf_393 |
393 |
Andrew Wade (turing_machine_explorer 9c5c2e82, Aug 2026) |
ZFInconsistent (¬ Halts zf393 proved) |
Zf393.lean, Semantics/Zf393.lean |
| ZF Consistency | zf_432 |
432 |
Andrew Wade (turing_machine_explorer 33b30300, Aug 2025) |
WadeZFInconsistent |
Semantics/Zf.lean |
| Riemann Hypothesis | riemann_95 |
95 |
Retained stage counter and proved operand-bank permutation | ¬ RiemannHypothesis |
Riemann95.lean, Semantics/Riemann95.lean |
| Riemann Hypothesis | riemann_104 |
104 |
Reduced from riemann_120 (120 states, Shunia Sept 2026) |
¬ RiemannHypothesis |
Riemann104.lean, Semantics/Riemann120.lean |
| Riemann Hypothesis | riemann_120 |
120 |
Joseph M. Shunia (arXiv:2609.30306, Sept 2026) |
¬ RiemannHypothesis |
Riemann120.lean, Semantics/Riemann120.lean |
| Riemann Hypothesis | riemann_744 |
744 |
Matiyasevich, O'Rear & Aaronson (riemann_744_sorear.tm, 2016) |
¬ RiemannHypothesis |
Semantics/Riemann.lean |
| Erdős's ternary conjecture | erdos_ternary_14 |
14 |
Tristan Stérin (bbchallenge Discord, Oct 2026; Cryptids wiki) | ¬ ErdosTernaryConjecture |
ErdosTernary14.lean, Semantics/ErdosTernary14.lean |
| Brocard's problem | brocard_28 |
28 |
Daniel Veljjanoski (Nov 2026); earlier: Charlie Reams's 61-state machine (calr3/tinycryptids, Nov 2026) and a 43-state table without a machine-checked proof (arXiv:2605.20215) |
¬ BrocardConjecture |
Brocard28.lean, Semantics/Brocard28.lean |
| Erdős's ternary conjecture | erdos_ternary_15 |
15 |
Tristan Stérin & Damien Woods (arXiv:2107.12475, 2021) |
¬ ErdosTernaryConjecture |
ErdosTernary15.lean, Semantics/ErdosTernary15.lean |
See RELATED_WORK.md for the historical progression across each domain.
All proofs in Cryptids/ are checked by the Lean 4 kernel (v4.35.0-rc4) without sorry:
-
State reductions: Each reduced machine (
goldbach_21,zf_380,riemann_104,riemann_95,erdos_ternary_14) has fewer states than its reference machine (goldbach_25,zf_393,riemann_120,riemann_104,erdos_ternary_15) and halts from the blank tape if and only if the reference machine halts (Goldbach21.lean,Zf380.lean,Riemann104.lean,Riemann95.lean,ErdosTernary14.lean). The direct simulation reductions (goldbach_21,zf_380,riemann_104), theerdos_ternary_14reduction, and all fivecandidate_fewer_statestheorems are completely constructive (["propext", "Quot.sound"], zeroClassical.choice), audited viacomparator/constructive.json,comparator/goldbach_21.json,comparator/zf_380.json, andcomparator/riemann_104.json, whileriemann_95routes through the arithmetic stage predicateShuniaCounterexample(Nat.Prime, audited viacomparator/riemann_95.json). -
End-to-end mathematical semantics (
Cryptids/Semantics/):-
ZF Consistency (
zf_380,zf_393, andzf_432): Bothzf_380and Wade's 393-state machinezf_393(incorporating upstream fix10fcf152b3) halt if and only if O'Rear'szf2.nqlHilbert system proves$v_0 \in v_0$ (Halts candidate ↔ ZFInconsistent,Halts zf393 ↔ ZFInconsistent), whilezf_432halts if and only if the 20-clause deductive system enumerated byzf_432_wade.tmderives$v_0 \in v_0$ (WadeZFInconsistent). All three proof-search equivalences are proved constructively in Lean using only["propext", "Quot.sound"](noClassical.choice, no Excluded Middle, and no Markov's Principle) and audited viacomparator/constructive.json, blocking classicalCon(ZF)shortcuts viaZf/Soundness.leanorClassical.em(object-levelPAinternalization forzf_393andzf_380is proved separately below viaPAProvable, whilezf_432internalization and establishing full two-wayZF-independence remain separate; seeSemantics/README.md). Separately,Zf/Soundness.leanuses classicalZFSet.{0}(Classical.choice) to establishnot_zfInconsistentand deduce unconditional non-halting (not_halts_zf393,not_halts_candidate) inside Lean's stronger meta-theory. -
First-Order Peano Arithmetic (
PAProvable,Semantics/PA.lean): Deeply embeds first-order Peano Arithmetic (PATerm,PAFormula,PAProvable) and$\Sigma_1^0$ encodingspaHalts MandpaZFInconsistentinPropositions.leanandChallenge.lean, proving constructive consistency (not_paProvable_false) and constructive standard-model adequacy (paHalts_holds_iff_halts,paZFInconsistent_holds_iff_zfInconsistent; all three audited withoutClassical.choiceincomparator/constructive.json), along with classical standard-model soundness (paProvable_sound_nat) and full object-levelPAproofs thatzf_380andzf_393halt iffZFis inconsistent (paProvable_halts_zf380_iff_zf393,paProvable_halts_zf393_iff_zfInconsistent,paProvable_halts_zf380_iff_zfInconsistent, audited incomparator/pa_semantics.jsonandcomparator/all.json; these threePAProvabletheorems useClassical.choicebecause they reason in arbitraryPAModels and reflect back toPAProvablevia internal Gödel–Henkin completenesspaProvable_iff_holdsIn_all_models). -
Goldbach (
goldbach_21andgoldbach_25): Bothgoldbach_21andgoldbach_25constructively satisfyHalts M ↔ ∃ w, ¬ HasGoldbachPair (2 * w + 4)withoutClassical.choice(Goldbach21.lean), and withClassical.choice(for Markov's Principle on¬ ∀ n, ...) satisfyHalts candidate ↔ ¬ GoldbachConjecture(Semantics/Goldbach.lean). -
Erdős's ternary conjecture (
erdos_ternary_15anderdos_ternary_14): Stérin and Woods's 15-state machine constructively satisfiesHalts erdosTernary15 ↔ ∃ n, 8 < n ∧ 2 ∉ pw n, wherepw nis the base-3 digit list of2 ^ ncomputed by repeated doubling (ErdosTernary15.lean), and withClassical.choice(Mathlib'sNat.digits, and Markov's Principle on¬ ∀ n, ...) satisfiesHalts erdosTernary15 ↔ ¬ ErdosTernaryConjecture(Semantics/ErdosTernary15.lean). Stérin's 14-state machineerdos_ternary_14constructively satisfiesHalts erdosTernary14 ↔ ∃ n, 8 < n ∧ 2 ∉ pw nand henceHalts candidate ↔ Halts referenceagainsterdos_ternary_15(ErdosTernary14.lean), andHalts candidate ↔ ¬ ErdosTernaryConjecture(Semantics/ErdosTernary14.lean). -
Brocard's problem (
brocard_28): The machine keepsn! / 8in unary and tests it for triangularity by subtracting1, 2, 3, …; it constructively satisfiesHalts brocard28 ↔ ∃ n, 8 ≤ n ∧ IsTri (n! / 8)andHalts brocard28 ↔ ∃ n, 7 < n ∧ IsSquare (n! + 1)withoutClassical.choice(Brocard28.lean,Semantics/Brocard28.lean), and with Markov's PrincipleHalts brocard28 ↔ ¬ BrocardConjecture. -
Riemann Hypothesis (
riemann_95,riemann_104,riemann_120, andriemann_744): All four machines (riemann_95,riemann_104, Shunia's 120-state machineriemann_120, and the 744-state machineriemann_744) halt if and only if Mathlib'sRiemannHypothesisis false (Halts candidate ↔ ¬ RiemannHypothesis,Halts riemann120 ↔ ¬ RiemannHypothesis, andHalts riemann744 ↔ ¬ RiemannHypothesis).
-
ZF Consistency (
Details on the proof architecture and the foundational distinction between constructive proof-search equivalence and meta-theoretic non-halting are in Cryptids/Semantics/README.md.
The 95-state Riemann construction retains the
stage counter in x after FOLD and permutes physical operand banks. Its proof
covers the entire blank initializer, the safe first stage, and all later stages,
then composes directly with the existing 104-state semantics. See the
proof guide for the layer boundaries.
For the reduced machines in artifacts/, the state-space transformations affect execution step counts as follows:
goldbach_21(339,411vs.170,966steps throughn = 40,1.99x): Eliminating 4 states (1, 8, 10, 17) reverses the partition enumeration to test larger summands first and routes divisor acceptance through the main counter-tape scanner.zf_380(+0.093%step overhead at1,000,000steps;0step overhead during39,753-step bootstrap): Eliminating 13 states (65, 68, 266, 278, 322, 335, 341, 353, 359, 361, 379, 387, 389) via a 5-cell sliding-window invariant (validState) and non-destructive leftward head bounces (1, 3, 5, 7, 9steps) preserves 100% bit-exact tape equality after every macro-step.riemann_104(9,037vs.89,775,610bootstrap steps,9,934.23xfaster initialization;498,382vs.111,294,346total steps over the first1,000register instructions,223.31xspeedup): Eliminating 16 states (120 -> 104) splits merged scanner state32via a 5-cell window invariant (120 -> 121), replaces the two-phase89.8M-step bootstrap (-9states) with a self-bootstrapping header and dynamic on-demand zero padding (padTotal -> padTotal + 1), and consolidates return scanners and binary call-stack frames (mapStack,-8states).riemann_95(3,634vs.9,037bootstrap steps,2.49xfaster initialization): Retaining the stage counter afterFOLDremoves the subsequent counter transfer. A permutation of the physical register banks permits the shorter blank initializer. The proof covers its complete tape and all subsequent stages.erdos_ternary_14(208,865vs.212steps to reach the stage for2 ^ 9;13,104,473vs.322for2 ^ 12): The saved state costs speed: keeping2 ^ nin unary and dividing it by3in place makes each stage about4xlonger than the previous one, whileerdos_ternary_15keeps the base-3 digits and needs only a few dozen steps per stage at this size.
Build the Cryptids and Challenge targets:
lake exe cache get
lake buildIndependently audit the proofs against Challenge.lean with
leanprover/comparator:
lake comparator --config comparator/constructive.json
lake comparator --config comparator/all.jsonRun the standalone zero-dependency Python verifier (re-compiles upstream baseline sources, checks SHA-256 digests and transition tables, and simulates 250,000 steps per domain):
python3 verify.py