On Mon, Jun 20, 2005 at 11:40:03AM +0200, Bruno Marchal wrote:
>
> Le 17-juin-05, ? 07:19, Russell Standish a ?crit :
>
> >Hmm - this is really a definition of a universal machine. That such a
> >machine exists is a theorem. Neither depend on the Church-Turing
> >thesis, which says that any "effective" computation can be done using
> >a Turing machine (or recursive function, or equivalent). Of course the
> >latter statement can be considered a definition, or a formalisation,
> >of the term "effective computation.
>
> Hmm - I disagree. Once you give a definition of what a turing machine
> is, or of what a program fortran is, then it is a theorem that
> universal turing machine exists and that universal fortran program
> exists. To say that a universal machine exists, computing by definition
> *all* computable function, without any "turing" or "fortran"
> qualification, you need Church thesis.
>
> Bruno
>
>
> http://iridia.ulb.ac.be/~marchal/
>
From Li & Vitanyi:
Church's thesis: The class of algorithmically computable numerical
functions (in the intuitive sense) coincides with the class of partial
recursive functions
Turing's thesis: Any process that can be naturally called an effective
procedure is realized by a Turing machine.
Both of these are really a definition of what it means call an
algorithm "effective".
Theorem: the class of Turing machines corresponds to to the class of
partial recursive functions. Consequently, both theses are equivalent.
Theorem: The class of Fortran machines corresponds to the class of
Turing machines. (I don't think this is proved in Li & Vitanyi, but
I'm sure it is proved somewhere. It is clearly not a consequence of
the Church-Turing thesis).
Theorem: There exist formalisable processes that aren't simulable by
Turing machines. Such processes are called hypermachines. See Toby
Ord, math.LO/0209332
Conjecture: All physical processes can be simulated by a Turing
machine. I suspect this is false, and point to beta decay as a
possible counter example.
Conjecture: All "harnessable" physical processes can be simulated by a
Turing machine. By harnessable, we mean exploited for performing some
computation. I suspect this is true. Machines with random oracles with
computable means only compute the same class of functions as do Turing
machines. (classic result by de Leeuw et al. in 1956)
So, no I don't think the Turing thesis is needed for a universal
machine.
Cheers
--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.
----------------------------------------------------------------------------
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics 0425 253119 (")
UNSW SYDNEY 2052 R.Standish.domain.name.hidden
Australia http://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
----------------------------------------------------------------------------
- application/pgp-signature attachment: stored
Received on Tue Jun 21 2005 - 07:05:01 PDT