Le 21-juin-05, à 12:28, Russell Standish a écrit :
> 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 using
>>> a Turing machine (or recursive function, or equivalent). Of course
>>> the
>>> latter 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 program
>> exists. To say that a universal machine exists, computing by
>> definition
>> *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/
Received on Tue Jun 21 2005 - 13:46:06 PDT