[Solved]: Connection between NAND gates and Turing completeness

Problem Detail: 

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.

Asked By : bsm

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51220