RE: Turing vs math

From: Marchal <marchal.domain.name.hidden>
Date: Tue Nov 2 07:20:24 1999

Nick Bostrom wrote:

>Bruno wrote:
>
> >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.
>
>No you've got that wrong, Bruno. The output of the process you describe is a
>countable string of reals, and it thus leaves out the vast majority of all
>real numbers. (To see that the string is countable, map it to the integers
>as follows: upper-left=1, upper-right = 2, second row-first column = 3 etc.;
>this mapping will include all entries in your listing) -- What you are
>leaving out are a lot of reals that have an infinite binary decimal
>representations.


I see what you mean. You look at the "reals" which are generated at
each step. Then, of course, I produce only rationals.

But in that case Schmidhuber generates also only rationnal approximation
of the computable real number he is generating.
I am not looking at the output of a process (nor is Schmidhuber), I am
looking at the limit of that process after a countable time.

So I insist, by admitting a countable time (not something which I get
at any step) the dovetailing on the initial segments (which of course are
just rationnals) gives a procedure dovetailing on ALL the reals.


Let me give an exemple which mainly shows the pertinence of that point
in our context.

Suppose just for the sake of the argument that *Planck constant* (or any
real constant you would like to imagine) is non computable.
And suppose also that you are a computational process using *Planck
constant* as oracle.
So I suppose that at any time you (or a subroutine of your brain)
can ask ANY decimal of *Planck Constant*. I suppose also that:
 
- in case the oracle gives you a wrong answer, you die (let us say).
- in case the oracle is correct, you survive.

Then you (1-person) are not emulable by any turing machine.

Nevertheless you will appear, infinitely often, in the UD* (the
infinite trace of the Universal Dovetailer).

Why ? Because the UD will generates all initial segments of ALL
the reals, including our uncomputable *Planck Constant*. And this
infinitely often.

The UD dovetail on all the version of you accompagnying all the reals.
you+ means you survive. The X means you will die.

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

Now remember that in the self-multiplication thought experiment
the way of quantifying the indeterminisme on the set of possible
future computational continuations doesn't depend at all of the
time the UD "reconstitute" you. In our case you will survive in
all the stories where the oracles will give you the correct answer
about Planck Constant.

So, in this (admittedly artificial case), the measure will be defined
on the branching line of the UD linked to the correct and arbitrarily
long decimals of our *Planck Constant*.

Even if at each finite steps the UD generates only things which are
codable by natural numbers, to describe the 1-point of view of an
observer you need to take account that in UD* all real numbers are
generated, altough never outputed !

I know some people find this a little paradoxical. You have the same
problem with the Chaitin's proof that no machine can provably output a
string more complex than itself. But of course this does not preclude
a machine for generating all natural numbers, including those much more
complex than itself!

The UD generates all real numbers, in a way that is not threatened
by diagonalisation, because we are not asking here to output these
reals in some kind of list.
But from the 1-point-of-view, the fact that the UD really goes through
all the reals is, as I illustrate, a key point.

Have I been a little more clearer ?

Bruno
Received on Tue Nov 02 1999 - 07:20:24 PST