Real RAM to tape machine: quadratic-overhead compilation

This theorem says that the random-access model and the tape model of the mission are polynomially equivalent in the direction that matters for the goal: an algorithm written for the real pointer machine can be run on the tape machine with at most quadratic slowdown.

The assertion. For every program $R$ of the real pointer machine there is a tape program $P$ and a constant $K$ such that, for every input $x$ (a function $\mathbb{Z} \to \mathbb{R}$, used as the initial memory of $R$ and as the initial tape of $P$), every $T$ and every verdict $b$: if $R$ halts with $b$ within $T$ steps, then $P$ halts with $b$ within $K\,(T+1)^2$ steps.

Why quadratic suffices. Pointer registers of $R$ start at $0$ and change by at most one per step, apart from being set to one of the finitely many constants of the program; hence during a run of $T$ steps every pointer, and every accessed cell, lies within distance $T + K_0$ of the origin, where $K_0$ is the largest pointer constant. The tape program keeps the real registers and the pointer registers (as reals) in a fixed window of cells next to its head, together with the current position of its head; a memory access load or store is simulated by walking the head to the pointer's cell, which costs a number of shifts proportional to the distance, each shift accompanied by a fixed number of copies that slide the register window along without destroying the tape contents. Every other instruction is simulated by a constant number of tape instructions. The total is $O(T \cdot (T + K_0))$, which is $K(T+1)^2$ for a suitable $K$.

Purpose. Combined with a strongly polynomial algorithm in the random-access model (SmaleNinth.smale_ninth_real_ram), this theorem yields the goal theorem of the mission; conversely it shows that the choice of the tape machine as the mission's model costs at most a squaring of the running time relative to the model in which algorithms are normally written.

Retired. This formulation quantifies over inputs with arbitrary contents on the negative cells, where the simulating tape program must place its register window; on a tape whose every cell carries live input the program has no scratch space, so the statement as written is not the intended one. It is replaced by SmaleNinth.ram_to_bss_quadratic_nonneg, which assumes the input vanishes on negative cells (as encodeLP does) and suffices for the reduction of the goal theorem.