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:11 GMT

In sci.logic, |-|erc
<H@r.c>
 wrote
on Sun, 30 Jan 2005 18:07:37 +1000
<363j11F4q24rcU1@individual.net>:
> "The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote
>> >> omega_U = sum(n) ( ( Halts(f(n)) ? 1 : 0) * 2^bitsize(f(n)) )
>> >
>> > Say the halt sequence is
>> >
>> > 001001001001001001001
>> >
>> > what value does your formula give, for some rudimentary bitsize function?
>> >
>> > Herc
>> >
>>
>> I don't know. I don't have the specifics handy at this point.
>> This is one of the problems I have with Mr. Weisstein's
>> definition; it's not quite specific enough. (He does give
>> a reference to Sloane's papers, whoever Mr. Sloane is;
>> I can't say I'm familiar with them.)
>>
>> I can define (and have defined) ad hoc machine specifications
>> in the past; whether these lead to consistent definitions
>> for Omega_U, I for one do not know, although I doubt it.
>>
>> Not that it matters. If Omega_U depends on the halting
>> function, then Omega_U is inherently uncomputable, as
>> the halting function is uncomputable (though it is well-defined).
>>
>> If you want I can exhume my machine definition (or make one
>> comparable thereto), and then try to compute Omega_U
>> for that machine definition. I'm not sure what that would
>> prove, if anything.
>>
>
> I gave you the initial segment of the values of Halt.
>
> HaltU(1) = 0
> HaltU(2) = 0
> HaltU(3) = 1
> HaltU(4) = 0
> HaltU(5) = 0
> HaltU(6) = 1
> ...
>
> omega_U = sum(n) ( ( Halts(f(n)) ? 1 : 0) * 2^bitsize(f(n)) )
>
> What more do you need to plug it in?
>
> Herc
>

If HaltU(n) = (n % 3 == 0) ? 1 : 0, then
it depends on bitsize. Assuming bitsize = ceil(log2(n)),
then omega_U = infinity.

This is not in error although one might question the assumptions. 

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

Relevant Pages