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

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

Date: Sun, 30 Jan 2005 19:00:12 GMT

In sci.logic, r.e.s.
<r.s@ZZmindspring.com>
 wrote
on Sun, 30 Jan 2005 10:09:35 GMT
<zn2Ld.1747$cl1.558@newsread3.news.pas.earthlink.net>:
> "The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote ...
>> <H@r.c> wrote
>>> the subject is chaitan's constant.
>
>> Let f : N -> {TM} be a mapping from N to the set of
>> all Turing machines. Then Chaitin's Constant is simply
>>
>> omega_U = sum(n) ( ( Halts(f(n)) ? 1 : 0) * 2^bitsize(f(n)) )
>>
>> http://mathworld.wolfram.com/ChaitinsConstant.html
>>
>> where bitsize(f(n)) is "the size in bits of program f(n)",
>> and Halts(f(n)) is true if f(n) halts.
>
> No, that's not correct. Here's why ...
>
> The definition at MathWorld is incomplete to the point of
> being misleading.

Yeah, I noticed that too. :-) Then again, I didn't reference
the paper.

> The formula given there is meant only
> for a restricted type of UTM -- one whose domain (the
> set of p such that U(p) halts) is *prefix-free*. Then the
> Kraft inequality for prefix-free sets of strings guarantees
> 0 <= Omega_U <= 1. (Without the prefix-free requirement,
> summing over all programs will give nonsensical results.)
>
> This is easily confirmed by referring to the following paper
> cited by MathWorld ...
>
> [1] C. S. Calude, et al, "Computing a Glimpse of Randomness"
> http://www.expmath.org/expmath/volumes/11/11.3/Calude361_370.pdf
>
> -- r.e.s. 

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

Relevant Pages