Proofs: RAM and Turing machine equivalence

A multitape Turing machine simulates a logarithmic-cost RAM in time O(t^2) full

This proof shows: ram-by-tm.

Statement. Let $P$ be a RAM program with the instructions LOAD, STORE, ADD, SUB, READ, JUMP, JZERO, JEOF, HALT, as on the random-access machine page. Let $P$ decide $L \subseteq \{0,1\}^*$ in logarithmic-cost time $t(n)$: on every input word $w$ of length $n$, given as $n$ integers in $\{0,1\}$, $P$ halts with logarithmic cost at most $t(n)$, and with $R_0 = 1$ if $w \in L$ and $R_0 = 0$ if $w \notin L$. Then there is a deterministic 5-tape Turing machine $M_P$ that decides $L$ in $O(t(n)^2)$ steps. The constant depends on $P$ only.

Setup. Fix an input $w$ of length $n$ and the run of $P$ on $w$. Let the run execute $N$ instructions, numbered $1, \ldots, N$, and let $c_s$ be the logarithmic cost of instruction $s$. Then $C = \sum_s c_s \le t(n)$. Every cost $c_s$ is at least 1, so $N \le C$. We write $\ell(x)$ for the bit length, with $\ell(0) = 1$. Let $K_P$ be the largest length of a number that occurs in the text of $P$ (a constant, a register number or a jump target). Every constant $K$ below depends on $P$ only.

Encoding. Numbers are written in binary on the tapes with the least significant bit first and with no leading zeros, and $0$ is the string 0. A number on a tape is followed by a blank or by a separator.

Tapes of $M_P$.

• Tape 1 holds the input $w$. Its head moves only to the right, and it is on the next unread symbol.
• Tape 2, the memory tape, holds a list of records #a:v, where $a$ and $v$ are numbers. The list stands in the first cells, and the cells after it are blank. The addresses of different records are different. A register $R_a$ with $a \ge 1$ that has no record has the value $0$. We write $m$ for the length of the list.
• Tape 3 holds the accumulator $R_0$.
• Tapes 4 and 5 are work tapes. Tape 4 holds an address, and tape 5 holds a value or a copy.

The program counter is in the finite control. Because $P$ has finitely many instructions, the control has finitely many states.

Invariant $J_s$. Before instruction $s$ of the run, the control is at the instruction that $P$ executes as instruction $s$. Tape 3 holds the value of $R_0$. Tape 2 holds exactly one record #a:v for each register $R_a$ with $a \ge 1$ that a STORE has written in the instructions $1, \ldots, s-1$, with its current value $v$. Tapes 4 and 5 are blank. Tape 1 has read exactly as many symbols as the instructions READ before $s$. All heads except head 1 are on cell 0.

Step 1: the length of the memory tape. Let $m_s$ be the length of the list before instruction $s$. We show $m_s \le 2 \sum_{r<s} c_r$. A record #a:v has length $\ell(a) + \ell(v) + 2$. It is in the list because of the last STORE $r < s$ that wrote the register $R_a$, and at that time $R_a$ received the value $v$ from $R_0$. By the cost table, the cost of STORE i is $\ell(c(0)) + \ell(i)$, and the cost of STORE *i is $\ell(c(0)) + \ell(i) + \ell(c(i))$. In both cases $c_r \ge \ell(v) + \ell(a)$, and also $c_r \ge 2$. So the record has length at most $c_r + 2 \le 2 c_r$. Different records belong to different instructions STORE, since one STORE writes one register. So the lengths add up to at most $2 \sum_{r<s} c_r \le 2t(n)$.

Step 2: the subroutines. All subroutines start and end with the heads of tapes 2, 4 and 5 on cell 0.

• FIND. Tape 4 holds a number $a$. The machine moves head 2 over the list. For each record it compares $a$ with the address, symbol by symbol, with head 4 and head 2 moving together, until the symbols differ or one string ends. If both strings end together, the record matches. Then it moves head 4 back to cell 0 and head 2 to the end of the record. For one record this takes $O(\text{the length of the record}+1)$ steps, since the comparison makes at most as many steps as the shorter address has symbols plus one, and the rewind of head 4 takes as many. So FIND takes $O(m + 1)$ steps. It stops at the first match. It ends in one of two states: found, with head 2 on the : of the record, or not found, with head 2 on the first blank after the list.
• LOOKUP. FIND, then copy the value after the : to tape 5 if found, or write 0 on tape 5 if not found. The result on tape 5 is the value of $R_a$. LOOKUP takes $O(m + \ell(v))$ steps where $v$ is the value, and $\ell(v) \le m$ if found. So it takes $O(m+1)$ steps. If $a = 0$, the address names the accumulator (a program can reach $R_0$ only through an indirect operand whose register holds $0$): LOOKUP copies tape 3 to tape 5 and does not use the list.
• UPDATE. Tape 4 holds $a$ and tape 3 holds $v$. If $a = 0$, do nothing, since STORE then copies $R_0$ to $R_0$. Else FIND. If found, copy the part of the list after the old value to tape 5 and blank it on tape 2, write $v$ after the :, copy the part back from tape 5 after $v$, and blank tape 5. This takes $O(m + \ell(v))$ steps. If not found, write #, $a$, : and $v$ at the end of the list, which takes $O(\ell(a) + \ell(v))$ steps. Then rewind. The total is $O(m + \ell(a) + \ell(v) + 1)$ steps.
• ARITH. Tapes 3 and 5 hold $x$ and $v$. Add: scan both from the left with a carry, and write the sum on tape 3. Subtract: scan with a borrow; if a borrow remains at the end, write 0, else erase the leading zeros of the result. Each takes $O(\ell(x) + \ell(v) + 1)$ steps.

