Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

ZF209: literal machine and model-internal halting

Definition
PalomarZF209_History

by LG · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

busy-beaverpalomar-zf209turing-machinezf-independence

This bundle fixes the literal 209209209-state, two-symbol Turing machine and the meaning of its blank-tape halting inside a model of set theory. The transition table literalRows lists, for each working state q∈{0,…,208}q\in\{0,\ldots,208\}q∈{0,…,208}, the two actions (write, move, next state) read on symbol 000 and symbol 111; the halt label is 209209209 and the start state is 000.

Working over a type VVV with membership relation E:V→V→PropE:V\to V\to\mathrm{Prop}E:V→V→Prop, the definitions build the internal set-theoretic apparatus: empty set, successor, pairing, ordered pairs, internal functions (FunctionOn), inductive sets and ω\omegaω (Omega), natural-number objects (NatObject), numerals, and internal addition and multiplication (Add, Mul) defined by internal finite recursion. Binary tape cells are read through BitCons (y=bit+2xy=\text{bit}+2xy=bit+2x), and configurations (Conf) record the state and the left/right tape halves. Step applies the literal table, Terminal marks a halting configuration, and lists are coded by the Cantor pairing 2z=(a+b)(a+b+1)+2b2z=(a+b)(a+b+1)+2b2z=(a+b)(a+b+1)+2b. LinkedRun assembles an internally finite run as an internal function on the successor of a code, and InternalLinkedHalts E asserts a blank-tape linked run ending in a terminal configuration. Histories may have nonstandard length.

These definitions are the machine-side interface for the independence claim; they are reusable for other busy-beaver and model-internal computation formalizations.

Definition code
import Std

