Le 22-juin-05, à 01:06, Russell Standish a écrit :

## Advertising

On Tue, Jun 21, 2005 at 07:43:49PM +0200, Bruno Marchal wrote:Turing's thesis: Any process that can be naturally called aneffectiveprocedure is realized by a Turing machine.Not OK. Please give me the page.2nd edition, page 24, about 1/3 of the way down the page.

`OK. Not good for Li & Vitanyi. "Process" and "effective" have different`

`meaning in similar context. But this is just a vocabulary question. It`

`is ok given they are (still) physicalist.`

Conjecture: All "harnessable" physical processes can be simulated byaTuring machine. By harnessable, we mean exploited for performing some computation. I suspect this is true.I don't understand.Again these are intuitive concepts. I would interpret this as saying that we can perform the same computation as any physical process, even if we cannot simulate the process itself (ie the process may do something more than computation).

`There is a danger in using those "intuitive" words without making clear`

`the context.`

Could we simulate a truly random oracle with a Turing Machine?

`No, in the sense we cannot find a program which generates a provably`

`infinite random string. Yes, with comp, in the sense it is enough to`

`iterate infinitely often the self applied duplication.`

Machines with random oracles withcomputable means only compute the same class of functions as doTuringmachines. (classic result by de Leeuw et al. in 1956)OK. Without computable means: random oracle makes them more powerfull. (Kurtz and Smith).Do you have a reference? Li & Vitanyi appear to be unaware of thisresult.

Sorry it was just Kurtz:

`KURTZ S. A., 1983, On the Random Oracle Hypothesis, Information and`

`Control, 57, pp. 40-47.`

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.I look forward to that.

`By definition a Universal digital or numerical machine is a machine`

`which is able to compute all intuitively (effectively if you want)`

`computable function.`

`Church's thesis = the class of intuitively computable function is equal`

`to the class of fortran computable function. Of course Church's`

`original thesis use lambda instead of fortran!`

`From this Church's Thesis (CT) is equivalent with the statement that a`

`universal fortran machine is a universal (digital) machine. The`

`reciprocal being obvious.`

`So CT = There exists a Universal Machine. (I always mean Universal`

`*digital* machine).`

Bruno http://iridia.ulb.ac.be/~marchal/