4.5 Unrestricted Grammars 193
Instruction Meaning
READ(&) read the next input integer into Ri
WRITE(Ri) write c( Ri) on the output tape
COPY(Ri, Rj) write c(R~) to Rj
ADD(Ri, Rj, R/c) write c(R~) + c(Rj) to Rk
SUB(& Y Rj > Rk) write c(R~) - c(Rj) to Rk
MULT(Ri, Rj, Rk) write c(R;). c(Rj) to Rk
DIv(Ri,Rj,Rk) write [c(Ri)/c(Rj)J to & (write 0 if c(Rj) = 0)
GOT0 (j) go to the instruction j
IF-THEN (Ri , j) if c(Ri) > 0 then go to the instruction j
Figure 4.17: Instructions of a RAM.
value 0, the output tape is “empty” (indicated by a special symbol, e.g.,
B), and the input tape contains a finite number of nonnegative integers
(n1, l l l > r&k), stored in cells 1 to k, and cell k + 1 is empty. The RAM
begins with instruction 1 and, after finishing each instruction i, it goes
to instruction i + 1 if instruction i is one of the first seven types, or it
goes to the instruction j as defined in instruction i if instruction i is one
of the last two types. The RAM halts when it reaches an instruction
k > n.
For any RAM M, we let L(M) = {(nl,... , nk) 1 M halts on in-
put (nl,-+k)}- We say M computes a function f : UF1 - Nk +
UT& Nk if, on input (nl,... , r&k), &! halts with outputs (ml,... , me) =
f(nly+k)*(a) Design a RAM that computes the function sort of Exercise 5(e)
of Section 4.3.
(b) Show th e e d t ai 1 s o a f multi-tape DTM that simulates the instruc-
tion ADD@, Rat R&) of a RAM.
(c) Show that every Turing-computable partial function f : N” + N,
as defined in Section 4.2, is computable by a RAM.
4.5 Unrestricted Grammars