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

number of states of a RAM can be very large; just the random-access memory alone has more
than 2 S states.
The programmability of the unbounded-memory RAM makes it universal for FSMs, as
we show in Section 3.4.4 . Before taking up this subject, we pause to introduce an assembly-
language program for the unbounded-memory RAM. This model will play a role in Chapter 5 .

3.4.3 Unbounded-Memory RAM Programs
We now introduce assembly-language programs to make concrete the use of the RAM. An
assembly language contains one instruction for each machine-level instruction of a CPU. How-
ever, instead of bit patterns, it uses mnemonics for opcodes and labels as symbolic addresses.
Labels are used in jump instructions.
Figure 3.18 shows a simple assembly language. It implements all the instructions of the
CPU defined in Section 3.10 and vice versa if the CPU has a sufficiently long word length.
Our new assembly language treats all memory locations as equivalent and calls them reg-
isters. Thus, no distinction is made between the memory locations in the CPU and those
in the random-access memory. Such a distinction is made on real machines for efficiency: it
is much quicker to access registers internal to a CPU than memory locations in an external
random-access memory.
Registers are used for data storage and contain integers. Register names are drawn from the

.The address of register R i is i . Thus, both the number of registers and
their size are potentially unlimited. All registers are initialized with the value zero. Registers
used as input registers to a program are initialized to input values. Results of a computation
are placed in output registers . Such registers may also serve as input registers. Each instruc-
tion may be given a label drawn from the set

{

R 0 ,R 1 ,R 2 , ...

}

set

{ N 0 , N 1 , N 2 , ... } . Labels are used by jump

instructions, as explained below.

Instruction Meaning

INC R i Increment the contents of R i by 1.

DEC R i Decrement the contents of R i by 1.

CLR R i Replace the contents of R i with 0.

R i ← R j Replace the contents of R i with those of R j .

JMP + N i Jump to closest instruction above current one with label N i .

N i Jump to closest instruction below current one with label N i .
R j JMP + N i If R j contains 0, jump to closest instruction above
current one with label N i .
R j JMP − N i If R j contains 0, jump to closest instruction below
current one with label N i .
CONTINUE Continue to next instruction; halt if none.
Figure 3.18 The instructions in a simple assembly language.

JMP

−