X-Message-Number: 9255
From: eli+@gs160.sp.cs.cmu.edu
Subject: "non-Turing"
Date: Sun, 8 Mar 98 22:27:12 EST

Thomas Donaldson wrote:
>The first thing I thought when I read about the nonTuring neural net was 
>that it was a counterexample to the notion that not all machines must be
>Turing machines. 

It is that, if you mean "not all abstract machines", but this notion is
flimsy to begin with.  Deliberately constructing counterexamples is easy:
pick a problem that's not Turing-computable, and define an abstract machine
that's a TM augmented with an `oracle' for the problem.

This neural net model is simply another example of an abstract machine
that's too powerful to be physically reasonable.  (If you weren't happy
with the argument I posted the last time this came up, specify your
disagreement and I will undertake to dig up my xerox of that paper.)

>The particular features of the counterexample aren't so 
>important: what it tells us, more than anything else, is that we cannot make
>the ASSUMPTION that Turing machines can emulate everything we find in the 
>world.

Agreed, that's a bad assumption.  The Church-Turing thesis is (in some
interpretations) a statement about the world, and could be empirically
falsified.

http://plato.stanford.edu/entries/church-turing/
may be of interest.  (though I don't think the distinction between
"computable by a machine" in Copeland's "Thesis M" and "`rule of thumb' or
`purely mechanical'" in Turing's thesis will bear nearly as much weight as
Copeland wants it to.)

-- 
     Eli Brandt  |  eli+@cs.cmu.edu  |  http://www.cs.cmu.edu/~eli/

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