Step 3: one instruction. Assume $J_s$. Let $\lambda_s$ be the length of $R_0$ before instruction $s$. We show that the machine executes instruction $s$ in at most $K(m_s + c_s + \lambda_s)$ steps if $s$ is a LOAD or a READ, in at most $K(m_s + c_s)$ steps if $s$ is a STORE, ADD, SUB or JZERO, and in $O(1)$ steps if $s$ is a JUMP, JEOF or HALT, and that $J_{s+1}$ holds after it. Only LOAD and READ pay $\lambda_s$ outside $c_s$. In the other instructions that read $R_0$, $\lambda_s \le c_s$ by the cost table. Operands: for the operand $=c$ the machine writes $c$ on tape 5 in $O(K_P)$ steps. For the operand $i$ it writes $i$ on tape 4, which takes $O(K_P)$ steps, and it does LOOKUP, which leaves $c(i)$ on tape 5. For the operand $*i$ it writes $i$ on tape 4 and does LOOKUP, so tape 5 holds $c(i)$. It then copies this number to tape 4, which takes $O(\ell(c(i)))$ steps, blanks tape 5 in $O(\ell(c(i)))$ steps, and does LOOKUP again, so tape 5 holds $c(c(i))$. Each of these takes $O(m_s + K_P + \ell(c(i)))$ steps, and each of the lengths that occur is part of the cost $c_s$ of the instruction.

• LOAD X: get the operand on tape 5 as above, and copy tape 5 to tape 3, after erasing the old content. This takes $O(\lambda_s + \ell(v))$ more steps, and $\ell(v) \le c_s$.
• STORE i, STORE *i: put the address on tape 4 (for *i, by LOOKUP of $i$, a copy to tape 4 and the blanking of tape 5, which cost $O(\ell(a))$ steps), so that tape 5 is blank, and do UPDATE with $v$ on tape 3. The register $R_a$ gets $R_0$. The records of the other registers do not change. The cost is $O(m_s + \ell(a) + \ell(v) + K_P)$, and $\ell(v) + \ell(a) \le c_s$.
• ADD X, SUB X: get the operand on tape 5, and do ARITH. The cost is $O(m_s + \ell(R_0) + \ell(v))$, and $c_s \ge \ell(R_0) + \ell(v)$. The result is $R_0 + v$ or $\max(R_0 - v, 0)$, as ARITH computes.
• READ: erase tape 3, and write the symbol of tape 1 under head 1 on tape 3 (the number is 0 or 1), and move head 1 right. If head 1 reads a blank, no input is left, and the machine writes 0 and does not move head 1. This takes $O(\lambda_s + 1)$ steps.
• JUMP k: set the control to $k$. JZERO k: read tape 3 and jump if it is 0. JEOF k: jump if head 1 reads a blank. HALT: accept if tape 3 holds 1, else reject. Each takes $O(1)$ steps.

After each instruction, the machine rewinds the heads to cell 0 (not head 1). This costs at most the lengths already counted. The effects are those of the RAM instruction, so $J_{s+1}$ holds. For HALT the answer is the value of $R_0$, so $M_P$ accepts if and only if $P$ halts with $R_0 = 1$.

Step 4: the length of the accumulator. In the list of Step 3, only LOAD and READ pay for the old length $\lambda_s$ outside $c_s$. In ADD and SUB the length $\lambda_s = \ell(R_0)$ is a part of $c_s$. Let $r$ be the last instruction before $s$ that set $R_0$ (LOAD, ADD, SUB or READ). Then $\lambda_s \le c_r$: for LOAD X the new value is the value of $X$, and its length is a part of $c_r$; for ADD the new length is at most $\max(\ell(R_0), \ell(v)) + 1 \le \ell(R_0) + \ell(v) \le c_r$, where $R_0$ is the old value; for SUB it is at most the length of the old $R_0$, which is a part of $c_r$; for READ it is $1 \le c_r$. If no instruction has set $R_0$, then $\lambda_s = 1$. A setter $r$ is the last setter before at most one later instruction $s$, namely the next setter. So $\sum_s \lambda_s \le 1 + \sum_r c_r \le t(n) + 1$, where the sum is over the instructions LOAD and READ.

