Polynomial simulation of stack programs with physical word output
ProvedAPSCounting893.Main.stack_function_polynomial_simulationLet be a language and a total function on binary words. Fix one finite stack program, a designated stop state, and an output register. Each instruction pops or pushes one bit, branches on a stack, or queries the word written in a register. Suppose the stop state halts with answer true, and there are constants such that on every input the program reaches that state, before halting, within stack steps with in the selected register. Then
The conclusion uses an ordinary finite oracle machine with physical tapes: the returned word is read from its charged output tape. The finite transition table, time polynomial and selected register are independent of the input. This simulation supplies word-valued subroutines for the dimension and coefficient algorithms in Section 6.
import Definitions.Def_APSCounting893_Main_OracleProofPrimitives set_option autoImplicit false open APSCounting893.Main
theorem APSCounting893.Main.stack_function_polynomial_simulation {Q : Type} [Fintype Q] {r : ℕ}
(P : StackProgram Q r) (A : Language) (f : Word → Word)
(stop : Q) (src : Fin (r+2)) (hstop : P.transition stop=.halt true) (c d : ℕ)
(h : ∀ x : Word,∃ T≤polyBound c d x.length,
(P.run A x [] T).state=stop ∧ (P.run A x [] T).answer=none ∧ (P.run A x [] T).regs src=f x) :
FunctionInPWithOracle A f := by sorry