Constant-overhead simulation of finite tape programs
ProvedExpandingCodes.Computation.TapeCompiler.compile_haltscoding-theorycomplexity-theoryexpanding-codes-polynomial-stretch
Let be a finite source program with registers, buffers and instruction labels. Let be any input, any oracle, and a natural number. If the source execution halts after instructions with binary output , its compiled canonical machine satisfies
The output uses the canonical bit-to-symbol encoding. This theorem supplies a uniform, constant-overhead bridge from finite source executions to the machine model used by the expanding-code mission.
Preamble
import Definitions.Def_ExpandingCodes_PolynomialStretch_BinaryRuntime set_option autoImplicit false open scoped Classical open NKtLB
Formal statement
theorem ExpandingCodes.Computation.TapeCompiler.compile_halts {R B L : ℕ} (P : ExpandingCodes.Computation.TapeProgram R B L) (O : Set (List Bool)) (inp : Inputs)
(t : ℕ) (hh : P.halted (P.run inp t)) :
(ExpandingCodes.Computation.TapeCompiler.compile P).HaltsWith O inp (1+2*t) (bitsSym (P.run inp t).output) := by sorry
Source
Algorithmic supporting lemma for Section 2 of Isaac M Hair and Amit Sahai, Expanding Codes with Polynomial Stretch; the explicit tape-machine implementation is formalized in ExpandingCodes.Computation.TapeCompiler. Supporting formal implementation contract, rather than a verbatim statement in the paper. Exact local source: ExpandingCodes/Computation/TapeCompiler.lean, declaration ExpandingCodes.Computation.TapeCompiler.compile_halts; source file SHA256 f440840078896ca879d015e964d8dbe8e7b88735222475fe194d758cacfe2170. The public construction is at https://prove2.me/missions/Expanding_Codes_with_Polynomial_Stretch.