The Role of Theory in Computer Science - Models of Computation: Exploring the Power of Computing - page 31

1.16 Describe the actions that could be taken by a Turing machine to simulate a circuit from
a straight-line program for it. Illustrate your approach by applying it to the simulation
of the full-adder circuit described in Section 1.4.1 .
1.17 Suppose you are told that a function is computed in four time steps by a very simple
finite-state machine, one whose logic circuit (but not its memory) can be realized with
four logic gates. Suppose you are also told that the same function cannot be computed
by a logic circuit with fewer than 20 logic gates. What can be said about these two
statements? Explain your answer.
1.18 Describe a finite-state machine that recognizes the language consisting of those strings
over

{ }

that end in 1.
1.19 Determine the language generated by the context-free grammar G =(

0, 1

N T R

, S ) , ,

N = { } T = { a , b , c , d } R

where

S , M , N

, and consists of the rules given below.

→ → c N d

a) d) N

S MN

b) M → a M b e) N → cd

c) M → ab

COMPUTATIONAL COMPLEXITY
1.20 Using the rules for the red pebble game, show how to pebble the FFT graph of Fig. 1.10
with five red pebbles by labeling the vertices with the time step on which it is pebbled.
If a vertex has to be repebbled, it will be pebbled on two time steps.
1.21 Suppose that you are told that the n -point FFT graph can be pebbled with √ n pebbles
in n/ 4 time steps for n 37. What can you say about this statement?

1.22 You have been told that the FFT graph of Fig. 1.10 cannot be pebbled with fewer than
three red pebbles. Show that it can be pebbled with two red pebbles in the red-blue
pebble game by sketching how you would use blue pebbles to achieve this objective.

≥

PARALLEL COMPUTATION
1.23 Using Fig. 1.12 as a guide, design a systolic array to convolve two sequences of length
two. Sketch out each step of the convolution process.
1.24 Consider a version of the PRAM consisting of a collection of RAMs (see Fig. 1.13 )with
small local random-access memories that repeat the following three-step cycle until they
halt: a) they simultaneously read one word from a common global memory, b) they
execute one local instruction using local memory, and c) they write one word to the
common memory. When reading and writing, the individual processors are allowed
to read and write from the same location. If two RAMs write to the same location,
they must be programmed so that they write a common value. (This is known as the
concurrent-read, concurrent-write (CRCW) PRAM.) Each RAM has a unique integer
associated with it and can use this number to decide where to read or write in the
common memory.
Show that the CRCW PRAM can compute the AND of n Booleanvariablesintwo
cycles.
Hint: Reserve one word in common memory and initialize it with 0 and assign RAMs
to the appropriate memory cells.