No subject

[Dave.Touretzky@B.GP.CS.CMU.EDU]

"Connectionist models" is too vague a term to use when discussing Turing
equivalence.  Let's agree that AND, OR, and NOT gates are sufficiently
close to simulated "neurons" for our purposes.  Then a connectionist net
composed of thse "neurons" can simulate a Vax.  If you believe a Vax is
Turing-equivalent, then connectionist nets are too.  Of course Vaxen don't
really have infinite-length tapes.  That's okay; connectionist nets don't
have an infinite number of neurons either.

Jordan Pollack has shown that a connectionist net with a finite number of
units can simulate a Turing machine if one assumes the neurons can perform
infinite-precision arithmetic.  The trick is to use the neuron activation
levels to simulate a two-counter machine, which is formally equivalent to a
Turing machine.  (See any basic automata theory textbook for the proof.)

Now, if you don't like AND gates as neurons, and you don't like units that
represent infinite precision numbers as neurons, then you have to define
what sorts of neurons you do like.  My guess is that any kind of neuron you
define can be used to build boolean AND/OR/NOT gates, and from there one
proceeds via the Vax argument to Turing equivalence.

A different kind of question is whether a connectionist net with a
particular architecture can simulate a Turing machine in a particular way.
For instance, can DCPS, Touretzky and Hinton's Distributed Connectionist
Production System, simulate a Turing machine by representing the cells of
the tape as working memory elements?  The answer to this question is left
as an exercise for the reader.

-- Dave