3 ms·
"The adder example demonstrates how a network of perceptrons can be used to simulate a circuit containing many NAND gates. And because NAND gates are universal
by joe_the_user 13y ago
"The adder example demonstrates how a network of perceptrons can be used to simulate a circuit containing many NAND gates. And because NAND gates are universal for computation, it follows that perceptrons are also universal for computation."
I think this comment from the article needs caveats. Of course, a neural network would not qualify as Turing Complete just because it's finite. Keep in mind also that neural network, lacking anything like counters, tape, or recursion, couldn't approximate a Turing in the way that a finite Von Neuman architecture machine does. (A NN can represent any given function over a domain if it get large enough, kind of the universality of a finite automaton).
I know this a reference to this generation of NN having overcome an earlier problem of not being able to represent a NAND gate but still, it's worthing keeping mind that an ordinary computer can simulate an NN with just a program but this doesn't work vice-versa, so that NN's in that sense are far from universal.
- michael_nielsen 13y agoNetworks of perceptrons are universal in the standard sense used when talking about circuits --- they can compute any finite Boolean function. I agree that the relationship between circuit complexity and Turing machines is somewhat subtle, for the reasons you mention. The relationship is greatly clarified by the notion of uniform circuit complexity, which makes it possible to prove an equivalence between a (carefully defined notion of) circuit complexity and Turing machine complexity. Unfortunately, I don't know of a good online treatment of uniform circuit complexity. I learnt it through a 1993 paper by Andy Yao, but that's definitely not a good introductory reference! In any case, in my book I'm using the term universal in the same way as people usually use it for circuits, i.e., it means the same thing as when people say that the NAND gate is universal for computation. Hope that clarifies things.