My claim on Omega's defn

From: |-|erc (H_at_r.c)
Date: 01/30/05 

Date: Sun, 30 Jan 2005 16:11:13 +1000

Omega = sum( p halts) 1 / (2 ^ size(p))

Program Size
1 1
2 1
3 2
4 2
5 3
6 3
7 3
8 3
9 4
..

If all programs halt

Omega = 1/2 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/16..

= 1 + 1/2 + 1/2 + 1/2 ...
= oo

Say there is a fixed constant for which this fraction of programs halt.

Let the percentage of programs that halt be 0.01%.

Omega = Omega(|p|=1) + Omega(|p|=2) + Omega(|p|=3) + ...

Omega(|p|=3) is half the probability that a program of size 3 will halt.

There are 4 programs of size 3, p = 5, 6, 7, 8.

If one of them halts then

Omega(|p|=3) = 1 / (2 ^ 3) = 1/8.

i.e. 25% of programs halt of size 3.

consider Omega(|p|=1,000,001) + Omega(|p|=1,000,002) + ... + Omega(|p|=2,000,000)

If on average 0.01% of programs halt, then each term is 1/2 * 0.01% = 0.00005.

there are a million terms, so Omega is greater than 1,000,000 * 0.00005 = 50.

Even with infinitesimally small total probability of halting, Omega will not converge and will equal oo.

------------------------------------------------------------------------------

Now try the modified Omega.

If all programs halt

Omega' = 1/4 + 1/4 + 1/16 + 1/16 + 1/64 +1/64 + 1/64 + 1/64 + 1/256 + ..
= 1/4 + 1/4 + 1/8 + 1/16 + 1/32...
= 0.75

You could dissalow the 1st program, 0, so it adds to 1.

Omega' = sum (p halts) 2 ^ (-2 |p| )
Herc

Relevant Pages

  • My claim on Omegas defn
    ... Say there is a fixed constant for which this fraction of programs halt. ... Even with infinitesimally small total probability of halting, Omega will not converge and will equal oo. ... Now try the modified Omega. ...
    (sci.math)
  • My claim on Omegas defn
    ... Say there is a fixed constant for which this fraction of programs halt. ... Even with infinitesimally small total probability of halting, Omega will not converge and will equal oo. ... Now try the modified Omega. ...
    (comp.theory)
Loading