Are Neural Nets Turing Equivalent?

[Dave.Touretzky@DST.BOLTZ.CS.CMU.EDU]

The Turing equivalence question has come up on this list before.

Here's a simple answer:
  No finite machine is Turing equivalent.
  This rules out any computer that physically exists in the real world.

You can make non-finite neural nets by assuming, say, numbers with
unbounded precision.  Jordan Pollack showed in his thesis how to encode a
Turing machine tape as two binary fractions, each of which was an
activation value of a "neuron".  This is no more ridiculous than assuming a
tape of unbounded length.

If you are willing to allow nets to have an unbounded number of units, then
you can use finite preceision units to simulate the tape and perhaps build
a Turing machine that way; it would depend on whether you view the wiring
scheme of the infinite neural net as having a finite or infinite
description.  (Classical Turing machines have a finite description because
you don't have to specify each square of the infinite tape individually.)

If you view the tape as external to the Turing machine, then all that's
left inside is a finite state automaton, and those can easily be
implemented with neural nets.

-- Dave