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
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
*all* computable function, without any "turing" or "fortran"
qualification, you need Church thesis.
From Li & Vitanyi:
Church's thesis: The class of algorithmically computable numerical
functions (in the intuitive sense) coincides with the class of partial
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
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.
Theorem: The class of Fortran machines corresponds to the class of
(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
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
I still disagree. I will say more but I have a meeting now.