2. Boolean circuits 21

t = 0 Γ0,1

t = 1

. . .

t = j Γj,k−1 Γj,k Γj,k+1

t = j + 1 Γj+1,k

. . .

t = T . . .

s cells

In this table the j-th row represents the configuration of M after j steps:

Γj,k corresponds to cell k at time j and consists of two parts: the symbol

on the tape and the state of the TM if its head is in k-th cell (or a special)

symbol Λ if it is not). In other words, all Γj,k belong to S ×

(

{Λ} ∪ Q .

(Only one entry in a row can have the second component different from Λ.)

For simplicity we assume that after the computation stops all subsequent

rows in the table repeat the last row of the computation.

There are local rules that determine the contents of a cell Γj+1,k if we

know the contents of three neighboring cells in row j, i.e., Γj,k−1, Γj,k and

Γj,k+1. Indeed, the head speed is at most one cell per step, so no other cell

can influence Γj+1,k. Rules for boundary cells are somewhat special; they

take into account that the head cannot be located outside the table.

Now we construct a circuit that computes F(x) for inputs x of length n.

The contents of each table cell can be encoded by a constant (i.e., indepen-

dent of n) number of Boolean variables. These variables (for all cells) will

be the auxiliary variables of the circuit.

Each variable encoding the cell Γj+1,k depends only on the variables

that encode Γj,k−1, Γj,k, and Γj,k+1. This dependence is a Boolean function

with a constant number of arguments. These functions can be computed

by circuits of size O(1). Combining these circuits, we obtain a circuit that

computes all of the variables which encode the state of every cell. The size

of this circuit is O(sT)O(1) = poly(n).

It remains to note that the variables in row 0 are determined by the

input string, and this dependence leads to additional poly(n) assignments.

Similarly, to find out the result of M it is enough to look at the symbol

written in the 0-th cell of the tape at the end of the computation. So the

output is a function of ΓT,0 and can be computed by an additional O(1)-size

circuit. Finally we get a poly(n)-size circuit that simulates the behavior of M

for inputs of length n and therefore computes the Boolean function Fn.