X-Message-Number: 4244
From: Peter Merel <>
Subject: Computability and Complexity
Date: Thu, 20 Apr 1995 00:47:33 +1000 (EST)

Paul Wakfer writes,

>     In that message he again states what everyone here must now know by
>heart (even the few who didn't already know it): that all computers
>including neural nets are *computationally equivalent* to Turing machines.
>But what neither he nor anyone else has done here is to refute, or even
>address, the statement that neural nets (and parallel machines in general)
>will always be able to do things faster in principle than Turing machines.
>Since we live in a reality which includes time as a very important
>attribute, this clearly makes neural nets fundamentally different from
>other types of computers.

I hate to extend a thread that is imho way off-topic, but as I recall my
computability theory it's not hard to demonstrate that parallel or
non-deterministic Turing machines are computationally equivalent to
ordinary serial Turing machines, no magic required.

Further to this, given that the only advantage that a neural net has over
a serial emulation of a neural net is that of time against computational
complexity, you're no longer dealing with computability theory at all. You're
dealing with complexity theory. Now there is a famous class of problems
in complexity theory, those with an "NP complete" computational complexity,
these being problems that cannot be solved in polynomial time on a serial
machine but which can be solved in polynomial time on a non-deterministic
(read "parallel") machine. Last I heard it remains an open question as to
whether this class actually has any members in it.

However, even if it should turn out that there are members in the
NP-complete class, a neural network is not really a non-deterministic
machine. To get real non-determinism you have to look at some of the
new quantum-dot machines; there are physical proofs being put about
that suggest that these machines will be able to solve all manner of
very hard problems in polynomial or even linear time - prime
factorization being the most important one. The algebras that these
machines employ are highly non-intuitive - they have operations like
the square-root of a not, whatever you might construe that to mean.

If it should turn out that these machines work as advertised, I should
imagine that this will be quite an empirical shot in the arm for
complexity theorists.  However I must say that my feeling is that it is
unlikely that human brains require such quantum algebras in order to
perform their tricks. My only evidence for this is anecdotal - no
idiot-savants have been observed factoring large primes in linear
time. Obviously this is an avenue of enquiry that Penrose and Eccles 
have overlooked :-)

Pete.


Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=4244