Re: ESSAY: Program length, Omega and Infinite Running Programs

From: William Pearson (
Date: Wed Mar 01 2006 - 20:32:58 MST

On 01/03/06, Philip Goetz <> wrote:
> On 2/28/06, William Pearson <> wrote:
> > With experimentation, by definition the bits of omega or equivalent
> > number are random, so knowing one bit will have no bearing on the
> > others so I wouldn't expect any improvement.
> The definition of omega says nothing about randomness, therefore the
> bits are not random by definition. I suspect you are assuming that
> the probability of one program halting is independent of the
> probability of any other program halting. This seems unlikely to me.

Okay maybe not quite by definition, but it is not far off. Take your
doubt of the randomness of Omega up with Chaitin.

"And what is the most surprising property of Omega? It's the fact that
it is irreducible, or algorithmically random, and that it is
infinitely complex."

I'll grant you there might be patterns within subsets of omega, but
within the whole thing I doubt it.

By this I mean I can see why the function X+1 would halt in the same
way that the function X+2 would up to X+infinity. But I don't see why,
whether word crashes or not should have anything to do with whether a
linux kernel panics.

A side note I found Verónica Becher's homepage with analogues of
kolmogorov complexity and omega for infinite running programs.

>Can you give a more precise statement, such as one would see at the
>beginning of a proof?

 I will have to give the becher papers a look before I state the exact
thing I wish to prove because I am not entirely sure of how to
formulate infinite programs at the moment. I also want to precisely
formulate what sort of change of program I am interested in. Ideally I
am looking for something that captures the idea of a change in
functionality so that the self-improved program can be said to be

  Will Pearson

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:56 MDT