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.Cslib.Turing.SingleTapeTM.comp_right_relatesWithinSteps← Cslib.Turing.SingleTapeTM.comp_right_relatesWithinSteps (Cslib/Computability/Machines/Turing/SingleTape/Deterministic.lean:360): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 36
- 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.BiTape.instInhabitedCslib.Turing.BiTape.instInhabited
- Cslib.Turing.StackTape.empty_eq_nilCslib.Turing.StackTape.empty_eq_nil
- Cslib.Turing.SingleTapeTM.map_toCompCfg_right_stepThe right converting function commutes with steps of the machines.
- 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.SingleTapeTM.finalCfgThe final configuration for the composed machine, after the second machine halts.
- 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.moveRight_moveLeftCslib.Turing.BiTape.moveRight_moveLeft
- Cslib.Turing.StackTape.head_consCslib.Turing.StackTape.head_cons
- 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.toCompCfg_rightConvert a
Cfgover the second input machine to a config over the composed machine - 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… - 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.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 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]