Turing Equivalence of Connectionist Nets

[Vasant Honavar]

On the Turing-equivalence of Connectionist networks.

Warren S. McCulloch & Walter H. Pitts, 1943.
"A Logical Calculus of the Ideas Immanent in Nervous Activity,"
Bulletin of Mathyematical Biophysics, Vol. 5, pp 115-133.
Chicago: University of Chicago Press. 
(Reprinted in "Embodiments of Mind", 1988. Cambridge, MA: MIT Press).

There is also a paper by Kleene in a collected volume titled
"Automata Studies" published by the Princeton Univeristy Press
(sorry, I don't have the exact citation) in the '50s or '60s
which addresses similar issues.

The basic argument is:
Consider a net which includes (but is not limited to) a set of nodes 
(possibly infinite in number) that serve as input and/or output nodes 
(a role akin to that of the inifinite tape in the Turing machine). 
Any such net can compute only those numbers that can be computed by 
the Turing machine. Furthermore, each of the numbers computable by 
the Turing machine can be computed by such a net. 

However, connectionist networks that we build are finite machines
just as the general purpose computers modeled on Turing machines are
finite machines and are therefore equivalent to Turing machines with
finite tapes.

Vasant Honavar
honavar at cs.wisc.edu