Turing.MultiTapeTM.Cfg
structureimported Lean
The configurations of a Turing machine is relative to the input of the machine and consist of: - an Optional state (or none for the halting state), - the position of the input head (shifted by one), - the contents of the work tape, - the positions of the work tape heads.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Turing in open Relation in variable {k : ℕ} {State Symbol : Type*} in variable {tm : MultiTapeTM k Symbol State} in @[ext] structure Turing.MultiTapeTM.Cfg (k : ℕ) (Symbol State : Type*) (input : List Symbol)
- Defined in
- CSLib, `Turing.MultiTapeTM.Cfg`
- Lean proof
- By Christian Reitwiessner, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2026 Christian Reitwiessner. 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.Turing.MultiTapeTM.Cfg← Turing.MultiTapeTM.Cfg (Cslib/Computability/Machines/Turing/MultiTape/Deterministic.lean:152): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 1
- Turing.MultiTapeTMA multi-tape Turing machine with
kwork tapes over the alphabet ofOption Symbol(wherenoneis the blankBiTapesymbol). Note…
- Turing.MultiTapeTMA multi-tape Turing machine with
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Turing in open Relation in variable {k : ℕ} {State Symbol : Type*} in variable {tm : MultiTapeTM k Symbol State} in /-- The configurations of a Turing machine is relative to the input of the machine and consist of: - an `Option`al state (or none for the halting state), - the position of the input head (shifted by one), - the contents of the work tape, - the positions of the work tape heads. -/ @[ext] structure Turing.MultiTapeTM.Cfg (k : ℕ) (Symbol State : Type*) (input : List Symbol) where /-- the state of the TM (or none for the halting state) -/ state : Option State /-- the position of the input head, shifted by one -/ inputPos : Fin (input.length + 2) /-- the work tapes -/ workTapes : Fin k → ℤ → Option Symbol /-- the positions of the heads on the work tapes -/ workTapePos : Fin k → ℤ deriving Inhabited