Initial stacks lie in program support
ProvedPvsNP.initList_supportedEvery initialized input word uses only symbols from machineSymbols.
Status: Local proof checked; unpublished draft statement.
import Definitions.Def_PvsNPSupport
namespace PvsNP
theorem initList_supported (M : Turing.FinTM2) (w : List (M.Γ M.k₀)) :
SupportedStacks M (machineSymbols M) (Turing.initList M w).stk := by sorry
end PvsNPRead-back
What the Lean code literally says, in plain math · gpt-6-astra
For every machine and every finite word over its input alphabet , initialize the configuration with the main label, the initial control state, on stack , and the empty list on every other stack. Every tagged symbol in every stack of this initial configuration belongs to : , membership of in that initialized stack implies . The word may be empty and is not required to satisfy any separate input-encoding promise. Here is a TM2 machine with a finite type of stack indices and decidable equality on , designated input and output indices , stack-symbol types , a finite type of program labels with a main label, a finite type of control states with an initial state, a finite input alphabet , and a statement for each label . No finiteness of for other is assumed. A tagged symbol has and ; tags from different stacks remain distinct. For a statement , its set of syntactically possible pushed tagged symbols is recursively defined: a push onto with symbol function and continuation contributes ; a peek, pop, or control-state load contributes only its continuation’s set; a conditional branch contributes the union of both branch sets; a jump to a program label and a halt contribute the empty set. Thus both branch bodies and all control states are counted, regardless of reachability, while a jump does not recursively inspect its target. Put , including every input-alphabet symbol and all syntactically possible pushes from every labeled statement.