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

next one that matches the ( i + 1 ) b most significant bits. Show that this procedure can
be used to find the RAM word whose address matches addr in O (( m/b )(log m ) 2 )
Turing machine steps by a machine that can store in its control unit only one b -bit
subword of addr .
3.27 Extend Problem 3.26 by demonstrating that the simulation can be done with a binary
tape symbol alphabet.
3.28 Extend Theorem 3.8.1 to show that there exists a Turing machine that can simulate an
unbounded-memory RAM.
3.29 Sketch a proof that every Turing machine can be simulated by a RAM program of the
kind described in Section 3.4.3 .
Hint: Because such RAM programs can only have a finite number of registers, encode
the contents of the TM tape as a number to be stored in one register.

COMPUTATIONAL INEQUALITIES FOR TURING MACHINES

3.30 Show that a one-tape Turing machine needs time exponential in n to compute most
Boolean functions f :

n

B →B on n variables, regardless of how much memory is

allocated to the computation.
3.31 Apply Theorem 3.2.2 to the one-tape Turing machine that executes T steps. Deter-
mine whether the resulting inequalities are weaker or stronger than those given in The-
orem 3.9.2 .
3.32 Write a program in your favorite language for the procedure WRITE OR ( t , m )intro-
duced in Fig. 3.27 .
3.33 Write a program in your favorite language for the procedure WRITE CELL CIRCUIT ( t ,
m )introducedinFig. 3.27 .
Hint: See Problem 2.4 .

FIRST P -COMPLETE AND NP -COMPLETE PROBLEMS

3.34 Show that the language MONOTONE CIRCUIT VALUE defined below is P -complete.

MONOTONE CIRCUIT VALUE
Instance: A description for a monotone circuit with fixed values for its input variables
and a designated output gate.
Answer: “Yes” if the output of the circuit has value 1.

Hint: Using dual-rail logic, find a way to translate (reduce) a string in the language
CIRCUIT VALUE to a string in MONOTONE CIRCUIT VALUE by converting in loga-
rithmic space (in the length of the string) a circuit over the standard basis to a circuit
over the monotone basis. Note that, as stated in the text, the composition of two
logarithmic-space reductions is a logarithmic-space reduction. To simplify the con-
version from non-monotone circuits to monotone circuits, use even integers to index
vertices in the non-monotone circuits so that both even and odd integers can be used
in the monotone case.
3.35 Show that the language FAN - OUT 2 CIRCUIT SAT defined below is NP -complete.