Cslib.Turing.SingleTapeTM.compComputer
defimported Lean
A Turing machine computing the composition of two other Turing machines. If f and g are computed by Turing machines tm1 and tm2 then we can construct a Turing machine which computes g ∘ f by first running tm1 and then, when tm1 halts, transitioning to the start state of tm2 and running tm2.
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 def Cslib.Turing.SingleTapeTM.compComputer (tm1 tm2 : SingleTapeTM Symbol) : SingleTapeTM Symbol
- Defined in
- CSLib, `Cslib.Turing.SingleTapeTM.compComputer`
- 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.compComputer← Cslib.Turing.SingleTapeTM.compComputer (Cslib/Computability/Machines/Turing/SingleTape/Deterministic.lean:237): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 24
- Cslib.Turing.BiTape.instInhabitedCslib.Turing.BiTape.instInhabited
- Cslib.Turing.StackTape.empty_eq_nilCslib.Turing.StackTape.empty_eq_nil
- 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.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.SingleTapeTM.instFintypeStateCslib.Turing.SingleTapeTM.instFintypeState
- 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.BiTapeA structure for bidirectionally-infinite Turing machine tapes that eventually take on blank
nonevalues - 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.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…
- Used by 10
- Cslib.Turing.SingleTapeTM.initialCfgThe initial configuration for the composed machine, with the first machine starting.
- Cslib.Turing.SingleTapeTM.map_toCompCfg_right_stepThe right converting function commutes with steps of the machines.
- Cslib.Turing.SingleTapeTM.compComputer_q₀_eqCslib.Turing.SingleTapeTM.compComputer_q₀_eq
- Cslib.Turing.SingleTapeTM.finalCfgThe final configuration for the composed machine, after the second machine halts.
- Cslib.Turing.SingleTapeTM.comp_right_relatesWithinStepsSimulation for the second phase of the composed computer. When the second machine runs from start to halt, the composed machine runs from…
- 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.SingleTapeTM.comp_left_relatesWithinStepsSimulation for the first phase of the composed computer. When the first machine runs from start to halt, the composed machine runs from…
- Cslib.Turing.SingleTapeTM.intermediateCfgThe intermediate configuration for the composed machine, after the first machine halts and the second machine starts.
- Cslib.Turing.SingleTapeTM.toCompCfg_rightConvert a
Cfgover the second input machine to a config over the composed machine - Cslib.Turing.SingleTapeTM.map_toCompCfg_left_stepThe left converting function commutes with steps of the machines.
Lean source view module on GitHub
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 /-- A Turing machine computing the composition of two other Turing machines. If f and g are computed by Turing machines `tm1` and `tm2` then we can construct a Turing machine which computes g ∘ f by first running `tm1` and then, when `tm1` halts, transitioning to the start state of `tm2` and running `tm2`. -/ def Cslib.Turing.SingleTapeTM.compComputer (tm1 tm2 : SingleTapeTM Symbol) : SingleTapeTM Symbol where -- The states of the composed machine are the disjoint union of the states of the input machines. State := tm1.State ⊕ tm2.State -- The start state is the start state of the first input machine. q₀ := .inl tm1.q₀ tr q h := match q with -- If we are in the first input machine's states, run that machine ... | .inl ql => match tm1.tr ql h with | (stmt, state) => -- ... taking the same tape action as the first input machine would. (stmt, match state with -- If it halts, transition to the start state of the second input machine | none => some (.inr tm2.q₀) -- Otherwise continue as normal | _ => Option.map .inl state) -- If we are in the second input machine's states, run that machine ... | .inr qr => match tm2.tr qr h with | (stmt, state) => -- ... taking the same tape action as the second input machine would. (stmt, match state with -- If it halts, transition to the halting state | none => none -- Otherwise continue as normal | _ => Option.map .inr state)