AFTD Auto-Formalizing Theoretical Domains

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.
Verified
08 Oct 2026
Axioms
none listed
Built on 1
  • Turing.MultiTapeTMA multi-tape Turing machine with k work tapes over the alphabet of Option Symbol (where none is the blank BiTape symbol). Note…

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