AFTD Auto-Formalizing Theoretical Domains

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.
Verified
08 Oct 2026
Axioms
none listed
Built on 1
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…

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
See it in the graphDiscuss this resultChallenge it