X-Message-Number: 4353
Subject: The Church-Turing Thesis
Date: Fri, 05 May 1995 10:50:16 -0400
From: "Perry E. Metzger" <>

> From:  (Thomas Donaldson)
> 
> For those who have been following this discussion a very interesting article
> has just appeared in the 28 April 1995 issue of SCIENCE. It seems that 
> neural nets may actually do MORE than Turing machines. The reason, basically,
> is that Turing machines work only in integers and are finite while neural
> nets, as analog devices, depend on real numbers rather than integers.

And its bullshit.

I won't even bother going into the details. I'm shocked that SCIENCE
would publish junk like that -- did they get a single automata
theorist to review the article?

Suffice it to say that you are correct that in a certain abstract way
analog systems deal with "real numbers", but real analog systems
always have a certain degree of error, so they can always be simulated
by a digital system with a small random number generator
attached. Furthermore, analog systems aren't really analog if you go
down far enough -- a capacitor's charge is quantized because charge
carriers are quantized, for example.

There are also theoretical proofs that analog systems are no more
powerful, but I don't want to get into them here. Read a good book on
automata theory for details if you like.

People have been arguing against the Church-Turing thesis for fifty
years. No one has ever built a machine that could do anything that a
Turing machine couldn't, or shown an actual example of a problem that
a theoretically constructable machine could do that a Turing machine
couldn't. People who have a religious attachment to the notion that
humans are more powerful than "mere" machines keep on looking, of
course. 

They make silly claims. I am fond of Lucas being Goedelized by the
famous "Lucas cannot consistantly assert this statement" sentence. I
have heard virtually every possibility before on the Church-Turing
thesis. I've heard analog machines, weird quantum machines, you name
it. None of it turns out to be more powerful using any reasonable
model. (Oracles ARE more powerful, but thats why they are Oracles --
you can't build them.)

I am not religious on this matter. I'm willing to hear legitimately
new ideas on the subject any time. However, I will point out that
nearly every obvious argument has been used over the last 40 years,
and none of them have turned out true. You are going to have to try
VERY HARD to find something legitimately new by way of argument.

Perry


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