Re: Turing vs math

From: Marchal <marchal.domain.name.hidden>
Date: Tue Nov 2 03:28:17 1999

Juergen Schmidhuber:

> Even the set of all real #'s is not formally describable. You cannot
> write a program that lists all reals. In infinite but countable time
> you can write down a particular computable real, but not all reals.

I don't agree. Indeed, you cannot write a program that lists all reals.
But in infinite and still countable time you can write down all the reals,
by dovetailing on all initial segment of all the reals, including
non computable one.

                  0.0 0.1
            0.00 0.01 0.10 0.11
       0.000 0.001 0.010 0.011 0.100 0.101 0.110 0.111
                 etc. etc.

There is of course no contradiction with the fact that most of the reals
are uncomputable, and that the set of reals is uncountable.


Hal Finney:

>What about the fact, which I mentioned earlier, that probabilities are
>based on Kolmogorov complexity, but that is uncomputable, or at least
>it would require a super-TM to compute it. However we do observe
>probabilities and their effects, hence K. complexity is being computed,
>hence there must be a super-TM somewhere to compute it.

The fact that we do observe things does not entail that these things are
computable. With COMP it is even provable that there is non-computable
observable phenomena.

Take the self-duplication experiment as a simple illustration, where
after having been read I am reconstitued at two different places.
Nobody (not even God) can compute where I will find myself after the
duplication.

Bruno
Received on Tue Nov 02 1999 - 03:28:17 PST