Step 5: the total. The first step of $M_P$ writes 0 on tape 3, and this makes $J_1$ true. By Step 3, Step 1 and Step 4, the total time of the simulation is at most

$$ K \sum_{s=1}^{N} (m_s + c_s + \lambda_s) + K' \le K\bigl( N \cdot 2t(n) + t(n) + t(n) + 1 \bigr) + K'. $$

Here the sum of the $\lambda_s$ is over the instructions LOAD and READ, and the other terms are bounded by Step 1 (so $m_s \le 2t(n)$) and by $\sum_s c_s \le t(n)$. Since $N \le t(n)$ and $t(n) \ge 1$, this is $O(t(n)^2)$. By the invariant at the halting instruction, $M_P$ decides $L$. $\blacksquare$

Remark. The bound uses that every instruction costs at least 1, so that the number of instructions is at most the time. It also uses that a STORE costs at least the length of its record, so that the list is as short as the time. These two facts are the reason for the logarithmic cost rule. With the unit rule and an instruction MULT, repeated squaring and a STORE make a record of length $2^{\Omega(t)}$, and the proof fails.

A RAM simulates a multitape Turing machine in logarithmic-cost time O(T log T) full

This proof shows: tm-by-ram.

Statement. Let $M$ be a deterministic $k$-tape Turing machine, with the tape alphabet $\Gamma$ of $g$ symbols and the input alphabet $\{0,1\}$, that decides $L \subseteq \{0,1\}^*$ and halts within $T(n)$ steps on every input of length $n$, where $T(n) \ge \max(n, 2)$. Then there is a RAM program $P_M$ (with the instructions of the random-access machine page, no multiplication) that decides $L$ in unit-cost time $O(T(n))$ and in logarithmic-cost time $O(T(n) \log T(n))$. The constants depend on $M$ only.

Setup. Write $\Gamma = \{\gamma_0, \ldots, \gamma_{g-1}\}$ with $\gamma_0 = \sqcup$, $\gamma_1 = 0$ and $\gamma_2 = 1$, and use the index $j$ as the code of $\gamma_j$. A blank cell has code $0$, which is the value of a register that was never written. Let $B = k + 2$. The registers are used like this.

• $R_i$ for $1 \le i \le k$ holds the address of the register that stores the cell scanned by head $i$.
• $R_{k+1}$ is a pointer $p$ for the copy of the input.
• The cell $c \ge 0$ of tape $i$ is stored in the register with the address $B + kc + (i-1)$. These addresses are at least $B > k + 1$ and are all different, for different pairs $(i, c)$, since $(i - 1)$ is the remainder of the offset modulo $k$ and $c$ is the quotient.
• $R_0$ is the accumulator.

The program has two parts. Part I copies the input into the cells of tape 1.

      LOAD =B
      STORE k+1               ; p = B
loop  JEOF done
      READ                    ; acc = w_c, 0 or 1
      ADD =1                  ; code of the bit: 1 for 0, 2 for 1
      STORE *(k+1)            ; the cell gets the code
      LOAD k+1
      ADD =k
      STORE k+1               ; p = p + k
      JUMP loop
done  LOAD =B+i-1             ; for each i = 1..k
      STORE i                 ; head i on cell 0
      JUMP S(q0)

Part II has a block $S(q)$ for each non-halting state $q$ of $M$ and a block for each of accept and reject. The block $S(\text{accept})$ is LOAD =1, HALT. The block $S(\text{reject})$ is LOAD =0, HALT. The block $S(q)$ is a decision tree of depth $k$ that finds the scanned symbols. At a node for tape $i$, with the symbols of the tapes $1, \ldots, i-1$ already fixed by the path, it runs the tests for $a = 0, 1, \ldots, g-2$ in this order. The test for $a$ is

      LOAD *i
      SUB =a
      JZERO (the node for tape i+1 in which the symbol of tape i is a)

