Turing Machines and Conenctionist networks

[David Chalmers]

Steve Hanson asks:

>mathematical query...is it contradictory that feedforward
>networks are claimed BOTH to be able to approximate any
>real valued function mapping and NOT be able (as Hendler suggests)
>be turing equivalent?    Cannot  specific turing machines be
>seen as a real valued function mapping?

Feedforward networks can approximate functions from any *finite* domain.
Turing equivalence requires the ability to compute general recursive functions
defined on *infinite* domains (such as the natural numbers).

The only ways that I can see to allow connectionist networks to handle
functions on infinite domains are:

(1) Arbitrarily high-precision inputs and processing; or
(2) Arbitrarily large numbers of input units (along with arbitrarily large
    network size); or
(3) Inputs extended over arbitrarily large periods of time.  (Of course a
    feed-forward network would be no good here.  We'd need some form of
    recurrence to preserve information.)

Note that we never need *infinite* precision/size/time, as some have suggested.
We merely need the ability to extend precision/size/time to an arbitrarily
large (but still finite) extent, depending on the problem and the input.
Infinite precision etc would give us something new again -- the ability to
handle functions from *uncountable* domains (not even Turing machines can do
this).

Incidentally, of the methods above, I think that (3) is the most plausible.
But the importance of Turing equivalence to cognition is questionable.

Dave Chalmers       (dave at cogsci.indiana.edu)
Center for Research on Concepts and Cognition
Indiana University.