RAM/register computation and Turing computation agree

Let $M$ be a deterministic one-tape Turing machine. A RAM/register program can simulate $M$ by storing the current state and head position in distinguished registers and storing the finitely many nonblank tape cells in addressed memory entries. One program macro reads the currently addressed tape symbol, consults the finite transition table of $M$, updates that symbol and the control registers, and increments or decrements the stored head position according to the chosen transition.

Conversely, let $P$ be a RAM/register program. Build a deterministic multitape Turing machine $N_P$ whose work tapes store the program counter, the finitely many currently nonzero memory entries as a sorted list of address-value pairs, and scratch data for arithmetic and list maintenance. Each instruction type from [L1] is implemented by a finite Turing-machine subroutine: copy and arithmetic operate on binary numerals on work tapes, indirect addressing searches the address-value list, and zero entries are inserted or deleted so that the stored list remains finite.

Induction on the number of simulated steps shows that the RAM/register program from step 1.1 reproduces the full computation of $M$ on every binary input, including acceptance, rejection, divergence, and final output. Hence every Turing-recognizable language and every Turing-computable partial function is RAM/register realizable.

Again by induction on computation length, the multitape machine $N_P$ from step 1.2 reproduces exactly the accept, reject, divergence, and output behavior of $P$ on the standard input layout.

By [L4], $N_P$ has an equivalent deterministic one-tape simulation. Combining this with steps 2.1 and 2.2, the RAM/register and deterministic Turing-machine models recognize the same languages in the sense of [L2] and compute the same partial functions in the sense of [L3].