Machines with Memory - Models of Computation: Exploring the Power of Computing - page 114

As indicated above, with large enough words each of the above assembly-language instruc-
tions can be realized with a few instructions from the instruction set of the CPU designed in
Section 3.10 . It is also true that each of these CPU instructions can be implemented by a
fixed number of instructions in the above assembly language. That is, with sufficiently long
memory words in the CPU and random-access memory, the two languages allow the same
computations with about the same use of time and space.
However, the above assembly-language instructions are richer than is absolutely essential
to perform all computations. In fact with just five assembly-language instructions, namely
INC, DEC, CONTINUE, R j JMP + N i ,andR j JMP N i , all the other instructions can be

−

realized. (See Problem 3.21 .)

3.4.4 Universality of the Unbounded-Memory RAM
The unbounded-memory RAM is universal in two senses. First, it can simulate any finite-
state machine including another random-access machine, and second, it can execute any RAM
program.

DEFINITION 3.4.1 Amachine M is universal for a class of machines C if every machine in C can
be simulated by M . (A stronger definition requiring that M also be in C is used in Section 3.8 .)

C

of finite-state machines. We show
that in O ( T ) steps and with constant storage capacity S the RAM can simulate T steps of any
other FSM. Since any random-access machine that uses a bounded amount of memory can be
described by a logic circuit such as the one defined in Section 3.10 , it can also be simulated by
the RAM.

We now show that the RAM is universal for the class

THEOREM 3.4.1 Every T -step FSM M =(Σ , Ψ , Q , δ , λ , s , F ) computation can be simulated
by a RAM in O ( T ) steps with constant space. Thus, the RAM is universal for finite-state machines.
Proof We sketch a proof. Since an FSM is characterized completely by its next-state and
output functions, both of which are assumed to be encoded by binary functions, it suffices to
write a fixed-length RAM program to perform a state transition, generate output, and record
the FSM state in the RAM memory using the tabular descriptions of the next-state and
output functions. This program is then run repeatedly. The amount of memory necessary
for this simulation is finite and consists of the memory to store the program plus one state
(requiring at least log 2 |

bits). While the amount of storage and time to record and
compute these functions is constant, they can be exponential in log 2 |

Q |

because the next-
state and output functions can be a complex binary function. (See Section 2.12 .) Thus, the
number of steps taken by the RAM per FSM state transition is constant.

Q |

The second notion of universality is captured by the idea that the RAM can execute RAM
programs. We discuss two execution models for RAM programs. In the first, a RAM program
is stored in a private memory of the RAM, say in the CPU. The RAM alternates between
reading instructions from its private memory and executing them. In this case the registers
described in Section 3.4.3 are locations in the random-access memory. The program counter
either advances to the next instruction in its private memory or jumps to a new location as a
result of a jump instruction.
In the second model (called by some [ 10 ]the random-access stored program machine
(RASP) ), a RAM program is stored in the random-access memory itself. A RAM program