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.
> >
> >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.
>
I think it was by Turing actually. Its been a while since I read the
original article though, so I'm not certain.
>
> >
> >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).
>
> >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.
>
> >
> >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.
> Bruno
>
> http://iridia.ulb.ac.be/~marchal/
--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.
----------------------------------------------------------------------------
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics 0425 253119 (")
UNSW SYDNEY 2052 R.Standish.domain.name.hidden
Australia http://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
----------------------------------------------------------------------------
- application/pgp-signature attachment: stored
Received on Tue Jun 21 2005 - 19:43:18 PDT