Are Neural Nets Turing Equivalent?

Leonard Uhr uhr at cs.wisc.edu
Thu Sep 20 13:26:34 EDT 1990


Peter Cariani's description of the equivalence of NN to finite state automata,
but to Turing machines when given a potentially infinite ability (either the
traditional memory tape or unbounded processors) is good, and nicely simple.
  Two comments:  NN processors execute directly on what flows into them;
TM interpret processes stored on the memory tape - so it's more natural to think
of NN with potentially infinite numbers of processors, rather than memory plus
the processors now interpreting.
  You can add sensors to a TM as well as an NN - and will need to for the same
reasons.  As soon as you actually realize a "potentially infinite" TM you must
give it sensors that in effect make the real world the tape (e.g., TV, with motors
to move it from place to place).  So there's really no difference.

Len Uhr


More information about the Connectionists mailing list