How to relate circuit size to the running time of Turing machine

Question

From http://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/,

Define, $M_{[x,c]}$ as the deterministic Turing machine that operates as follows on an input $y$. The machine treats $x$ as a deterministic program, and simulates $x$ on input $y$. At the same time the machine runs a counter that stops its execution after steps $|y|^c$. If the machine accepts before the counter stops, then it accepts; otherwise, it rejects.

Let $f(i,c)$ be the smallest natural number so that $M_{[i,c]}$makes a mistake on the input $y$. Then, if $P \neq NP$ is true, the function $f(i,c)$ is always defined.

Theorem: Suppose that there are infinite number of $i$ for which there exists a $c$ so that $$f(i,c) > 2^{2^{|i|+c}}$$ Then, for infinitely many $n$, SAT has circuit size $n^{O(\log n)}$.

Proof: Let $i>1$ and $c$ be so that $$f(i,c) > 2^{2^{|i|+c}}$$ Define $n = 2^{|i|+c-1}$. Note, that $c$ is at most $\log n$. Then, $M_{[i,c]}$ on all $y$ of length $n$ is correct, since $y \leq 2^n = 2^{2^{|i|+c-1}} < f(i,c)$. The size of the circuit that simulates this Turing machine on inputs of length $n$ is polynomial in $|i|$, $n$, and the running time of the machine. The machine, by definition, runs in time $|y|^c \leq n^c \leq n^{\log n}$

I am not getting this part. Can anyone explain this (to specify, “The size of the circuit that simulates this Turing machine on inputs of length $n$ is polynomial in $|i|$, $n$, and the running time of the machine” in the quote)? (So the question is how can we relate the running time of Turing machine to the size of the circuit.)

Answer 1

The way to show that circuits are equivalent to TMs is as follows: for a TM, you encode it in binary (i.e states, transitions, etc.)

Then, you construct a circuit whose gates represent the transitions between each configuration of the TM. Since configuration transitions are local, then you only need local gates (i.e gates that depend on a constant number of inputs).

The idea is that you can compute configuration $c_i$ from configuration $c_{i-1}$ by examining the contents of 3 adjacent cells, and if the head of the machine is there, update them accordingly. It's rather technical to write formally, but it's a generally simple proof (See "Computational complexity" by Arora and Barak for a proof).

Using this proof, you see that the size of the circuit is polynomial in the running time of the machine and the input length, because the circuit is constructed in "levels", where each level corresponds to a configuration of the TM.