Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg
theoremverifiedformalizationimported Lean
Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Cslib Cslib.Turing Cslib.Turing.SingleTapeTM in open Relation in open Cslib.Turing.BiTape Cslib.Turing.StackTape in open _root_.Turing in variable {Symbol : Type} in variable [Inhabited Symbol] [Fintype Symbol] (tm : SingleTapeTM Symbol) in @[grind =] lemma Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg (tm : SingleTapeTM Symbol) (s : List Symbol) : (tm.initCfg s).spaceUsed = max 1 s.length
- Formalizes
- CSLib, `Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg`
- 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.Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg← Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg (Cslib/Computability/Machines/Turing/SingleTape/Deterministic.lean:167): adapted
What was changed in
Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg--- Cslib/Computability/Machines/Turing/SingleTape/Deterministic.lean:167 (Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg) +++ as compiled here @@ -1,3 +1,11 @@ -@[scoped grind =] -lemma Cfg.spaceUsed_initCfg (tm : SingleTapeTM Symbol) (s : List Symbol) : +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +open Cslib Cslib.Turing Cslib.Turing.SingleTapeTM in +open Relation in +open Cslib.Turing.BiTape Cslib.Turing.StackTape in +open _root_.Turing in +variable {Symbol : Type} in +variable [Inhabited Symbol] [Fintype Symbol] (tm : SingleTapeTM Symbol) in +@[grind =] +lemma Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg (tm : SingleTapeTM Symbol) (s : List Symbol) : (tm.initCfg s).spaceUsed = max 1 s.length := BiTape.spaceUsed_mk₁ s - Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 24
- Cslib.Turing.BiTape.instInhabitedCslib.Turing.BiTape.instInhabited
- Cslib.Turing.StackTape.empty_eq_nilCslib.Turing.StackTape.empty_eq_nil
- Cslib.Turing.BiTape.instEmptyCollectionCslib.Turing.BiTape.instEmptyCollection
- Cslib.Turing.StackTape.cons_none_nil_toListCslib.Turing.StackTape.cons_none_nil_toList
- Cslib.Turing.StackTape.instEmptyCollectionCslib.Turing.StackTape.instEmptyCollection
- Cslib.Turing.StackTape.instInhabitedCslib.Turing.StackTape.instInhabited
- Cslib.Turing.BiTape.empty_eq_nilCslib.Turing.BiTape.empty_eq_nil
- Cslib.Turing.StackTape.length_nilCslib.Turing.StackTape.length_nil
- Cslib.Turing.BiTape.spaceUsed_writeCslib.Turing.BiTape.spaceUsed_write
- Cslib.Turing.BiTape.moveLeft_moveRightCslib.Turing.BiTape.moveLeft_moveRight
- Cslib.Turing.SingleTapeTM.Cfg.spaceUsedThe space used by a configuration is the space used by its tape.
- Cslib.Turing.BiTape.moveRight_moveLeftCslib.Turing.BiTape.moveRight_moveLeft
- Cslib.Turing.StackTape.head_consCslib.Turing.StackTape.head_cons
- Cslib.Turing.StackTape.tail_consCslib.Turing.StackTape.tail_cons
- Cslib.Turing.StackTape.cons_some_toListCslib.Turing.StackTape.cons_some_toList
- Cslib.Turing.StackTape.cons_head_tailCslib.Turing.StackTape.cons_head_tail
- Cslib.Turing.SingleTapeTM.stepThe step function corresponding to a
SingleTapeTM. - Cslib.Turing.BiTapeA structure for bidirectionally-infinite Turing machine tapes that eventually take on blank
nonevalues - Cslib.Turing.BiTape.spaceUsed_mk₁Cslib.Turing.BiTape.spaceUsed_mk₁
- Cslib.Turing.StackTape.length_mapSomeCslib.Turing.StackTape.length_mapSome
- Cslib.Turing.StackTape.nil_toListCslib.Turing.StackTape.nil_toList
- Cslib.Turing.SingleTapeTMA single-tape Turing machine over the alphabet of
Option Symbol(wherenoneis the blankBiTapesymbol). - Cslib.Turing.SingleTapeTM.initCfgThe initial configuration corresponding to a list in the input alphabet. Note that the entries of the tape constructed by
BiTape.mk₁are… - Cslib.Turing.StackTapeAn infinite tape representation using a list of
Optionvalues, where the list is eventuallynone. Represented as a…
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Cslib Cslib.Turing Cslib.Turing.SingleTapeTM in open Relation in open Cslib.Turing.BiTape Cslib.Turing.StackTape in open _root_.Turing in variable {Symbol : Type} in variable [Inhabited Symbol] [Fintype Symbol] (tm : SingleTapeTM Symbol) in @[grind =] lemma Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg (tm : SingleTapeTM Symbol) (s : List Symbol) : (tm.initCfg s).spaceUsed = max 1 s.length := BiTape.spaceUsed_mk₁ s