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

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

Date: Mon, 31 Jan 2005 04:00:10 GMT

In sci.logic, r.e.s.
<r.s@ZZmindspring.com>
 wrote
on Mon, 31 Jan 2005 01:57:46 GMT
<uggLd.2186$Nn1.672@newsread1.news.pas.earthlink.net>:
> "The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote ...
>> <H@r.c> wrote ...
>
>>> So you CANNOT define Omega then?
>>>
>>> NOBODY IN SCI.MATH CAN DEFINE OMEGA!!!
>
>> You win this round. Congratulations!
>
> A correct definition has been given many times in
> multiple threads -- it's a mystery to me why Herc won't
> admit it. And it's equally mysterious why you encourage
> his delusions.

Perhaps I encourage his delusions because I'm looking for
the grain of truth therein. With luck, I might find it --
but it's a struggle, believe me. :-) Especially since
he can't seem to swim in the continuum and gets bogged
down in the denumerability/computability area. (Me,
I'm comfortable in the continuum, but it's not all
that useful in the computability world. Of course
infinite isn't all that useful, either; almost all
natural numbers will never be written down -- too big
for the carbon atoms. :-) )

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. (|-|erc's assumption was
that every third program halts. This assumption, of
course, is slightly silly -- but it's a bit like primes,
except not as computable.)

But it really depends on the precise definition of numbits().

>
> Aside from my clarification of the definition at MathWorld,
> it's easy to find the definition in
> C. S. Calude, et al, "Computing a Glimpse of Randomness"
> http://www.expmath.org/expmath/volumes/11/11.3/Calude361_370.pdf
> -- which is link that has been posted many times.
>
>
>> Not that it matters all that much. I will have
>> to do some research (or perhaps some kindly soul
>> can do it for me :-) ) as to, not Chaitin's Omega,
>> but some other constant which might be described
>> as
>>
>> K_U = sum(X = Enc(all halting (P,I) pairs)) ( (2^(-X)))
>>
>> where:
>>
>> K_U is a binary constant, and
>> Enc(P,I) encodes a program/machine P with its input tape I
>> into a unique integer. (There are corresponding
>> DecProg() and DecInput() forms, complementary to Enc().)
>>
>> And just to beat this to death, assume that we have a
>> program H that can take as input Enc(P,I) and return true
>> if it halts, false if it does not.
>
> In the thread
> "Herc defines the HOLY GRAIL OF MATHEMATICS"
> I'd already explained to Herc about the problems with the
> MathWorld definition of Omega, *and* how to fix it, *and*
> provided a reference to the paper by Calude, et al, *and*
> explained differences between Omega and the quantity tau,
> which is special case of your K_U.

Tau? Heh...maybe we need to crank up SETI just so we can get
more symbols for our mathematical notation! :-)

Hello...is there anyone out there? Do you have an alphabet?
Can we borrow a few of your letters/characters/glyphs? :-)

All kidding aside, I'm not surprised someone's at least given
some thought to the matter; it's an obvious thing to have a go at.

Of course Chaitin's Constant is not that hard to fix,
and, once fixed, it has the same problem as tau, K_U,
whatever one will; it's not computable by a UTM, as
the halting problem is not determinable by a UTM.

And |-|erc can't seem to get that, either -- I'm not sure
if it's a problem in his understanding of "reducto ad absurdum"
or something deeper.

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... :-)

>
> --r.e.s. 

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

Relevant Pages
Loading