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.
$\begingroup$
$\endgroup$
2
-
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$– AProgrammerCommented Dec 29, 2015 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$– bsmCommented Dec 29, 2015 at 16:18
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
4
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.
answered Dec 28, 2015 at 21:05
-
$\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$– bsmCommented Dec 29, 2015 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$ Commented Dec 29, 2015 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$ Commented Dec 29, 2015 at 18:48
-
3$\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$ Commented Dec 29, 2015 at 20:11
$\begingroup$
$\endgroup$
1
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
-
$\begingroup$ Factual mistake: combinational circuits are memoryless (no flip-flop) and cannot implement a FA. $\endgroup$– user16034Commented Sep 21, 2023 at 12:13
$\begingroup$
$\endgroup$
Logical gates alone can do little, they can just build combinatorial logical systems.
But as soon as you add a clock, states become possible and you can build sequential systems and devices such as Turing machines or any kinds of processors.
$\begingroup$
$\endgroup$
1
Its because nand is another statement for distinction/contradiction --- contradictions are bad in logic because they make 'every possible statement true and its possible to build a contradiction out of a NAND more or less directly (just negate one input and tie them together). This is the deeper theoretical reason for a NAND gate's universality.
-
1$\begingroup$ This comment is not an answer and is wrong. $\endgroup$– user16034Commented Sep 21, 2023 at 12:02