Are Neural Nets Turing Equivalent?

[Jordan B Pollack]

In my 1987 dissertation, as Touretzky pointed out, I assumed rational
output values between 0 and 1 for two neurons in order to represent an
unbounded binary tape. Besides that assumption, the construction of
the "neuring machine" (sorry) required linear combinations,
thresholds, and multiplicative connections.  Linear combinations are
subsumed by multiplicative connections and a bias unit. Without
thresholds you cant make a decision, and without multiplicative
connections, you cant (efficiently) gate rational values, which is
necessary for moving in both directions on the tape.

Proofs of computability should be used necessarily be used as
architectures to build upon further (which I think a few people
misunderstood my thesis to imply), but as an indication of what
collection of primitives are necessary in a machine. One wouldn't want
to build a theoretical stored program computer without some sort of
conditional branch, or a practical stored program computer without a
connection between program and data memory.

I took this result to argue that higher-order connections are crucial
to general purpose neural-style computation. It is interesting to note
that GZ Sun's theorem involves second-order connection weights. It
probably involves thresholds as well.

I temporarily posted a revised version of the chapter of my thesis in
neuroprose, as pollack.neuring.ps.Z

Jordan Pollack                            Assistant Professor
CIS Dept/OSU                              Laboratory for AI Research
2036 Neil Ave                             Email: pollack at cis.ohio-state.edu
Columbus, OH 43210                        Fax/Phone: (614) 292-4890