On Wed, Jun 22, 2005 at 09:25:09AM +0200, Bruno Marchal wrote:
>
>
> >>>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 - what that conjecture states is that we cannot use a random oracle
to compute something no computable on a Turing machine.
>
> No, in the sense we cannot find a program which generates a provably
> infinite random string.
How do you prove the output random? I thought it wasn't possible.
All we can say is that the output is random with measure 1.
> Yes, with comp, in the sense it is enough to
> iterate infinitely often the self applied duplication.
>
But then you can't separate out the random string (unless you are
one!), so again it is not a computation. (At least not "harnessable")
> >
> >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.
>
Thanks - I will look that up. As you probably aware I am fascinated by
this topic.
>
>
> 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/
Fair enough. Its really a harmless terminological thing. For me, we
have universal Turing machines, provably equivalent to universal
Fortran machines provably equivalent to universal partial recursive
functions etc. Since they are all the same thing under equivalence,
why not just call them universal machines. CT just adds an extra thing
the "intuitively computable" universal machine, to use your terminology.
Since I don't have an issue with the CT thesis, just its various
stronger manifestations, we are in fact talking about the same thing anyway.
Cheers
--
*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 Wed Jun 22 2005 - 18:56:19 PDT