Re: ******** CAN ANYONE HERE DEFINE CHAITIN'S OMEGA ? ***********

From: |-|erc (H_at_r.c)
Date: 01/31/05 

Date: Mon, 31 Jan 2005 14:27:20 +1000

"The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote
>
> As it is, Chaitin's Omega has a problem in Mathworld;
> the terminology |p| is breezily described as "the size
> in bits of program p". I'll admit I'm not all that up
> on my information theory, but if p has an encoding number,
> the number of bits and the encoding number are going to
> be roughly comparable unless someone plays some wacked-
> out games with the mapping.
>
> This means that the value
>
> sum (all programs P) (2^(-numbits(P)))
>
> is not going to converge, as there will be approximately
> 2^j programs with numbits = j, if there's a 1-1 mapping
> between N and each and every program. How that correlates
> with the value
>
> sum (all halting programs P) (2^(-numbits(p)))
>
> is not all that clear to me without a highly specific
> mapping between N and P.

RIGHT! 3 days later someone else can see the defn cannot work at all.

>
> At least I think I've gotten him to finally acknowledge that
> 1/3 is not in S_3 = {.3, .33, .333, ... }. Now if I can
> get him to leap to the conclusion that
> TX_10 = {k/10^n: k,n in J, n >= 0} does not cover R... :-)
>

No, cite where I said it was in the set in the 1st place, your memory
bridged a few too many gaps by suddenly introducing that example again
after a year.

Herc

Relevant Pages