Re: Turing vs math

From: Marchal <marchal.domain.name.hidden>
Date: Thu Nov 4 02:10:15 1999

Juergen Schmidhuber wrote:

> Bruno:
> In countably infinite time you can compute an
> entire real, but not all reals.

It depend by what you mean by computing a set. But here
we are discussing words.

What I say is just this: throughout his countably infinite
execution the UD generates all the reals, or let us say, all
the infinite sequence of bits (for the sake of simplicity).

Step 1
0

Step 2
0
1

Step 3
00
01
10
11

Step 4
000
001
010
011
100
101
110
111

Step 5, ...

Step n owns 2^(n-1) initial segments.

Now, could you give me a bitstring which is not generated
by this countably infinite process ?

I doubt it !

It is more easy to show that any bitstring will be generated
through that process. For exemple the 1 billion length initial
segment of (a) Chaitin number (a well known uncomputable real)
will appear at the 1 billion + 1 step. Of course it will be
among 2^(1 billion + 1) other initial segments and I don't
pretend I can provably isolate it. But this change nothing
in my reasonning.

There is no contradiction with the uncountability of the reals,
nor with the facts that most real are uncomputable !
The reason is that for a real to be computable it needs in some
way to be distinguish from other reals, and that need not
to happen with the generation of all the reals.

Bruno
Received on Thu Nov 04 1999 - 02:10:15 PST