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

length of the accumulator. (See Section 2.7 .)Thesameistrueforthelogicalvectorandthe
shift operations. (See Section 2.5.1 .) Thus, circuits affecting the accumulator (see Fig. 3.39 )
have size O ( b ) and depth O (log b ) . Circuits affecting the opcode and output registers and
the memory address and data registers are simple and have size O ( b ) and depth O (log b ) .
The circuits affecting the program counter not only support transfer of data from the accu-
mulator to the program counter but also allow the program counter to be incremented. The
latter function can be performed by an adder circuit whose size is O (

log m ) and depth is

O (log log m ) . It follows that

C Ω ( δ CPU )= O ( b + log m )

D Ω ( δ CPU )= O (log b +log log m )

3.10.7 Emulation
In Section 3.4 we demonstrated that whatever computation can be done by a finite-state ma-
chine can be done by a RAM when the latter has sufficient memory. This universal nature of
the RAM, which is a model for the CPU we have just designed, is emphasized by the problem
of emulation, the simulation of one general-purpose computer by another.
Emulation of a target CPU by a host CPU means reading the instructions in a program
for the target CPU and executing host instructions that have the same effect as the target
instructions. In Problem 3.44 we ask the reader to sketch a program to emulate one CPU
by another. This is another manifestation of universality, this time for unbounded-memory
RAMs.
.......................................
Problems
MATHEMATICAL PRELIMINARIES

3.1 Establish the following identity:

k

j 2 j = 2 ( k

1 ) 2 k + 1

−

j = 0

3.2 Let p : ￿ be polynomial functions on the set ￿ of non-

negative integers. Show that p ( q ( n )) is also a polynomial in n .

→ and q : ￿ →

FINITE-STATE MACHINES

3.3 Describe an FSM that compares two binary numbers supplied as concurrent streams of
bits in descending order of importance and enters a rejecting state if the first string is
smaller than the second and an accepting state otherwise.
3.4 Describe an FSM that computes the threshold-two function on n Boolean inputs that
are supplied sequentially to the machine.
3.5 Consider the full-adder function f FA ( x i , y i , c i )=( c i + 1 , s i ) defined below where +
denotes integer addition:

2 c i + 1 + s i = x i + y i + c i