3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Prof, I understand from the answer, that the comparison between the circuits and the machine is an unfair comparison, because the circuits has only a fixed length of input either machine is accepting any input , But I still have a question about cpu which is really a logical circuit "Is cpu equal to dtm?" Maybe that's what I'll ask in a new question $\endgroup$ – small Aug 29 '18 at 16:17
  • 1
    $\begingroup$ The CPU isn’t the entire system. Memory and I/O devices are separate, for example. $\endgroup$ – Yuval Filmus Aug 29 '18 at 16:44
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Every circuit has a fixed size, namely, its size. $\endgroup$ – Yuval Filmus Aug 25 '18 at 17:55
  • $\begingroup$ Sometimes we discuss families of circuits where one circuit is specified for each size. In that case, we distinguish the situation where the circuit of the family can be computed given the size and the situation where it cannot be computed. $\endgroup$ – dionyziz Aug 26 '18 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.