Re: My claim on Omega's defn

From: The Ghost In The Machine (ewill_at_sirius.athghost7038suus.net)
Date: 01/31/05 

Date: Mon, 31 Jan 2005 05:01:51 GMT

In sci.logic, |-|erc
<H@r.c>
 wrote
on Mon, 31 Jan 2005 13:54:33 +1000
<365oihF4td553U1@individual.net>:
>> >
>> >>|-|erc wrote:
>> >>
>> >>>Omega = sum( p halts) 1 / (2 ^ size(p))
>> >>>
>> >>> [big snip]
>> >>>
>> >>>Even with infinitesimally small total probability of halting, Omega will not converge and will equal oo.
>> >>
>> >>
>> >>You seem to be missing the point that the domain of the universal
>> >>self-delimiting TM U is taken to be prefix-free --- ie, the encoding of
>> >>halting TMs is such that if x is the encoding of some halting TM, then
>> >>no proper prefix of x is a encoding. Basically, any branch of the
>> >>infinite-binary tree will contain at most one such encoding, and so to
>> >>simply say that there are 2^n encoding with n bits is just being
>> >>ignorant. If follows via Kraft's inequality that Chaitin's Omega will
>> >>be bounded.
>> >
>> >
>> > So all Omega means is there exists 1 program of that size that halts.
>>
>> No, what it does mean is that the set of encodings of programs is sparse
>> (quite possibly meagre) is the space of all finite binary strings. It
>> is a perhaps unnatural condition, but its what was done to ensure that
>> the "Omega series" converges.
>>
>> > What a load of crap, I could design an arbirtrary UTM where Omega = 1.
>> >
>> > It skips 100% of programs without any reason.
>>
>> Then this number really doesn't mean anything. We could all come up
>> with our own numerical constants, but unless there's a reason for them,
>> no-one will care. It's the natural interpretation that Chaitin was able
>> to get that makes it extremely worthwhile.
>>
>
>
> the number of programs per size must be contant for Omega to converge.
> its useless.
>
> if 1 program halts per |p|, omega = 1/2 + 1/4 + 1/8 + 1/16 ... = 1
> if 2 programs halt per |p|, omega = 1/2 + 1/2 + 1/4 + 1/4 + ... = 2
>
> Its hasn't been *modified* to fix this, this error is so huge
> becuase they botched it completely.

I'm not sure this is a major problem as such; the main requirement
is that the number of programs that have a certain bitsize be
less than at most (2^bitsize) / bitsize, for large bitsize. (The
harmonic series is known to diverge.)

But it doesn't matter; if one calculates

K_U = sum(all halting P) (2^(-identifyingnumber(P)))

instead of

omega_U = sum(all halting P) (2^(-numbits(P)))

then K_U will always converge, and both are uncomputable by a UTM.

[rest snipped] 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

Relevant Pages

  • Re: My claim on Omegas defn
    ... what it does mean is that the set of encodings of programs is sparse ... >> (quite possibly meagre) is the space of all finite binary strings. ... is that the number of programs that have a certain bitsize be ...
    (sci.logic)
  • Re: My claim on Omegas defn
    ... what it does mean is that the set of encodings of programs is sparse ... >> (quite possibly meagre) is the space of all finite binary strings. ... is that the number of programs that have a certain bitsize be ...
    (sci.math)