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 [EMAIL PROTECTED] Australia http://parallel.hpc.unsw.edu.au/rks International prefix +612, Interstate prefix 02 ----------------------------------------------------------------------------

**
pgpQklhRggBVS.pgp**

*Description:* PGP signature