turing equivalence

[Gary Cottrell]

Noel writes:

Jay McClelland does not think that this is a very worthwhile
pursuit because "Turing equivalence is not a guarantee of
capturing the kinds of intelligence that people exhibit but
Turing machines do not, such as: [long list...]

While this may be true, we do not know whether something
like Turing equivalence is a NECESSARY condition for the
performance of such human phenomena.

Jay says, and I agree, that, "We need to start thinking of
ways of going beyond Turing equivalence." 

[end of noel]

Wait, this is crazy unless you believe in Quantum machines
or some such [which is a perfectly reasonable response to
the following, but for now, let's pretend it's not]. If you 
are a normal computer scientis/AI/PDP/Cognitive Science 
researcher, then you believe the basic assumption underlying
AI that >>thinking is a kind of computation<<. All of the known
kinds of computation are equivalent to the kind performed by
a TM. So if we could show that a PDP net is equivalent to a
TM, then we would have captured all of those things Jay was talking
about. The problem is the proof is not constructive. 

If anything, what we need to do is find the class of functions that 
are easily *learnable* by particular PDP architectures. This will 
be a *subset* of the things computable by a TM. Hence, proving TM 
equivalence is not NECESSARY, however, it sure would be SUFFICIENT 
to show that it isn't crazy to try to find a learning algorithm and 
an architecture that could learn some particular class of problems, 
since whatever we would want to compute is certainly do-able by a 
neural net.

Interesting work along these lines has been done by Servan-Schreiber
et al., & Jeff Elman, where they show that certain kinds of FSM's
are hard for simple recurrent nets to learn, and Jeff shows that
a net can learn the syntactic structure of English, but is poor
at center embedding, while being fine with tail recursive clauses.

gary cottrell