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

In sci.logic, |-|erc
<H@r.c>
 wrote
on Mon, 31 Jan 2005 11:09:15 +1000
<365esmF4tbqqlU1@individual.net>:
> "The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote
>> >> then omega_U = infinity.
>> >>
>> >> This is not in error although one might question the assumptions.
>> >>
>> >
>> > why is it not an error?
>>
>> Because it is not. Given your assumptions and the computation
>> given of bitsize, it's a foregone conclusion.
>
> Are probabilities allowed to reach oo?

Probabilities are confined to the closed interval [0,1].

>
>
>>
>> > why are u adding exponential sums?
>>
>> The issue is similar to the harmonic series, and diverges for much
>> the same reason. If bitsize(x) = n then x must be between
>> 2^n (inclusive) and 2^(n+1) (exclusive), which gives 2^n - 1
>> numbers to play with, each of weight 2^(-n). The factor
>> is therefore (1 - 1/2^n), and the total sum diverges without
>> bound if one includes every program, not merely the halting
>> ones (one might call that omegamax_U).
>>
>> Even if only a third of the programs halt, one still sees
>> divergence without bound.
>>
>> If you're not familiar with the harmonic series:
>>
>> Let S = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n + ...
>
>
> Your sequence is 1 + 2 + 4 + 8 + 16...
>
> For what halt values would it ever converge?

I'm not sure what you mean by "halt values", but if one
postulates that no programs halt, then of course it will
converge. Otherwise, you will have to clarify your question.

Perhaps I forgot a minus sign somewhere for K_U?

I intended it to be

    K_U = sum (all halting P) (2^(-number(P)))

where number(P) is a unique identification number for each P.

This is guaranteed to be in [0,2] (and is only not in [0,1]
if program P_0 halts; that depends on number()).

>
> Herc
> 

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

Relevant Pages

  • Re: ******** CAN ANYONE HERE DEFINE CHAITINS OMEGA ? ***********
    ... Probabilities are confined to the closed interval. ... >> The issue is similar to the harmonic series, and diverges for much ... >> Even if only a third of the programs halt, ...
    (sci.math)
  • Re: Program analysis
    ... those that provably halt, ... halt, and those that never halt but cannot be proven never to halt. ... all programs halt with the heat death of the universe. ...
    (comp.programming)