on the Turing computability of networks

[Paul Kube]

   From: Noel Sharkey <noel%CS.EXETER.AC.UK at VMA.CC.CMU.EDU>
   Date:        Sun, 14 Jan 90 17:27:23 GMT

   I keep hearing that there is a formal result about the
   equivalence of connect. models and Turing machines, but
   I have never seen it. 

If you don't restrict the class of connectionist models and consider
networks whose state transitions are solutions to algebraic
differential equations (this class is universal for analog computation
in some sense; see references below), then it's pretty obvious that a
connectionist network can simulate a universal digital machine.  For
example, the Sun on my desk is implemented as an analog network.

Going the other way is a little trickier, since you have to 
make decisions about how to represent real numbers on Turing machine
tapes etc., but there are reasonable ways to do this.  Here the
main results are Pour-El's that there are ADE's defined in terms
of computable functions which have UNcomputable solutions from
computable initial conditions (the shockwave solution to the wave
equation has this property, in fact), and Vergis, Steiglitz and
Dickinson's that if the second derivative of the solution is
bounded, then the system is efficiently Turing simulatable.

So if you bound second derivatives of network state (which amounts to
bounding things like acceleration, force, energy, bandwidth, etc. in
physical systems), then networks and Turing machines are equivalent.
Beyond this, one would like a hierarchy of connectionist models
ordered by computational power along the lines of what you get in
classical automata theory, but I don't know of anything done on this since
_Perceptrons_ (so far as I'm aware, none of the recent
universal-approximator results separate any classes).

	--Paul Kube
	  kube at cs.ucsd.edu

-----------------------------------------------------------------------------
References:

%A Anastasios Vergis
%A Kenneth Steiglitz
%A Bradley Dickinson
%T The complexity of analog computation
%J Mathematics and Computers in Simulation
%V 28
%D 1986
%P 91-113

%A Marian Boykan Pour-El
%A Ian Richards
%T Noncomputability in models of physical phenomena
%J International Journal of Theoretical Physics
%V 21
%D 1982
%P 553-555
%X lots more interesting stuff in this number of the journal

%A Marian Boykan Pour-El
%A Ian Richards
%T A computable ordinary differential equation which possesses no computable solution
%J Ann. Math. Logic
%V 17
%D 1979
%P 61-90

%A Lee A. Rubel
%T A universal differential equation
%J Bulletin of the American Mathematical Society
%V 4
%D 1981
%P 345-349

%A Marian Boykan Pour-El
%A Ian Richards
%T The wave equation with computable initial data such that its unique solution is not computable
%J Advances in Mathematics
%V 39
%D 1981
%P 215-239

%A A. Grzegorczyk
%T On the definitions of computable real continuous functions
%J Fundamenta Mathematicae
%V 44
%D 1957
%P 61-71

%A A. M. Turing
%T On computable numbers, with an application to the Entscheidungsproblem
%J Proceedings of the London Mathematics Society
%V 42
%N 2
%D 1936-7
%P 230-265