AFTD Auto-Formalizing Theoretical Domains

Cslib.Turing.SingleTapeTM.comp_left_relatesWithinSteps

theoremverifiedformalizationimported Lean

Simulation for the first phase of the composed computer. When the first machine runs from start to halt, the composed machine runs from start (with Sum.inl state) to Sum.inr tm2.q₀ (the start of the second phase). This takes the same number of steps because the halt transition becomes a transition to the second machine.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Cslib Cslib.Turing Cslib.Turing.SingleTapeTM in
open Relation in
open Cslib.Turing.BiTape Cslib.Turing.StackTape in
open _root_.Turing in
variable {Symbol : Type} in
variable [Inhabited Symbol] [Fintype Symbol] in
variable (tm1 tm2 : SingleTapeTM Symbol) (cfg1 : tm1.Cfg) (cfg2 : tm2.Cfg) in
theorem Cslib.Turing.SingleTapeTM.comp_left_relatesWithinSteps (input intermediate : List Symbol) (t : ℕ)
    (htm1 :
      RelatesWithinSteps tm1.TransitionRelation
        (tm1.initCfg input)
        (tm1.haltCfg intermediate)
        t) :
    RelatesWithinSteps (compComputer tm1 tm2).TransitionRelation
      (initialCfg tm1 tm2 input)
      (intermediateCfg tm1 tm2 intermediate)
      t
Formalizes
CSLib, `Cslib.Turing.SingleTapeTM.comp_left_relatesWithinSteps`
Lean proof
By Bolton Bailey, Pim Spelier, Daan van Gent, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2026 Bolton Bailey. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 39

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Cslib Cslib.Turing Cslib.Turing.SingleTapeTM inopen Relation inopen Cslib.Turing.BiTape Cslib.Turing.StackTape inopen _root_.Turing invariable {Symbol : Type} invariable [Inhabited Symbol] [Fintype Symbol] invariable (tm1 tm2 : SingleTapeTM Symbol) (cfg1 : tm1.Cfg) (cfg2 : tm2.Cfg) in/-- Simulation for the first phase of the composed computer. When the first machine runs from start to halt, the composed machine runs from start (with Sum.inl state) to Sum.inr tm2.q₀ (the start of the second phase). This takes the same number of steps because the halt transition becomes a transition to the second machine. -/theorem Cslib.Turing.SingleTapeTM.comp_left_relatesWithinSteps (input intermediate : List Symbol) (t : ℕ)    (htm1 :      RelatesWithinSteps tm1.TransitionRelation        (tm1.initCfg input)        (tm1.haltCfg intermediate)        t) :    RelatesWithinSteps (compComputer tm1 tm2).TransitionRelation      (initialCfg tm1 tm2 input)      (intermediateCfg tm1 tm2 intermediate)      t := by  simp only [initialCfg, intermediateCfg, initCfg, haltCfg] at htm1 ⊢  refine RelatesWithinSteps.map (toCompCfg_left tm1 tm2) ?_ htm1  intro a b hab  have ha : a.state.isSome := by    simp only [TransitionRelation, step] at hab    cases a with | mk state _ => cases state <;> simp_all  have h1 := map_toCompCfg_left_step tm1 tm2 a ha  rw [hab, Option.map_some] at h1  exact h1.symm
See it in the graphDiscuss this resultChallenge it