Xref: utzoo talk.religion.misc:7891 comp.ai:2316
Path: utzoo!attcan!uunet!seismo!sundc!pitstop!sun!quintus!ok
From: ok@quintus.uucp (Richard A. O'Keefe)
Newsgroups: talk.religion.misc,comp.ai
Subject: Re: The Ignorant assumption
Message-ID: <492@quintus.UUCP>
Date: 30 Sep 88 07:51:15 GMT
References: <1369@garth.UUCP> <2346@uhccux.uhcc.hawaii.edu> <1383@garth.UUCP> <372@quintus.UUCP> <1390@garth.UUCP> <388@quintus.UUCP> <7059@aw.sei.cmu.edu> <1929@aplcomm.jhuapl.edu> <7202@aw.sei.cmu.edu>
Sender: news@quintus.UUCP
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 28

In article <7202@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes:
>   Since a function is surely "computable" if a physical
            ********
>   system can be constructed that computes it, ...
>from which, I submit, the conclusion follows:
>   ... the existence of true random-number generators directly
>   disproves the Church-Turing conjecture.

>Granted, one can readily evade this conclusion.  It is necessary merely
>to redefine "natural", "computable", "function", or some other key term.

It is not necessary to REdefine "function", only to use the usual meaning.
Given the same inputs, a function must always yield the same output(s).
The kind of physical system Firth has described is a realisation of
a(n indexed) random variable, and it has been held for many years that
"true random numbers" are not computable.  (See section 3.5 ("What is a
random sequence") of Knuth's "The Art of Computer Programming, Vol 2",
this statement is implicit in definition R6.

The original question was a purely rhetorical one (I _don't_ believe that
the universe is a Turing machine), but it's worth pointing out that we
only have a finite set of imprecise observations, so that a sufficiently
good simulation of a quantum-mechanical system (with top-notch pseudo-
random number generation!) *might* be fooling us.  You can only appeal to
phsyical random number generators to disprove the Church-Turing hypothesis
if you assume that the quantum-mechanical laws a really true, which is to
say if you already assume that the universe is not running on a Turing machine.
I believe it, but a circular "proof" like that is no proof!