Are Neural Nets Turing Equivalent?

[bmb@Think.COM]

As I recall, another interesting point that somebody (I don't remember
who it was) brought up in our last discussion about this topic is the
possibility of a difference in the capabilities of analog and digital
implementations of neural nets (or of any other type of computation for
that matter).  This speculation is based on the work of Pour-El and
Richards at the Department of Mathematics at the University of
Minnesota.

The general idea is as follows: Real numbers that can be produced by a
Turing machine are called "computable."  There must be a countable
number of these, since there is a countable number of Turing machines.
(Note: Since the real numbers are uncountable, there's clearly lots more
of them than there are computable numbers.)

Now, Pour-El and Richards showed that the wave equation, with computable
initial conditions, evolving for a computable length of time, can give
rise to noncomputable values of the dependent variable.  This, of
course, makes one wonder whether or not the same is true for other
continuum equations of mathematical physics, such as those that govern
the passage of signals through wires (basically the wave equation with
complicated boundary conditions and other bells and whistles) and
semiconductors (ditto plus some nonlinearities).

Since analog computation takes place in the presumably continuous real
world where physical processes are governed by continuum equations,
whereas digital circuitry goes through great pains to wash out all but
the "binariness" of signals, one might conclude that there is a
possibility that analog circuitry can do things that digital circuitry
can't.

This conclusion is far from clear, but I'd say it's definitely worth
thinking about.  In "The Emperor's New Mind," Penrose cites the above
work in his attack on Strong AI (since it seems to imply that there is a
stronger notion of computability than Turing equivalence).  In any
event, here's the reference in case anybody's interested:

M. Pour-El, I. Richards, Advances in Mathematics, Vol. 39, pp. 215-239
(1981).

Bruce Boghosian
Thinking Machines Corporation
bmb at think.com