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.
Previous Page Next Page