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/
Received on Wed Jun 22 2005 - 03:27:13 PDT