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

From: r.e.s. (r.s_at_ZZmindspring.com)
Date: 01/30/05 

Date: Sun, 30 Jan 2005 10:09:35 GMT

"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. 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.

Relevant Pages