Le 21-juin-05, à 12:28, Russell Standish a écrit :

## Advertising

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 usinga Turing machine (or recursive function, or equivalent). Of coursethelatter 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 programexists. To say that a universal machine exists, computing bydefinition*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

OK.

Turing's thesis: Any process that can be naturally called an effective procedure is realized by a Turing machine.

Not OK. Please give me the page.

Both of these are really a definition of what it means call an algorithm "effective".

By who? Effective has more than one meaning in logic.

Theorem: the class of Turing machines corresponds to to the class of partial recursive functions. Consequently, both theses are equivalent.

OK.

Theorem: The class of Fortran machines corresponds to the class of Turing machines.

OK.

(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).

It depends of the context, but you can prove it without Church's thesis.

Theorem: There exist formalisable processes that aren't simulable by Turing machines. Such processes are called hypermachines. See Toby Ord, math.LO/0209332

`It is an "obvious" consequence of Church's thesis. See the`

`"diagonalisation posts" in my url.`

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.

`OK. I even pretend it is provably false with comp. You cannot simulate`

`a priori all 1-person continuations generated by the UD in one stroke,`

`as the first person lives it from his point of view given that the`

`first person is unaware of the number of steps the UD computes to get`

`at it, in its dovetailing way.`

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.

I don't understand.

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)

OK. Without computable means: random oracle makes them more powerfull. (Kurtz and Smith).

So, no I don't think the Turing thesis is needed for a universal machine.

I still disagree. I will say more but I have a meeting now. Bruno http://iridia.ulb.ac.be/~marchal/