Cslib.Turing.SingleTapeTM.inhabitedStmt
instanceimported Lean
Cslib.Turing.SingleTapeTM.inhabitedStmt
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Cslib Cslib.Turing Cslib.Turing.SingleTapeTM in open Relation in open _root_.Turing in variable {Symbol : Type} in variable [Inhabited Symbol] [Fintype Symbol] (tm : SingleTapeTM Symbol) in instance Cslib.Turing.SingleTapeTM.inhabitedStmt : Inhabited (Stmt Symbol)
- Defined in
- CSLib, `Cslib.Turing.SingleTapeTM.inhabitedStmt`
- 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.inhabitedStmt← Cslib.Turing.SingleTapeTM.inhabitedStmt (Cslib/Computability/Machines/Turing/SingleTape/Deterministic.lean:122): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 2
- Cslib.Turing.SingleTapeTMA single-tape Turing machine over the alphabet of
Option Symbol(wherenoneis the blankBiTapesymbol). - 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.SingleTapeTMA single-tape Turing machine over the alphabet of
- Used by 20
- Cslib.Turing.SingleTapeTM.TransitionRelationThe
TransitionRelationcorresponding to aSingleTapeTM Symbolis defined by thestepfunction, which maps a configuration to its… - 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.TimeComputableA Turing machine + a time function + a proof it outputs
fin at mosttime(input.length)steps. - Cslib.Turing.SingleTapeTM.PolyTimeComputable.idA proof that the identity map on Symbol is computable in polytime.
- Cslib.Turing.SingleTapeTM.OutputsWithinTimeA proof of
tmoutputtingl'on inputlin at mostmsteps. - 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.PolyTimeComputableA Turing machine + a polynomial time function + a proof it outputs
fin at mosttime(input.length)steps. - 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.stepThe step function corresponding to a
SingleTapeTM. - 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.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.idComputerA Turing machine computing the identity.
- 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.OutputsA proof of
tmoutputtingl'on inputl. - Cslib.Turing.SingleTapeTM.map_toCompCfg_left_stepThe left converting function commutes with steps of the machines.
- Cslib.Turing.SingleTapeTM.TimeComputable.idThe identity map on Symbol is computable in constant time.
- Cslib.Turing.SingleTapeTM.TransitionRelationThe
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 _root_.Turing in variable {Symbol : Type} in variable [Inhabited Symbol] [Fintype Symbol] (tm : SingleTapeTM Symbol) in instance Cslib.Turing.SingleTapeTM.inhabitedStmt : Inhabited (Stmt Symbol) := inferInstance