Turing.MultiTapeTM
structureimported Lean
A multi-tape Turing machine with k work tapes over the alphabet of Option Symbol (where none is the blank BiTape symbol). Note that it is not required that Symbol or State are finite to keep the definition more general. The restriction will be introduced once we start talking about computability by Turing machines in general.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Relation in variable {k : ℕ} {State Symbol : Type*} in structure Turing.MultiTapeTM (k : ℕ) (Symbol State : Type*)
- Defined in
- CSLib, `Turing.MultiTapeTM`
- 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← Turing.MultiTapeTM (Cslib/Computability/Machines/Turing/MultiTape/Deterministic.lean:121): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 1
- Turing.TransitionOutThe output of the transition function.
- Used by 1
- Turing.MultiTapeTM.CfgThe configurations of a Turing machine is relative to the input of the machine and consist of: - an
Optional state (or none for the…
- Turing.MultiTapeTM.CfgThe configurations of a Turing machine is relative to the input of the machine and consist of: - an
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Relation in variable {k : ℕ} {State Symbol : Type*} in /-- A multi-tape Turing machine with `k` work tapes over the alphabet of `Option Symbol` (where `none` is the blank `BiTape` symbol). Note that it is not required that `Symbol` or `State` are finite to keep the definition more general. The restriction will be introduced once we start talking about computability by Turing machines in general. -/ structure Turing.MultiTapeTM (k : ℕ) (Symbol State : Type*) where /-- initial state -/ q₀ : State /-- transition function, mapping a state, the current input symbol and a tuple of work head symbols to a movement for the input head, actions on the work tape, optionally a symbol to output and the successor state -/ tr (q : State) (input : Option Symbol) (work : Fin k → Option Symbol) : TransitionOut k Symbol State