Cslib.Turing.SingleTapeTM.Stmt
structureimported Lean
A Turing machine "statement" is just a Optional command to move left or right, and write a symbol (i.e. an Option Symbol, where none is the blank symbol) on the BiTape
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Relation in open _root_.Turing in variable {Symbol : Type} in structure Cslib.Turing.SingleTapeTM.Stmt (Symbol : Type)
- Defined in
- CSLib, `Cslib.Turing.SingleTapeTM.Stmt`
- 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.Stmt← Cslib.Turing.SingleTapeTM.Stmt (Cslib/Computability/Machines/Turing/SingleTape/Deterministic.lean:80): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 8
- Cslib.Turing.SingleTapeTM.map_toCompCfg_right_stepThe right converting function commutes with steps of the machines.
- 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.SingleTapeTMA single-tape Turing machine over the alphabet of
Option Symbol(wherenoneis the blankBiTapesymbol). - Cslib.Turing.SingleTapeTM.inhabitedStmtCslib.Turing.SingleTapeTM.inhabitedStmt
- 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 Relation in open _root_.Turing in variable {Symbol : Type} in /-- A Turing machine "statement" is just a `Option`al command to move left or right, and write a symbol (i.e. an `Option Symbol`, where `none` is the blank symbol) on the `BiTape` -/ structure Cslib.Turing.SingleTapeTM.Stmt (Symbol : Type) where /-- The symbol to write at the current head position -/ symbol : Option Symbol /-- The direction to move the tape head -/ movement : Option Dir deriving Inhabited