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.Cslib.Turing.SingleTapeTM.comp_left_relatesWithinSteps← Cslib.Turing.SingleTapeTM.comp_left_relatesWithinSteps (Cslib/Computability/Machines/Turing/SingleTape/Deterministic.lean:335): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 39
- Cslib.Turing.SingleTapeTM.TransitionRelationThe
TransitionRelationcorresponding to aSingleTapeTM Symbolis defined by thestepfunction, which maps a configuration to its… - Cslib.Turing.SingleTapeTM.haltCfgThe final configuration corresponding to a list in the output alphabet. (We demand that the head halts at the leftmost position of the…
- Cslib.Turing.SingleTapeTM.initialCfgThe initial configuration for the composed machine, with the first machine starting.
- Cslib.Turing.BiTape.instInhabitedCslib.Turing.BiTape.instInhabited
- Cslib.Turing.StackTape.empty_eq_nilCslib.Turing.StackTape.empty_eq_nil
- Cslib.Turing.BiTape.optionMoveOptionally perform a
move, or do nothing ifnone. - Cslib.Turing.BiTape.instEmptyCollectionCslib.Turing.BiTape.instEmptyCollection
- Cslib.Turing.StackTape.cons_none_nil_toListCslib.Turing.StackTape.cons_none_nil_toList
- Cslib.Turing.StackTape.instEmptyCollectionCslib.Turing.StackTape.instEmptyCollection
- Cslib.Turing.StackTape.instInhabitedCslib.Turing.StackTape.instInhabited
- Cslib.Turing.BiTape.empty_eq_nilCslib.Turing.BiTape.empty_eq_nil
- Cslib.Turing.StackTape.length_nilCslib.Turing.StackTape.length_nil
- Cslib.Turing.BiTape.spaceUsed_writeCslib.Turing.BiTape.spaceUsed_write
- Cslib.Turing.BiTape.moveLeft_moveRightCslib.Turing.BiTape.moveLeft_moveRight
- Cslib.Turing.BiTape.writeWrite a value under the head of the
BiTape. - Cslib.Turing.BiTape.moveRight_moveLeftCslib.Turing.BiTape.moveRight_moveLeft
- Cslib.Turing.StackTape.head_consCslib.Turing.StackTape.head_cons
- Cslib.Turing.SingleTapeTM.toCompCfg_leftConvert a
Cfgover the first input machine to a config over the composed machine. Note it may transition to the start state of the… - Cslib.Turing.StackTape.tail_consCslib.Turing.StackTape.tail_cons
- Cslib.Turing.StackTape.cons_some_toListCslib.Turing.StackTape.cons_some_toList
- Cslib.Turing.StackTape.cons_head_tailCslib.Turing.StackTape.cons_head_tail
- Cslib.Turing.SingleTapeTM.stepThe step function corresponding to a
SingleTapeTM. - Cslib.Turing.BiTape.mk₁Given a
ListofSymbols, construct aBiTapeby mapping the list tosomeelements and laying them out to the right side, with the… - Cslib.Turing.SingleTapeTM.compComputerA Turing machine computing the composition of two other Turing machines. If f and g are computed by Turing machines
tm1andtm2then… - Cslib.Turing.BiTapeA structure for bidirectionally-infinite Turing machine tapes that eventually take on blank
nonevalues - Cslib.Turing.SingleTapeTM.intermediateCfgThe intermediate configuration for the composed machine, after the first machine halts and the second machine starts.
- Cslib.Turing.StackTape.length_mapSomeCslib.Turing.StackTape.length_mapSome
- Cslib.Turing.StackTape.nil_toListCslib.Turing.StackTape.nil_toList
- Cslib.Turing.SingleTapeTMA single-tape Turing machine over the alphabet of
Option Symbol(wherenoneis the blankBiTapesymbol). - Cslib.Turing.SingleTapeTM.inhabitedStmtCslib.Turing.SingleTapeTM.inhabitedStmt
- Cslib.Turing.SingleTapeTM.initCfgThe initial configuration corresponding to a list in the input alphabet. Note that the entries of the tape constructed by
BiTape.mk₁are… - Cslib.Turing.SingleTapeTM.CfgThe configurations of a Turing machine consist of: an
Optional state (or none for the halting state), and aBiTaperepresenting the… - Cslib.Turing.SingleTapeTM.map_toCompCfg_left_stepThe left converting function commutes with steps of the machines.
- Relation.RelatesWithinSteps
RelatesWithinStepsis a variant ofRelatesInStepsthat allows for a loose bound. It states thatarelates tobin *at most*n… - Relation.RelatesWithinSteps.mapIf
gis a homomorphism fromrtor'(i.e., it preserves the reduction relation), thenRelatesWithinStepsis preserved underg. - Cslib.Turing.SingleTapeTM.StmtA Turing machine "statement" is just a
Optional command to move left or right, and write a symbol (i.e. anOption Symbol, wherenone… - Cslib.Turing.StackTapeAn infinite tape representation using a list of
Optionvalues, where the list is eventuallynone. Represented as a… - Relation.RelatesInSteps.zero_iffRelation.RelatesInSteps.zero_iff
- Relation.RelatesWithinSteps.zero_iffRelation.RelatesWithinSteps.zero_iff
- Cslib.Turing.SingleTapeTM.TransitionRelationThe
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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