Neural nets are universal computing devices

[sontag@control.rutgers.edu]

     NEURAL NETS ARE UNIVERSAL COMPUTING DEVICES -- request for comments

We have proved that it is possible to build a recurrent net that simulates a
universal Turing machine.  We do not use high-order connections, nor do we
require an unbounded number of neurons or an "external" memory such as a stack
or a tape.  The net is of the standard type, with linear interconnections and
about 10^6 neurons.

There was some discussion in this medium, some time ago, about questions of
universality.  At that time, besides classical references, mention was made of
work by Pollack, Franklin/Garzon, Hartley/Szu, and Sun.  It would appear that
our conclusion is not contained in any of the above (which assume high-order
connections or potentially infinitely many neurons).

[More precisely: a ``net'' is as an interconnection of N synchronously
evolving processors, each of which updates its state, a rational number,
according to x(t+1) = s(...), where the expression inside is a linear
combination (with biases) of the previous states of all processors.  An
"output processor" signals when the net has completed its computation by
outputting a "1".  The initial data, a natural number, is encoded via a
fractional unary representation into the first processor; when the computation
is completed, this same processor has encoded in it the result of the
computation.  (An alternative, which would give an entirely equivalent result,
would be to define read-in and read-out maps.)  As activation function we pick
the simplest possible "sigmoid," namely the saturated-linear function s(x)=x
if x is in [0,1], s(x)=0 for x<0, and s(x)=1 for x>1.]

We would appreciate all comments/flames/etc about the technical result.
(Philosophical discussions about the implications of these types of results
have been extensively covered in previous postings.)

A technical report is in preparation, and will be posted to connectionists
when publicly available.  Any extra references that we should be aware of,
please let us know.

Thanks a lot,
-Hava Siegelman and Eduardo Sontag,
 Depts of Comp Sci and Math, Rutgers University.