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