namespace PalomarZF209History
abbrev Row := Option (Bool × Bool × Nat)
def literalRows : List (Row × Row) := [
  (some (true, true, 1), some (true, true, 60)),
  (some (true, true, 81), some (true, true, 1)),
  (some (false, false, 2), some (true, false, 3)),
  (some (false, false, 4), some (true, false, 3)),
  (some (false, false, 6), some (true, false, 3)),
  (some (true, true, 7), some (false, false, 5)),
  (some (false, false, 9), some (true, false, 3)),
  (some (false, true, 7), some (false, true, 10)),
  (some (false, true, 13), some (true, true, 12)),
  (some (false, false, 14), some (true, false, 3)),
  (some (false, false, 15), some (false, true, 10)),
  (some (false, false, 25), some (true, true, 17)),
  (some (false, false, 78), some (true, false, 30)),
  (some (false, false, 11), some (false, true, 21)),
  (some (false, false, 22), some (true, false, 3)),
  (some (true, false, 2), some (false, false, 2)),
  (some (false, true, 23), some (false, true, 31)),
  (some (false, true, 83), some (false, false, 94)),
  (some (false, true, 27), some (true, true, 28)),
  (some (false, true, 29), some (true, true, 30)),
  (some (false, true, 23), some (false, true, 56)),
  (some (false, true, 32), some (true, true, 21)),
  (some (false, false, 33), some (true, false, 3)),
  (some (false, false, 34), some (false, true, 1)),
  (some (false, true, 35), some (true, true, 24)),
  (some (false, true, 120), some (true, true, 40)),
  (some (false, true, 37), some (false, false, 38)),
  (some (false, true, 39), some (true, true, 40)),
  (some (false, true, 41), some (true, true, 42)),
  (some (false, true, 43), some (true, true, 44)),
  (some (false, true, 20), some (true, true, 45)),
  (some (false, true, 46), some (true, true, 31)),
  (some (false, true, 31), some (true, true, 32)),
  (some (false, false, 68), some (true, false, 3)),
  (some (true, true, 34), some (true, false, 2)),
  (some (false, true, 48), some (true, true, 35)),
  (some (false, true, 27), some (true, true, 19)),
  (some (false, false, 11), some (false, true, 35)),
  (some (false, false, 5), some (true, false, 50)),
  (some (false, true, 23), some (false, true, 24)),
  (some (false, true, 12), some (false, false, 15)),
  (some (false, true, 52), some (true, true, 53)),
  (some (false, true, 54), some (true, true, 55)),
  (some (false, true, 23), some (false, true, 51)),
  (some (false, true, 57), some (true, true, 58)),
  (some (false, true, 59), some (false, false, 15)),
  (some (false, true, 24), some (true, true, 46)),
  (some (false, false, 34), some (false, true, 60)),
  (some (false, true, 15), some (true, true, 48)),
  (some (false, true, 62), some (true, true, 63)),
  (some (false, false, 38), some (true, false, 50)),
  (some (false, true, 21), some (true, true, 51)),
  (some (false, false, 11), some (false, true, 48)),
  (some (false, true, 57), some (false, false, 15)),
  (some (false, true, 64), some (true, true, 65)),
  (some (false, true, 58), some (true, true, 66)),
  (some (false, true, 51), some (true, true, 56)),
  (some (false, true, 47), some (false, true, 24)),
  (some (false, false, 27), some (true, false, 67)),
  (some (false, false, 101), some (true, false, 29)),
  (some (false, true, 0), some (true, true, 60)),
  (some (true, true, 123), some (true, false, 50)),
  (some (false, true, 69), some (true, true, 209)),
  (some (false, false, 124), some (true, true, 30)),
  (some (false, true, 39), some (true, true, 59)),
  (some (false, false, 78), some (true, true, 70)),
  (some (false, true, 52), some (true, false, 71)),
  (some (false, true, 72), some (true, true, 73)),
  (some (false, true, 68), some (true, true, 74)),
  (some (false, true, 75), some (true, true, 76)),
  (some (false, true, 78), some (true, false, 109)),
  (some (false, false, 97), some (true, true, 53)),
  (some (false, true, 47), some (false, true, 32)),
  (some (false, true, 80), some (false, false, 40)),
  (some (false, true, 49), some (true, true, 128)),
  (some (false, true, 126), some (true, true, 20)),
  (some (false, true, 100), some (true, true, 89)),
  (some (false, true, 91), some (true, true, 92)),
  (some (false, true, 72), some (true, true, 71)),
  (some (false, true, 90), some (true, true, 117)),
  (some (false, true, 94), some (true, true, 95)),
  (some (false, true, 61), some (false, true, 1)),
  (some (false, true, 26), some (true, true, 96)),
  (some (false, true, 88), some (true, true, 87)),
  (some (true, false, 98), some (true, false, 84)),
  (some (false, true, 18), some (true, true, 99)),
  (some (false, true, 57), some (true, true, 57)),
  (some (false, true, 115), some (true, true, 114)),
  (some (false, false, 25), some (true, true, 208)),
  (some (false, true, 94), some (false, false, 127)),
  (some (false, true, 101), some (true, true, 102)),
  (some (false, true, 66), some (true, true, 55)),
  (some (false, true, 54), some (true, true, 103)),
  (some (false, true, 20), some (true, true, 104)),
  (some (false, true, 20), some (false, false, 10)),
  (some (false, true, 58), some (true, true, 40)),
  (some (false, true, 105), some (true, true, 8)),
  (some (false, true, 90), some (true, true, 106)),
  (some (false, false, 127), some (false, false, 84)),
  (some (false, true, 107), some (true, true, 93)),
  (some (false, false, 108), some (false, false, 2)),
  (some (false, true, 37), some (true, true, 67)),
  (some (false, true, 58), some (true, true, 109)),
  (some (false, true, 58), some (true, true, 110)),
  (some (false, true, 65), some (false, false, 15)),
  (some (false, true, 13), some (true, true, 109)),
  (some (false, true, 20), some (true, true, 111)),
  (some (false, true, 112), some (true, false, 19)),
  (some (false, true, 29), some (true, true, 64)),
  (some (false, true, 37), some (true, false, 107)),
  (some (false, true, 119), some (false, false, 15)),
  (some (false, true, 113), some (false, false, 15)),
  (some (false, true, 23), some (false, true, 46)),
  (some (false, true, 47), some (false, true, 31)),
  (some (false, true, 69), some (true, true, 85)),
  (some (false, true, 124), some (true, true, 27)),
  (some (false, true, 120), some (true, true, 106)),
  (some (false, true, 93), some (true, true, 85)),
  (some (false, true, 82), some (true, true, 97)),
  (some (false, true, 86), some (true, true, 86)),
  (some (false, true, 16), some (true, false, 108)),
  (some (false, true, 69), some (true, true, 100)),
  (some (false, true, 95), some (true, true, 107)),
  (some (true, false, 38), some (true, false, 98)),
  (some (false, true, 79), some (true, true, 77)),
  (some (false, true, 118), some (true, true, 129)),
  (some (false, true, 43), some (true, true, 89)),
  (some (false, false, 5), some (false, false, 127)),
  (some (false, true, 125), some (true, true, 58)),
  (some (false, true, 11), some (true, true, 36)),
  (some (false, true, 18), some (true, true, 19)),
  (some (false, true, 77), some (true, true, 86)),
  (some (false, true, 85), some (true, true, 131)),
  (some (false, true, 130), some (true, true, 132)),
  (some (false, false, 159), some (true, true, 77)),
  (some (false, false, 169), some (true, true, 134)),
  (some (false, true, 18), some (true, true, 116)),
  (some (false, true, 136), some (true, true, 134)),
  (some (false, true, 134), some (true, true, 133)),
  (some (false, true, 57), some (true, true, 77)),
  (some (false, true, 18), some (true, true, 139)),
  (some (false, false, 197), some (true, true, 140)),
  (some (false, true, 140), some (true, true, 141)),
  (some (false, true, 138), some (true, true, 135)),
  (some (false, true, 137), some (true, true, 143)),
  (some (false, true, 136), some (true, true, 131)),
  (some (false, true, 130), some (true, true, 145)),
  (some (false, true, 132), some (true, true, 133)),
  (some (false, true, 145), some (true, true, 77)),
  (some (false, false, 147), some (true, false, 184)),
  (some (false, true, 149), some (true, true, 57)),
  (some (false, true, 130), some (true, true, 150)),
  (some (false, true, 148), some (true, true, 151)),
  (some (false, false, 174), some (true, true, 152)),
  (some (false, true, 146), some (true, true, 153)),
  (some (false, true, 144), some (true, true, 154)),
  (some (false, true, 135), some (true, true, 155)),
  (some (false, true, 124), some (true, true, 156)),
  (some (false, true, 77), some (true, true, 157)),
  (some (false, true, 158), some (true, true, 146)),
  (some (false, true, 136), some (true, false, 152)),
  (some (false, false, 184), some (true, true, 160)),
  (some (false, true, 138), some (true, true, 57)),
  (some (false, true, 161), some (true, true, 162)),
  (some (false, true, 163), some (true, true, 137)),
  (some (false, true, 164), some (true, true, 163)),
  (some (false, true, 159), some (true, true, 165)),
  (some (false, true, 85), some (true, true, 166)),
  (some (false, true, 142), some (true, true, 160)),
  (some (false, true, 167), some (true, true, 168)),
  (some (false, true, 130), some (true, true, 169)),
  (some (false, true, 63), some (true, true, 170)),
  (some (false, true, 57), some (true, true, 137)),
  (some (false, true, 147), some (true, true, 162)),
  (some (false, true, 172), some (true, true, 173)),
  (some (false, true, 171), some (true, true, 174)),
  (some (false, true, 175), some (true, true, 133)),
  (some (false, true, 133), some (true, true, 176)),
  (some (false, true, 160), some (true, true, 57)),
  (some (false, true, 130), some (true, true, 178)),
  (some (false, true, 179), some (true, true, 161)),
  (some (false, true, 148), some (true, true, 180)),
  (some (false, true, 151), some (true, true, 181)),
  (some (false, true, 153), some (true, true, 182)),
  (some (false, true, 139), some (true, true, 145)),
  (some (false, true, 137), some (true, true, 184)),
  (some (false, true, 136), some (true, true, 179)),
  (some (false, true, 140), some (true, true, 77)),
  (some (false, true, 187), some (true, true, 149)),
  (some (false, true, 186), some (true, true, 188)),
  (some (false, true, 136), some (true, true, 189)),
  (some (false, true, 190), some (true, true, 188)),
  (some (false, true, 185), some (true, true, 191)),
  (some (false, true, 183), some (true, true, 192)),
  (some (false, false, 197), some (true, true, 187)),
  (some (false, true, 77), some (true, true, 194)),
  (some (false, true, 132), some (true, true, 188)),
  (some (false, true, 195), some (true, true, 196)),
  (some (false, true, 193), some (true, true, 197)),
  (some (false, true, 194), some (true, true, 148)),
  (some (false, true, 141), some (true, true, 120)),
  (some (false, true, 121), some (false, false, 127)),
  (some (false, true, 122), some (true, true, 201)),
  (some (false, true, 121), some (true, true, 202)),
  (some (false, true, 200), some (true, true, 203)),
  (some (false, true, 199), some (true, true, 204)),
  (some (false, true, 186), some (true, true, 205)),
  (some (false, true, 198), some (true, true, 206)),
  (some (false, true, 177), some (true, true, 207))
]
section InternalSets
variable {V : Type} (E : V → V → Prop)
def Empty (a : V) : Prop := ∀ x, ¬ E x a
def Succ (a b : V) : Prop := ∀ x, E x b ↔ E x a ∨ x = a
def Pair (a b p : V) : Prop := ∀ x, E x p ↔ x = a ∨ x = b
def OrderedPair (a b p : V) : Prop :=
 ∃ aa ab, Pair E a a aa ∧ Pair E a b ab ∧ Pair E aa ab p