and if all $g - 1$ tests fail, the code goes on to the node in which the symbol of tape $i$ is $g - 1$. The tree has $g^k$ leaves, one for each tuple $(a_1, \ldots, a_k)$ of codes, and each leaf is a separate piece of code. In the leaf $(q; a_1, \ldots, a_k)$, let $\delta(q, \gamma_{a_1}, \ldots, \gamma_{a_k}) = (q', \gamma_{b_1}, \ldots, \gamma_{b_k}, D_1, \ldots, D_k)$. The leaf has these instructions, for $i = 1, \ldots, k$ in turn.

• LOAD =b_i, then STORE *i: write the symbol.
• If $D_i = R$: LOAD i, ADD =k, STORE i.
• If $D_i = L$: LOAD i, SUB =B+i-1, JZERO skip_i, LOAD i, SUB =k, STORE i, and then the label skip_i.
• If $D_i = S$: nothing.

The leaf ends with JUMP S(q'). The program has $O(g^k)$ instructions, which is a constant.

Step 1: the test finds the symbol. Let $x = R_{R_i}$, the code of the scanned symbol, with $0 \le x \le g-1$. The test for $a$ computes $\max(x - a, 0)$, and the jump is taken if and only if $x \le a$. The tests run for $a = 0, 1, \ldots$ in this order. If $x = a_0$, then the tests for $a < a_0$ fail, since $x > a$. The test for $a = a_0$ jumps. So the first jump is at $a = x$. If no test jumps, then $x > g - 2$, so $x = g - 1$. Hence the leaf that the block reaches is the leaf of the true symbols. (After each test the accumulator is overwritten by the next LOAD *i, so the tests do not interact.)

Step 2: the left move. The cell $0$ of tape $i$ has the address $B + i - 1$, and every cell has an address of at least this value. So SUB =B+i-1 gives $0$ if and only if $R_i \le B + i - 1$, that is, if and only if head $i$ is on cell $0$. In that case the move $L$ keeps the head in place, as in the machine, since JZERO skips the subtraction. Else SUB =k moves the address of head $i$ one cell to the left (the address of cell $c-1$ is that of cell $c$ minus $k$).

Invariant $I_j$. After $j$ steps of $M$ (and after Part I for $j = 0$), the control is at the beginning of $S(q_j)$, where $q_j$ is the state of $M$ after $j$ steps. For each $i$ the register $R_i$ holds the address of the cell scanned by head $i$. For each $i$ and $c$ the register with the address $B + kc + (i-1)$ holds the code of the symbol in cell $c$ of tape $i$.

Proof of $I_0$. The registers other than those of tape 1 are $0$, which is the code of the blank, and tape $i \ge 2$ is blank at the start. Part I stores the codes of the input symbols at the addresses $B + kc$ for $c = 0, 1, \ldots, n-1$, since $p$ starts at $B$ and grows by $k$ at each pass, and JEOF done ends the loop after $n$ passes. The cells $c \ge n$ of tape 1 are blank and the registers are $0$. The heads start on cell $0$, whose address is $B + i - 1$.

Proof of $I_{j} \Rightarrow I_{j+1}$. Assume $I_j$ and $q_j$ non-halting. By Step 1 the block reaches the leaf of the true tuple of symbols. In the leaf, for each $i$ the instruction pair LOAD =b_i, STORE *i writes the symbol $b_i$ into the register of the scanned cell, and then the move updates $R_i$ as in Step 2. Different tapes use different registers, so the order in which the tapes are handled does not matter. The leaf jumps to $S(q_{j+1})$. This is the configuration of $M$ after step $j+1$. If $q_j$ is accept, $S(q_j)$ halts with $R_0 = 1$, and if reject with $R_0 = 0$. $\blacksquare$ (of the invariant)

Step 3: the cost. Let $M$ halt after $T' \le T(n)$ steps on the input. A head moves at most one cell in a step, so during the run, every scanned cell has an index of at most $\max(n, T')\le T(n)$ (the input has length $n \le T(n)$). So every address and every register value that occurs is at most $B + k(T(n)+1) + k$, and every constant in the program is bounded by a constant. An instruction costs at most four lengths (by the cost table), each at most $\lg(B + k(T(n) + 2)) + 1 = O(\log T(n))$, since $T(n) \ge 2$. The number of instructions executed is as follows.

• Part I executes $8n + O(1)$ instructions with $n$ the length of the input, since each pass of the loop executes 8 instructions and the end has $2k + 1$.
• Each step of $M$ executes at most $3k(g-1) + 8k + 1$ instructions: at most $3(g-1)$ for each tape in the tests, at most $8$ for each tape in the leaf (the longest case is the move $L$ with 6 instructions plus 2 for the write), and 1 for the jump at the end of the leaf.
• The last block has 2 instructions.

So the number of instructions is at most $8n + K_1 T' + K_2 \le K T(n)$, using $n \le T(n)$. This is the unit-cost time $O(T(n))$. Multiplying by the cost per instruction, the logarithmic-cost time is $O(T(n) \log T(n))$. By the invariant, $P_M$ halts with $R_0 = 1$ exactly when $M$ accepts. $\blacksquare$