Re: Turing vs math

From: Marchal <marchal.domain.name.hidden>
Date: Mon Nov 8 03:48:04 1999

Hal Finney wrote:

>Marchal <marchal.domain.name.hidden> writes:
>> Step n owns 2^(n-1) initial segments.
>>
>> Now, could you give me a bitstring which is not generated
>> by this countably infinite process ?
>
>Are you familiar with Cantor's diagonalization argument which proves that
>the real numbers are greater in cardinality than the integers? It
>directly disproves your statement.
>
>The real number 2/3, = .10101010... is never output by your procedure.
>If you disagree, tell me at what step it is output.

Gosh! Please Hal, I have explicitely explained how and why my
procedure cannot be disproved by Cantor diagonalisation, nor does
my procedure contradicts the uncountability of the reals.
I have also explicitely said that I don't ask for ma procedure to
output the reals at some step. (but that is the case for any
procedure giving the complete expansion of a real!).
What I say is that the UD generates the entire decimal or binary
expansion of all the real: 2/3, = .10101010... is generated at
the first, second, third, ... steps.
Note that any procedure outputing the expansion of a real does that.
The fact is that my procedure generates also non-computable reals.
There is no contradiction with diagonalisation, because at each step
the procedure generates a set of decimal expansion and I don't
provide (and I cannot provide!) a way to pick a particular
expansion as the one being the expansion of a non computable real.

Exemple:

Suppose for simplicity that 0.00010110011110110... is the binary
expansion of an uncomputable real (like Chaitin's number for exemple).
The my procedure generates, 0,at the first step 00, at the second
(among 01,10,11), 000 at the third step (among the 8 others),
and so one.

What I am saying is incredibly trivial, even if it looks a little
paradoxical.
You know, I can write a procedure which gives me with
certainty the answer for any well defined mathematical question.
It looks crazy? Take the question ``is Goldbach conjecture
true or false"?

Here is my procedure: generate the set {true, false}. I know that
the answer is in the set. Of course I don't know which one it is
but I have never been pretending knowing that.

In the same way, it is easy to realise that during his infinite
running the UD generates the binary expansion of each reals
including the non-computable one. (Exercice: show that any attempt
to build a LIST of all the reals using my procedure will fail. Hint:
diagonalisation!).

NOW, the important and perhaps less trivial point is the following one:

1) With comp we survive self-duplication (at a unknown level!, but here
I will not insist although it is fundamental in other part of the proof).

2) From the first person point of views the delays of virtual
reconstitution in the UD does not change the way of quantifying the
indeterminism.

SO we must take the generation of non computable reals into account
in the search for a measure on the computational histories.

Bruno

PS 1) I send this message friday. For obscur reasons it has not been
send as I discover in the archive. Does someone knows if something
happens friday with the mailing list ?
Received on Mon Nov 08 1999 - 03:48:04 PST