def At (f x y : V) : Prop := ∃ p, E p f ∧ OrderedPair E x y p
/-- The function and its domain are elements of the model, not external maps. -/
def FunctionOn (f domain : V) : Prop :=
 (∀ x, E x domain → ∃ y, At E f x y ∧ ∀ z, At E f x z → z = y) ∧
 (∀ p, E p f → ∃ x y, E x domain ∧ OrderedPair E x y p)
def Inductive (a : V) : Prop :=
 (∃ z, Empty E z ∧ E z a) ∧ ∀ x, E x a → ∃ y, Succ E x y ∧ E y a
def Omega (w : V) : Prop :=
 Inductive E w ∧ ∀ a, Inductive E a → ∀ x, E x w → E x a
/-- Meaningful on actual ZF models, where a unique omega exists. -/
def NatObject (x : V) : Prop := ∃ w, Omega E w ∧ E x w
def Numeral : Nat → V → Prop
 | 0, x => Empty E x
 | n + 1, x => ∃ y, Numeral n y ∧ Succ E y x
/-- Internal finite recursion, including nonstandard finite lengths. -/
def Add (a b c : V) : Prop :=
 NatObject E a ∧ NatObject E b ∧ NatObject E c ∧
 ∃ z domain f, Empty E z ∧ Succ E b domain ∧ FunctionOn E f domain ∧
 At E f z a ∧ At E f b c ∧
 (∀ i x, E i domain → At E f i x → NatObject E x) ∧
 ∀ i, E i b → ∃ j x y, Succ E i j ∧ At E f i x ∧ At E f j y ∧ Succ E x y
