AFTD Auto-Formalizing Theoretical Domains

Cslib.Turing.SingleTapeTM

structureimported Lean

A single-tape Turing machine over the alphabet of Option Symbol (where none is the blank BiTape symbol).

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Cslib Cslib.Turing in
open Relation in
open Cslib.Turing.BiTape Cslib.Turing.StackTape in
open _root_.Turing in
variable {Symbol : Type} in
structure Cslib.Turing.SingleTapeTM Symbol [Inhabited Symbol] [Fintype Symbol]
Defined in
CSLib, `Cslib.Turing.SingleTapeTM`
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.
Verified
08 Oct 2026
Axioms
none listed
Built on 20
Used by 29

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Cslib Cslib.Turing in
open Relation in
open Cslib.Turing.BiTape Cslib.Turing.StackTape in
open _root_.Turing in
variable {Symbol : Type} in
/-- A single-tape Turing machine over the alphabet of `Option Symbol` (where `none` is the blank `BiTape` symbol). -/
structure Cslib.Turing.SingleTapeTM Symbol [Inhabited Symbol] [Fintype Symbol] where
  /-- type of state labels -/
  (State : Type)
  /-- finiteness of the state type -/
  [stateFintype : Fintype State]
  /-- Initial state -/
  (q₀ : State)
  /-- Transition function, mapping a state and a head symbol to a `Stmt` to invoke,
  and optionally the new state to transition to afterwards (`none` for halt) -/
  (tr : State → Option Symbol → SingleTapeTM.Stmt Symbol × Option State)
See it in the graphDiscuss this resultChallenge it