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

On Tue, Jun 21, 2005 at 07:43:49PM +0200, Bruno Marchal wrote:

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.


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 by a
Turing 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 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).


Do you have a reference? Li & Vitanyi appear to be unaware of this result.


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/


Reply via email to