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

Hint: Construct a program that temporarily moves the value of AC aside, fetches the
address containing the destination for the store, and uses Boolean operations to modify
a STA instruction in the program so that it contains the destination address.
3.43 Write an assembly-language program that repeatedly examines the input register until
it is nonzero and then moves its contents to the accumulator.
3.44 Sketch an assembly-language program to emulate a target CPU by a host CPU under
the assumption that each CPU's instruction set supports indirection. Provide a skeleton
program that reads an instruction from the target instruction set and decides which host
instruction to execute. Also sketch the particular host instructions needed to emulate a
target add instruction and a target jump-on-zero instruction.
Chapter Notes
Although the concept of the finite-state machine is fully contained in the Turing machine
model (Section 3.7 ) introduced in 1936 [ 338 ], the finite-state machine did not become a se-
rious object of study until the 1950s. Mealy [ 215 ] and Moore [ 223 ] introduced models for
finite-state machines that were shown to be equivalent. The Moore model is used in Sec-
tion 3.1 . Rabin and Scott [ 266 ] introduced the nondeterministic machine, although not de-
fined in terms of external choice inputs as it is defined here.
The simulation of finite-state machines by logic circuits exhibited in Section 3.1.1 is due
to Savage [ 285 ], as is its application to random-access (Section 3.6 ) and deterministic Tur-
ing machines (Section 3.9.1 )[ 286 ]. The design of a simple CPU owes much to the early
simple computers but is not tied to any particular architecture. The assembly language of
Section 3.4.3 is borrowed from Smith [ 312 ].
The shallow circuits simulating finite-state machines described in Section 3.2 are due to
Ladner and Fischer [ 186 ] and the existence of a universal Turing machine, the topic of Sec-
tion 3.7 ,wasshownbyTuring[ 338 ].
Cook [ 74 ] identified the first NP -complete problem and Karp [ 159 ]demonstratedthata
large number of other problems are NP -complete, including the Traveling Salesperson prob-
lem. About this time Levin [ 199 ] (see also [335]) was led to similar concepts for combinatorial
problems. Our construction in Section 3.9.1 of a satisfiable circuit follows the general out-
line given by Papadimitriou [ 235 ](whoalsogivesthereductionto SATISFIABILITY )aswell
as the construction of a circuit simulating a deterministic Turing machine given by Savage
[ 286 ]. Cook also identified the first P -complete problem [75, 79 ]. Ladner [ 185 ]observed
that the circuit of Theorem 3.9.1 could be written by a program using logarithmic space,
thereby showing that CIRCUIT VALUE is P -complete. More information on P -complete and
NP -completeproblemscanbefoundinChapter 8 .
The more sophisticated simulation of a circuit by a Turing machine given in Section 3.9.7
is due to Pippenger and Fischer [ 252 ] with improvements by Schnorr [ 301 ]andSavage,as
cited by Schnorr.