Re: Raatikainen's critique of Chaitin

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

  • Next message: Eray Ozkural exa: "Re: Raatikainen's critique of Chaitin" 
    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!
  • Next message: Eray Ozkural exa: "Re: Raatikainen's critique of Chaitin"

    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 ...
      (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)
    • Re: use of real numbers in mathematics and physics
      ... with an infinite amount of information. ... ::> And this will be so in any reasonable form of physics. ... complexity and computable real numbers demonstrate that ... itself requires similarly infinite precision. ...
      (sci.physics.research)