A shared polynomial WordRAM-to-TM simulation backend exists
ProvedWordRAM.Complexity.polynomial_backend_existsThere exists a backend supplying both function-output and verifier-verdict simulation certificates for every uniform WordRAM program in either the restricted or multiplication model and every polynomial RAM fuel budget.
Each certificate selects its fixed legal Cook–Levin machine, number of tapes, alphabet, and polynomial TM step bound before all input strings are quantified. It preserves every successful RAM run with a valid output or Boolean verdict under the specified standard bit encodings. Loading, bounded-word operations, and output serialization fit within the TM bound. Words use the fixed program’s canonical logarithmic width; native constants are absent.
The backend is asserted to exist without any simulation assumption. This does not assert an executable compiler, reverse polynomial simulation, an exact overhead exponent, or behavior on unsuccessful or malformed-output RAM runs. Together with the existing transfer lemmas, it lets RAM algorithm proofs establish the original Cook–Levin reduction and NP-verifier obligations.
import Definitions.Def_WordRAM_Complexity_Simulation set_option autoImplicit false
namespace WordRAM.Complexity theorem polynomial_backend_exists : Nonempty PolynomialBackend := by sorry end WordRAM.Complexity
Read-back
What the Lean code literally says, in plain math · GPT-6 (independent Codex sub-agent)
There exists an object containing two selection functions with the following domains and outputs. The first, for every model , every algorithm of that model, and every , returns natural numbers and data for a legal Turing machine, together with the assertion that for all finite bit strings , if the RAM run on with fuel has halted flag true and valid output , then after exactly Turing steps on the state equals and its bounded decoded output is . The second, for every independently, returns its own natural numbers and legal-machine data together with the assertion that for all finite bit strings and Booleans , if the RAM run on with fuel has halted flag true and cell has unsigned value for false or for true , then after exactly Turing steps on the state equals and cell one of tape contains symbol for false or for true . The model is either restricted or multiplication. An algorithm consists of a fixed finite instruction list and arbitrary natural numbers ; at total input length its word width is . Its memory is a function from all natural addresses to -bit words. The fixed list permits copying, addition and subtraction modulo , zero-filling left and right shifts by an unsigned word value, bitwise AND, OR and NOT, unconditional jumps, branches testing unsigned equality or order ( or ), and explicit halt; multiplication modulo is additionally available precisely in the multiplication model. Literal operands are natural numbers reduced modulo , and addresses are either fixed natural addresses or the unsigned word stored at a fixed pointer address; fixed addresses and jump targets have no well-formedness restriction. There are no native-constant instructions. For bit strings , the initial RAM memory stores at addresses , respectively, then the bits of followed by those of from address , and zero elsewhere, with stored values reduced to the chosen word width. Initially the program counter and tick count are zero and the halted flag is false. One RAM instruction uses operand values and destination addresses from the old memory, increases the tick count by one, and advances the program counter by one unless a jump or branch changes it; halt sets the halted flag. A run with fuel performs at most instructions, stopping without further change when already halted or when the program counter indexes no instruction; an invalid fetch does not set the halted flag. A RAM state has output exactly when, writing and for the unsigned contents of cells and , one has , every cell for holds the unsigned value or , and is the resulting length- bit list. In particular yields the empty output. Here a legal machine is a finite list of transition functions with natural numbers of tapes and alphabet symbols: for every command and every list of natural symbols, the command returns exactly write-and-move actions and a next state at most ; if all read symbols are below , all written symbols are below ; and the first tape always has its scanned symbol rewritten unchanged, even on symbol lists outside that alphabet. Each tape has natural-number cells and a natural head position; a step reads all heads, applies the command indexed by the current state, writes at the old head positions and moves each head left, right or not at all, with a left move at zero staying at zero. States at least are fixed by further steps. The initial Turing configuration has state zero, all heads at cell zero, symbol at cell zero of every tape, the first input string on tape zero and the second on tape one starting at cell one, and symbol elsewhere; input bits false and true are encoded by symbols and , respectively. For the first selection function, use and . The Turing output is read from cell one of tape : symbols decode to false,true, reading stops at the first other symbol, and at most cells are inspected. Equality to concerns this bounded reading; it imposes no condition on later cells, and if the reading reaches its cap it requires no following non-bit delimiter. For the second selection function, and only the specified verdict cell is constrained. Every selected machine and pair is fixed across the inputs for its particular ; neither the two selections nor selections for different arguments must agree, and a single common machine or common polynomial for all algorithms is not required. All input and output strings may be empty, and all polynomial coefficients and degrees, including , may be zero; at total length zero the budgets are and . If , the initially false halted flag makes every preservation premise false. Runs that do not halt or stop on an invalid fetch impose no preservation condition; the first selection also imposes none for invalid RAM bit outputs, and the second imposes none for RAM verdict words outside . No hypothesis requires the algorithms to halt on all inputs, and no bound on witness length relative to the first input is imposed. Empty RAM code and empty Turing command lists are allowed. The assertion is existence of these data-returning functions and their conditional guarantees; it gives no uniqueness, correspondence of intermediate states, converse preservation implication, or requirement that the selections be computable or implemented by an executable compiler.
Confirmed by the mission captain (proposal self-audit).