Re: Raatikainen's critique of Chaitin

From: Eray Ozkural exa (erayo_at_bilkent.edu.tr)
Date: 09/01/04 

Date: 1 Sep 2004 00:32:07 -0700

Torkel Franzen <torkel@sm.luth.se> wrote in message news:<vcb8ybvfmpx.fsf@beta19.sm.ltu.se>...
> erayo@bilkent.edu.tr (Eray Ozkural exa) writes:
>
> > 1. The halting problem's structure is random, it cannot be attributed
> > to mechanical causes less complex than itself (by the very definition
> > of randomness), in this case infinite complexity.
>
> What does this mean?

Omega can be said to represent halting problem's structure
(minimally), because given first n bits of Omega, you can compute all
n-bit programs that halt.

Here is a definition of randomness in Kolmogorov complexity:
 
A sequence x0x1x2... is Martin-Lof random if and only if there exists
some constant c such that
  KP(x0x1x2...x_{n-1}) >= n-c

(From Alexander Shen's lectures)

where KP(x,y) is the prefix complexity of a pair. The definition in
Chaitin, AIT is different:

A real r is Chaitin random if the information content of the initial
segment r_n of length n of the base-two representation of r eventually
becomes and remains arbitrarily greater than n: lim H(r_n) - n =
infinity.

Omega is Chaitin random. Terefore, its information content is
(countably!) infinite. It cannot be computed by a program less complex
than infinite.

It can be computed *in the limit* by a small program, but that is not
what we mean. The infinity in program size is then transferred to an
infinity in time, philosophically we don't gain much.

If we accept that a discrete computer is an adequate formalization of
"mechanism" in this universe (e.g. there are no machines that cannot
be simulated by a universal discrete computer), *then* it follows that
the structure of the halting problem cannot have been constructed by
finite mechanisms. [*]

Then, this structure cannot be attributed to finite mechanical causes
(ie. computation), such as the causes in the entire history of our
physical universe.

All of this explanation was of course essentially present in my post.
 
> > 3. Therefore, the bits of Omega are true for no mechanical cause
> > (reason) in this universe.
>
> What is meant by a bit being true?

That they attain particular 0 or 1 values according to which programs
halt. (Correspondence) Maybe, you are pointing out to the realist
tendencies in this sentence?

Yes, we seem to be first defining something, and then defining its
truth in terms of this definition. But you have snipped a large part
of my post, possibly because you do not really care, which contained
the answer to your question: the bits of Omega are true in answer to a
question in number theory.

So it is really more advanced than a hypothetical definition hanging
in the air:
-------------------------------------------
Theorem D
  There is an exponential diophantine equation

  L(n,x_1, ..., x_m) = R(n, x_1, ..., x_m)

which has only finitely many solutions x_1, ..., x_m if the nth bit of
Omega is a 0, and which has infinitely many solutions x1, ..., x_m if
the nth bit of Omega is a 1.
....
---------------------------------------------

Like Godel, Chaitin proves the existence of a new kind of
incompleteness in the foundations of mathematics. Without this
existence proof, the "truth of bits of Omega" would not make much
sense, other than having been designated by a definition. Here,
however, we see that it can be encoded as an algebraic equation in
integers.

If we take a realist approach to mathematics, there is no difficulty
in believing that Omega exists, if you also believe that 3 exists in
solution to 1 + x = 4. As I have indicated, however, this may not be
the case if we abandon Platonism.

Regards, 

--
Eray Ozkural
[*] Note that this is an answer to one of the major questions asked in
the Gibbs lecture!

Relevant Pages

  • Re: Raatikainens critique of Chaitin
    ... in this case infinite complexity. ... Omega can be said to represent halting problem's structure ... Here is a definition of randomness in Kolmogorov complexity: ... A real r is Chaitin random if the information content of the initial ...
    (comp.theory)
  • Re: Uncountability of the Rationals?
    ... My rules don't say such a set doesn't exist - all countably infinite ... The set omega still exists and is the ... TO intends his ICI ... TO states that "tav" could represent any set, ...
    (sci.math)
  • Re: Cantor Confusion
    ... And the number of digits is omega. ... why I insist that an actually infinite set of natural numbers must ... If your axiom contradicts this, ...
    (sci.math)
  • Re: Galileos Paradox
    ... He uses the assumption that any infinite number can have a finite number ... is NOT talking about ordinals such as omega. ... includes not just first order logic). ... at the ultrafilter approaches - all in classical mathematics. ...
    (sci.math)
  • Re: infinity
    ... >> If by omega you mean the smallest infinite cardinal (usually referred ... that given a finite set, you can count it by singing a ditty, and using ... Suppose the attempt to sing the ditty never stops - in that case ... >> creates an infinite element, ...
    (sci.math)