Cslib.Turing.StackTape.cons_none_nil_toList
theoremverifiedformalizationimported Lean
Cslib.Turing.StackTape.cons_none_nil_toList
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Cslib Cslib.Turing Cslib.Turing.StackTape in attribute [local grind! .] StackTape.toList_getLast?_ne_some_none in variable {Symbol : Type*} in @[simp, grind =] lemma Cslib.Turing.StackTape.cons_none_nil_toList : (cons none (nil : StackTape Symbol)).toList = []
- Formalizes
- CSLib, `Cslib.Turing.StackTape.cons_none_nil_toList`
- Lean proof
- By Bolton Bailey, 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.StackTape.cons_none_nil_toList← Cslib.Turing.StackTape.cons_none_nil_toList (Cslib/Foundations/Data/StackTape.lean:87): adapted
What was changed in
Cslib.Turing.StackTape.cons_none_nil_toList--- Cslib/Foundations/Data/StackTape.lean:87 (Cslib.Turing.StackTape.cons_none_nil_toList) +++ as compiled here @@ -1,3 +1,8 @@ -@[simp, scoped grind =] -lemma cons_none_nil_toList : (cons none (nil : StackTape Symbol)).toList = [] := by +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +open Cslib Cslib.Turing Cslib.Turing.StackTape in +attribute [local grind! .] StackTape.toList_getLast?_ne_some_none in +variable {Symbol : Type*} in +@[simp, grind =] +lemma Cslib.Turing.StackTape.cons_none_nil_toList : (cons none (nil : StackTape Symbol)).toList = [] := by grind only [nil, cons] - Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- Cslib.Turing.StackTape.empty_eq_nilCslib.Turing.StackTape.empty_eq_nil
- Cslib.Turing.StackTape.instEmptyCollectionCslib.Turing.StackTape.instEmptyCollection
- Cslib.Turing.StackTape.instInhabitedCslib.Turing.StackTape.instInhabited
- Cslib.Turing.StackTape.nilThe empty
StackTape - Cslib.Turing.StackTape.consPrepend an
Optionto theStackTape - Cslib.Turing.StackTape.nil_toListCslib.Turing.StackTape.nil_toList
- Cslib.Turing.StackTapeAn infinite tape representation using a list of
Optionvalues, where the list is eventuallynone. Represented as a…
- Used by 57
- Cslib.Turing.StackTape.lengthThe length of the
StackTapeis the number of elements up to the last non-noneelement - Cslib.Turing.SingleTapeTM.TransitionRelationThe
TransitionRelationcorresponding to aSingleTapeTM Symbolis defined by thestepfunction, which maps a configuration to its… - Cslib.Turing.SingleTapeTM.haltCfgThe final configuration corresponding to a list in the output alphabet. (We demand that the head halts at the leftmost position of the…
- Cslib.Turing.SingleTapeTM.initialCfgThe initial configuration for the composed machine, with the first machine starting.
- Cslib.Turing.StackTape.length_cons_noneCslib.Turing.StackTape.length_cons_none
- Cslib.Turing.BiTape.instInhabitedCslib.Turing.BiTape.instInhabited
- Cslib.Turing.SingleTapeTM.instInhabitedStateCslib.Turing.SingleTapeTM.instInhabitedState
- Cslib.Turing.BiTape.spaceUsedThe space used by a
BiTapeis the number of symbols between and including the head, and leftmost and rightmost non-blank symbols on the… - Cslib.Turing.SingleTapeTM.map_toCompCfg_right_stepThe right converting function commutes with steps of the machines.
- Cslib.Turing.BiTape.optionMoveOptionally perform a
move, or do nothing ifnone. - Cslib.Turing.SingleTapeTM.compComputer_q₀_eqCslib.Turing.SingleTapeTM.compComputer_q₀_eq
- Cslib.Turing.BiTape.instEmptyCollectionCslib.Turing.BiTape.instEmptyCollection
- Cslib.Turing.SingleTapeTM.finalCfgThe final configuration for the composed machine, after the second machine halts.
- Cslib.Turing.StackTape.eq_iffCslib.Turing.StackTape.eq_iff
- Cslib.Turing.SingleTapeTM.TimeComputableA Turing machine + a time function + a proof it outputs
fin at mosttime(input.length)steps. - Cslib.Turing.SingleTapeTM.PolyTimeComputable.idA proof that the identity map on Symbol is computable in polytime.
- Cslib.Turing.BiTape.empty_eq_nilCslib.Turing.BiTape.empty_eq_nil
- Cslib.Turing.SingleTapeTM.OutputsWithinTimeA proof of
tmoutputtingl'on inputlin at mostmsteps. - Cslib.Turing.StackTape.length_nilCslib.Turing.StackTape.length_nil
- Cslib.Turing.BiTape.spaceUsed_writeCslib.Turing.BiTape.spaceUsed_write
- Cslib.Turing.SingleTapeTM.comp_right_relatesWithinStepsSimulation for the second phase of the composed computer. When the second machine runs from start to halt, the composed machine runs from…
- Cslib.Turing.BiTape.moveLeft_moveRightCslib.Turing.BiTape.moveLeft_moveRight
- Cslib.Turing.SingleTapeTM.PolyTimeComputableA Turing machine + a polynomial time function + a proof it outputs
fin at mosttime(input.length)steps. - Cslib.Turing.StackTape.tailRemove the first element of the
StackTape, returning the rest - 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.SingleTapeTM.toCompCfg_leftConvert a
Cfgover the first input machine to a config over the composed machine. Note it may transition to the start state of the… - Cslib.Turing.StackTape.tail_consCslib.Turing.StackTape.tail_cons
- Cslib.Turing.SingleTapeTM.instFintypeStateCslib.Turing.SingleTapeTM.instFintypeState
- 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.BiTape.mk₁Given a
ListofSymbols, construct aBiTapeby mapping the list tosomeelements and laying them out to the right side, with the… - Cslib.Turing.SingleTapeTM.compComputerA Turing machine computing the composition of two other Turing machines. If f and g are computed by Turing machines
tm1andtm2then… - Cslib.Turing.SingleTapeTM.comp_left_relatesWithinStepsSimulation for the first phase of the composed computer. When the first machine runs from start to halt, the composed machine runs from…
- Cslib.Turing.BiTapeA structure for bidirectionally-infinite Turing machine tapes that eventually take on blank
nonevalues - Cslib.Turing.BiTape.moveLeftMove the head left by shifting the left StackTape under the head.
- Cslib.Turing.SingleTapeTM.idComputerA Turing machine computing the identity.
- Cslib.Turing.BiTape.moveRightMove the head right by shifting the right StackTape under the head.
- Cslib.Turing.BiTape.moveMove the head to the left or right, shifting the tape underneath it.
- Cslib.Turing.SingleTapeTM.intermediateCfgThe intermediate configuration for the composed machine, after the first machine halts and the second machine starts.
- Cslib.Turing.BiTape.spaceUsed_mk₁Cslib.Turing.BiTape.spaceUsed_mk₁
- Cslib.Turing.StackTape.length_mapSomeCslib.Turing.StackTape.length_mapSome
- Cslib.Turing.StackTape.headGet the first element of the
StackTape. - Cslib.Turing.SingleTapeTMA single-tape Turing machine over the alphabet of
Option Symbol(wherenoneis the blankBiTapesymbol). - Cslib.Turing.SingleTapeTM.toCompCfg_rightConvert a
Cfgover the second input machine to a config over the composed machine - Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfgCslib.Turing.SingleTapeTM.Cfg.spaceUsed_initCfg
- Cslib.Turing.StackTape.length_cons_someCslib.Turing.StackTape.length_cons_some
- Cslib.Turing.StackTape.mapSomeCreate a
StackTapefrom a list by mapping all elements tosome - Cslib.Turing.SingleTapeTM.OutputsA proof of
tmoutputtingl'on inputl. - 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.SingleTapeTM.CfgThe configurations of a Turing machine consist of: an
Optional state (or none for the halting state), and aBiTaperepresenting the… - Cslib.Turing.BiTape.nilThe empty
BiTape - Cslib.Turing.SingleTapeTM.map_toCompCfg_left_stepThe left converting function commutes with steps of the machines.
- Cslib.Turing.SingleTapeTM.Cfg.spaceUsed_haltCfgCslib.Turing.SingleTapeTM.Cfg.spaceUsed_haltCfg
- Cslib.Turing.SingleTapeTM.TimeComputable.idThe identity map on Symbol is computable in constant time.
- Cslib.Turing.StackTape.lengthThe length of the
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Cslib Cslib.Turing Cslib.Turing.StackTape inattribute [local grind! .] StackTape.toList_getLast?_ne_some_none invariable {Symbol : Type*} in@[simp, grind =]lemma Cslib.Turing.StackTape.cons_none_nil_toList : (cons none (nil : StackTape Symbol)).toList = [] := by grind only [nil, cons]