AFTD Auto-Formalizing Theoretical Domains

Cslib.Turing.SingleTapeTM.comp_right_relatesWithinSteps

theoremverifiedformalizationimported Lean

Simulation for the second phase of the composed computer. When the second machine runs from start to halt, the composed machine runs from Sum.inr tm2.q₀ to halt.

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_right_relatesWithinSteps (intermediate output : List Symbol) (t : ℕ)
    (htm2 :
      RelatesWithinSteps tm2.TransitionRelation
        (tm2.initCfg intermediate)
        (tm2.haltCfg output)
        t) :
    RelatesWithinSteps (compComputer tm1 tm2).TransitionRelation
      (intermediateCfg tm1 tm2 intermediate)
      (finalCfg tm1 tm2 output)
      t
Formalizes
CSLib, `Cslib.Turing.SingleTapeTM.comp_right_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 36

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 second phase of the composed computer. When the second machine runs from start to halt, the composed machine runs from Sum.inr tm2.q₀ to halt. -/theorem Cslib.Turing.SingleTapeTM.comp_right_relatesWithinSteps (intermediate output : List Symbol) (t : ℕ)    (htm2 :      RelatesWithinSteps tm2.TransitionRelation        (tm2.initCfg intermediate)        (tm2.haltCfg output)        t) :    RelatesWithinSteps (compComputer tm1 tm2).TransitionRelation      (intermediateCfg tm1 tm2 intermediate)      (finalCfg tm1 tm2 output)      t := by  simp only [intermediateCfg, finalCfg, initCfg, haltCfg] at htm2 ⊢  refine RelatesWithinSteps.map (toCompCfg_right tm1 tm2) ?_ htm2  intro a b hab  grind [map_toCompCfg_right_step tm1 tm2 a]
See it in the graphDiscuss this resultChallenge it