14
$\begingroup$

I know that NAND gates can be used to create circuits that implement every truth table, and modern computers are built up of NAND gates. What is the theoretical link between NAND gates and Turing completeness? It seems to me that NAND gate circuits are closer to finite automata than Turing machines. My intuition is that I can build flip-flops, and therefore registers and memory, out of NAND gates, and unbounded memory is a crucial property of Turing complete systems. I'm looking for a more theoretical or mathematical explanation, or pointers on what to read.

$\endgroup$
  • 1
    $\begingroup$ "modern computers are built up of NAND gates" I'm pretty sure that's false. Typical cell libraries for digital designs contains tens when not hundred of gates and they vary in function (look for AOI gates) as well as in fan-in and fan-out. $\endgroup$ – AProgrammer Dec 29 '15 at 13:03
  • $\begingroup$ You're correct, I meant in a theoretical sense that all digital logic can be built up of NANDS, which are considered functionally complete $\endgroup$ – bsm Dec 29 '15 at 16:18
9
$\begingroup$

There is indeed little connection. For a thorough understanding, let me explain the connection between programs and circuits.

A program (or algorithm, or machine) is a mechanism for computing a function. For definiteness, let us assume that the input is a binary string $x$, and the output is a Boolean output $b$. The size of the input is potentially unbounded. One example is a program that determines whether the input is the binary encoding of a prime number.

A (Boolean) circuit is a collection of instructions for computing some finite function. We can picture the circuit as an electrical circuit, or think of it as a sequence of instructions (this view is called confusingly a straight-line program). Concretely, we can assume that the input is a binary string $x$ of length $n$, and the output is Boolean. One example is a circuit that determines whether the input encodes a prime number (just as before, only now the input has to be of length $n$).

We can convert a program $P$ into a circuit $P_n$ that simulates $P$ on inputs of length $n$. The corresponding sequence of circuits $P_0,P_1,P_2,\ldots$ is not arbitrary – they can all be constructed by a program that given $n$ outputs $P_n$. We call such a sequence of circuits a uniform circuit (confusingly, we often think of the sequence as a "single" circuit $P_n$ for an indefinite $n$).

Not every sequence of circuits is uniform. Indeed, a sequence of circuits can compute every function from strings to Boolean, computable or uncomputable! Nevertheless, in complexity theory we are interested in such non-uniform models in which the circuits are restricted. For example, the question P=NP states that NP-complete problems cannot be solved by polynomial time algorithms. This implies that NP-complete problems cannot be solved by polynomial size uniform circuits. It is moreover conjectured that NP-complete problems cannot be solved by polynomial size circuits without the requirement of uniformity.

Turing-complete computation models are models which realize all computable functions (and no more). In contrast, complete systems of gates (such as AND,OR,NOT or NAND) allow computing arbitrary finite functions using circuits made of these gates. Such complete systems can compute completely arbitrary functions using (unrestricted) sequences of circuits.

$\endgroup$
  • $\begingroup$ Can you explain " a sequence of circuits can compute every function from strings to Boolean, computable or uncomputable"? Does their ability to compute uncomputable (from the perspective of Turing-completeness) functions come from the restriction on input size? $\endgroup$ – bsm Dec 29 '15 at 0:40
  • 2
    $\begingroup$ @bsm There are absolutely no restrictions on what a sequence of circuits can compute. For inputs of length $n$ you can choose whichever function you want, and you can do this independently for each $n$. $\endgroup$ – Yuval Filmus Dec 29 '15 at 6:33
  • $\begingroup$ Can you expound on that, @YuvalFilmus? It seems odd that an uncomputable function such as Kolmogorov complexity would suddenly be "computable" using circuits. $\endgroup$ – Cort Ammon Dec 29 '15 at 18:48
  • 2
    $\begingroup$ @CortAmmon Every finite function is computable. For any (string) function $f$, its restriction to strings of length $n$ is computable. That's all. $\endgroup$ – Yuval Filmus Dec 29 '15 at 20:11
3
$\begingroup$

You are in fact correct. A combinational logic circuit is equivalent to a finite automaton. NAND gates do not make them more powerful; they are used because it is simply cheaper to build a digital logic circuit with only one kind of gate than it is to build it with all different gates. In fact, a NAND gate can be constructed from just an AND gate and a NOT gate. Flip-flops make the circuit Turing-complete. Here is a handy key:

Combinational circuits ~ Finite automata ~ Regular languages ~ Regular expressions ~ Propositional calculus ~ Straight line programs

Sequential circuits ~ Turing machines ~ Recursively enumerable languages ~ Predicate calculus ~ $\mu$-recursive functions

If you want to learn more, there is a very good book you can download in PDF form for free that explains all this:

https://cs.brown.edu/people/jes/book/pdfs/ModelsOfComputation.pdf

$\endgroup$

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.