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 : \mathbb{Z} \to \mathbb{R}$ vanishing on the negative cells (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 the support condition. The tape program keeps its registers in a fixed window of cells immediately to the left of its head, so the first register write overwrites the input cells $-1, \dots, -Z$; the simulation is therefore stated for inputs that are zero there, which includes the standard encoding encodeLP of a linear system (it occupies cells $0, \dots, mn+m+1$). Without such a condition a tape machine facing an input with live data in every cell has no scratch space, and a data-preserving simulation cannot even keep a loop counter.

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.