Proof that Turing machines and computers have same power

Question

How do we prove that any logical circuit can be simulated by a Turing machine?

For example, we take a logical circuit $L$ that is made of gates and, or, and not. This circuit determines a problem, for example, whether the input is an even number. How can we prove that if a problem is decided by a logical circuit, there is a Turing machine that can decide the problem?

In other words, how do we prove that a CPU is equal in power to a Turing machine? We should not forget that a Turing machine has infinitely many cells.

Answer 1

Turing machines and Boolean circuits cannot really be compared, since Turing machines handle inputs of arbitrary length, whereas Boolean circuits only handle inputs of fixed length.

Furthermore, Turing machines and CPUs corresponds to two different computation models. Turing machines access their memory by moving a head across a tape. In contrast, a CPU accesses its memory via random access. The abstraction corresponding to CPUs is the random-access machine.

If we want to compare the power of Turing machines and circuits, we need to put them into equal footing. One way to do this is to consider a sequence of circuits $C_0,C_1,C_2,\ldots$, one per input length. Such a sequence computes a language in the natural way: an input $x$ belongs to the language if $C_{|x|}$ returns True when given $x$ as input. This circuit model is much more powerful than Turing machines – indeed, it can compute any language, whereas Turing machines can only compute decidable languages.

What went wrong? Let us consider your example, of circuits for parity. The circuits computing parity for different lengths of input are very similar to one another; they seem to be made from a "mold", a set of instructions which can be translated to a circuit of arbitrary length. In contrast, the circuit model considered in the preceding paragraph specifies no such relation between the different circuits. When we add this constraint – that the different circuits follow a "blueprint" – we do get a model equivalent to Turing machines. What exactly constitutes a blueprint is a bit technical (one option is to have the circuits generated by a Turing machine), but the intuitive idea should be clear.

Circuits also come up when trying to understand resource-bounded computation, such as the complexity class $\mathsf{P}$ of languages which can be decided in polynomial time. It is known that any such language can be translated to a "uniform" family of circuits of polynomial size. In this way, the fact that the language can be decided efficiently is reflected by the size of circuits that compute it.

Answer 2

If your circuit is of fixed-size, then a Turing Machine T exists to compute it. The reason is that the Turing Machine can simply contain a list with all the possible input/output pairs.

If your circuit is not of fixed size, then we distinguish two cases. Either the circuit can be computed by a TM, given the input size, or not. In the case the circuit can be computed by a TM, say T', then T can invoke T' to obtain the circuit encoding. Subsequently, T can evaluate the circuit on the input. In order to do so, T would topologically sort the circuit and obtain the output value of each gate until the output value of the output gate is obtained, which will be its output. In case there exists no TM T' to obtain the circuit given the size, then the language is uncomputable and T cannot exist. To see this, note that the circuit could encode the halting problem.