def Mul (a b c : V) : Prop :=
 NatObject E a ∧ NatObject E b ∧ NatObject E c ∧
 ∃ z domain f, Empty E z ∧ Succ E b domain ∧ FunctionOn E f domain ∧
 At E f z z ∧ At E f b c ∧
 (∀ i x, E i domain → At E f i x → NatObject E x) ∧
 ∀ i, E i b → ∃ j x y, Succ E i j ∧ At E f i x ∧ At E f j y ∧ Add E x a y
/-- y = bit + 2*x, using arithmetic internal to the set model. -/
def BitCons (bit : Bool) (x y : V) : Prop :=
 ∃ b two twice, Numeral E (if bit then 1 else 0) b ∧ Numeral E 2 two ∧
 Mul E two x twice ∧ Add E b twice y
structure Conf (V : Type) where
 q : V
 left : V
 right : V
def Valid (s : Conf V) : Prop := NatObject E s.q ∧ NatObject E s.left ∧ NatObject E s.right
/-- Literal table movement. true means right; false means left. -/
def Move (read write direction : Bool) (next : Nat) (s t : Conf V) : Prop :=
 ∃ r, BitCons E read r s.right ∧ Numeral E next t.q ∧
 if direction then BitCons E write s.left t.left ∧ t.right = r
 else ∃ l bit middle, BitCons E bit l s.left ∧ t.left = l ∧
   BitCons E write r middle ∧ BitCons E bit middle t.right
