From: firth@sei.cmu.edu (Robert Firth)
Subject: Re: Computability of the universe
Organization: Software Engineering Institute
Date: Fri, 11 Sep 1992 14:22:13 GMT

In article <1992Sep11.013141.28378@galois.mit.edu> jbaez@riesz.mit.edu (John C. Baez) writes:

>This is rather unfair to Church and Turing, and I'm crossposting to
>sci.math and sci.logic so you can be properly flamed.  :-)  Hopefully
>you know that you're being unfair.  These guys aren't famous for
>proposing "A Turing machine can do any computation that can be done by
>any machine which can do precisely those computations that can be done
>by a Turing machine"!

Yes, it's unfair; and yes, I'd rather be in a discussion than a debate,
so please let me amplify.

What the Church-Turing thesis shows is this, in my view: there is a class
of "computing machines" - engines manipulating symbols according to rules -
and all these machines are equivalent, so any function that one machine
can compute can be computed by any other.  This class contains a lot of
interesting machines, including digital computers, and it also includes
the "universal Turing machine", which is of interest because of its
extreme and elegant simplicity.

This is a most valuable result, and yes, it was hard work to get there,
and of course it's a true theorem.  But that is not how the result is
usually presented.  Far more often, one hears that "anything that can be
computed" can be computed by a Turing machine.  Indeed, that's how Alan
Turing himself described the result:

	Every function which would "naturally be regarded as
	computable" can be computed by the universal Turing machine

And that's false.  If I can build a machine to compute something, then
that something would naturally be regarded as computable, yes?  For
if something exists, it must be possible.  Well, I can build a machine
that will compute the function Random(), and out of very simple
components - a photon source, a polarising filter, and a detector,
for instance.  But a Turing machine cannot compute that function.

Fair enough - the result is interesting, and valuable, and happens
to have been a wee bit overstated.  But in my experience, the computer
scientists quote the result in its overstated form, and, when challenged,
immediately redefine "computable" in a way that palpably closes the
circle.  Again, they're entitled to define words however they please,
as was Humpty Dumpty - but many of them seem to make this thesis the
basis for a claim that *real things in the real world* can all be
simulated by Turing machines - and that claim is preposterous; the
photon is one of the simplest things in the real world, and they can't
even simulate that.

This point is important to me, because I care about the real world and
want to understand it.  And, as best we know, true randomness is a key
and irreducible component of that world.  Yes, QM may be totally wrong,
but the current evidence is most compelling, so compelling that anyone
who denies it looks rather crankish.  And I'd like a formal model of
that world, to aid in understanding it.  But a model that cannot
represent what to me is one of the most important features of the
real world seems to me a very bad model, and one that, however well
it might approximate the phenomena, can add nothing to our understanding.

Yes, you can approximate an ellipse with epicycles, but the difference
is that the epicycle model is fundamentally wrong, and the ellipse model
is fundamentally right.  The one is unphysical and the other is physical.
I feel the same about the Turing machine model - I don't care about the
approximations; the model is unphysical, and so wrong.  The goal, after
all, is not numbers, but insight.



Xref: sparky sci.physics:14723 sci.astro:9717 sci.math:11521 sci.philosophy.tech:3244