/-- All 209 rows are fixed above. The initial state is 0, not a supplied parameter. -/
def Step (s t : Conf V) : Prop :=
 Valid E s ∧ Valid E t ∧ ∃ q : Fin 209, Numeral E q.val s.q ∧
 ∃ read write direction next,
 (if read then (literalRows.getD q.val (none,none)).2 else (literalRows.getD q.val (none,none)).1) = some (write,direction,next) ∧
 Move E read write direction next s t
/-- This finite condition matches no outgoing row: both entries of every
in-range row are defined. It requires a separate exact-row totality proof. -/
def Terminal (s : Conf V) : Prop := ∀ q : Fin 209, ¬ Numeral E q.val s.q
/-- Cantor graph, matching the production equation
2*z=(a+b)*(a+b+1)+2*b. All witnesses are model objects. -/
def Cantor (a b z : V) : Prop :=
 NatObject E a ∧ NatObject E b ∧ NatObject E z ∧
 ∃ two sum next product twiceB twiceZ total,
 Numeral E 2 two ∧ Add E a b sum ∧ Succ E sum next ∧
 Mul E sum next product ∧ Mul E two b twiceB ∧
 Mul E two z twiceZ ∧ Add E product twiceB total ∧ twiceZ = total
def ListCons (a b c : V) : Prop := ∃ p, Cantor E a b p ∧ Succ E p c
def ListHead (x a : V) : Prop :=
 (Empty E x ∧ Empty E a) ∨ ∃ b, ListCons E a b x
def ListTail (x b : V) : Prop :=
 (Empty E x ∧ Empty E b) ∨ ∃ a, ListCons E a b x
def NumericConfCode (s : Conf V) (code : V) : Prop :=
 ∃ lr, Cantor E s.left s.right lr ∧ Cantor E s.q lr code
def NumericStep (before after : V) : Prop :=
 ∃ s t : Conf V, NumericConfCode E s before ∧ NumericConfCode E t after ∧ Step E s t
def RunEdge (initial next tail : V) : Prop :=
 (Empty E tail ∧ next = initial) ∨
 (¬ Empty E tail ∧ ∃ previous, ListHead E tail previous ∧ NumericStep E previous next)
/-- Preferred production-aligned representation. The iterator f is an
internal set function on successor(code), NOT an external recursive function.
Every nonzero tail encountered before code steps has a correct run edge. -/
def LinkedRun (initial code : V) : Prop :=
 NatObject E initial ∧ NatObject E code ∧ ¬ Empty E code ∧
 ∃ zero domain f, Empty E zero ∧ Succ E code domain ∧ FunctionOn E f domain ∧
 At E f zero code ∧ At E f code zero ∧
 (∀ i x, E i domain → At E f i x → NatObject E x) ∧
 ∀ i, E i code → ∃ j x y, Succ E i j ∧ At E f i x ∧ At E f j y ∧
 ListTail E x y ∧ (Empty E x ∨ ∃ a b, ListHead E x a ∧ ListTail E x b ∧ RunEdge E initial a b)
/-- Primary proposed Challenge operational predicate. The equivalence with
production physicalHalts is a NEW proof obligation, not assumed here. -/
def InternalLinkedHalts : Prop :=
 ∃ zero hist last, ∃ (t : Conf V), Empty E zero ∧ LinkedRun E zero hist ∧
 ListHead E hist last ∧ NumericConfCode E t last ∧ Valid E t ∧ Terminal E t
end InternalSets
end PalomarZF209History
Source
https://github.com/jamesyc/BusyBeaver/blob/37861b991bb70dbaee7dbd91120ab533cba658e2/ZF209/ProofSources/Challenge.lean#L7-L314

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me