Prev: higher-order logic
Next: Name the thesis: "Formal sentences capture informal ones"
From: |-|erc on 29 Jan 2005 01:05
http://mathworld.wolfram.com/ChaitinsConstant.html
o = sum 2^(-|p|)
(p halts)

|p| is the size in bits of program p.

Note: if ALL programs halt,

2 programs of size 1
4 programs of size 2
8 programs of size 3

omega = 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 ..
omega = 1 + 1 + 1 ..

If he actually meant to make a probability he should have used

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

If all programs halt, you get a probability value to reflect this.

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

Remember this historic moment here... www.tinyurl.com/4jpxl

Herc
--
Throw away the chicken salad, and put a KNIFE
on the bread, and look at the sandwich as you butter it!
I don't need the chicken salad John!


From: r.e.s. on 29 Jan 2005 03:01
"|-|erc" <H(a)r.c> wrote ...
> http://mathworld.wolfram.com/ChaitinsConstant.html
> o = sum 2^(-|p|)
> (p halts)
>
> |p| is the size in bits of program p.


That page does not make it clear that 'p halts' is w.r.t.
Chaitin's particular UTM -- about the UTM, it says only
that it's "a universal Turing machine". But a crucial
aspect of Chaitin's UTM is that its domain is prefix-free
-- otherwise the sum won't make sense (which is what you
seem to have discovered).

--r.e.s.


> Note: if ALL programs halt,
>
> 2 programs of size 1
> 4 programs of size 2
> 8 programs of size 3
>
> omega = 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 +
> 1/8 + 1/8 + 1/8 ..
> omega = 1 + 1 + 1 ..
>
> If he actually meant to make a probability he should have used
>
> Herc's Omega = sum (p halts) 2^ -2|p|
>
> If all programs halt, you get a probability value to reflect this.
>
> Omega = 1/4 + 1/4 + 1/16 + 1/16 + 1/16 + 1/16 + 1/64 + 1/64 ...
> = 1/2 + 1/4 + 1/8 ...
> = 1

From: David Bernier on 29 Jan 2005 05:26
|-|erc wrote:
> http://mathworld.wolfram.com/ChaitinsConstant.html
> o = sum 2^(-|p|)
> (p halts)
>
> |p| is the size in bits of program p.
>
> Note: if ALL programs halt,
>
> 2 programs of size 1
> 4 programs of size 2
> 8 programs of size 3
>
> omega = 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 ..
> omega = 1 + 1 + 1 ..
>
> If he actually meant to make a probability he should have used
[...]

Programs can't have two or more different sizes.

David Bernier
From: |-|erc on 29 Jan 2005 05:45
"r.e.s." <r.s(a)ZZmindspring.com> wrote in
> "|-|erc" <H(a)r.c> wrote ...
> > http://mathworld.wolfram.com/ChaitinsConstant.html
> > o = sum 2^(-|p|)
> > (p halts)
> >
> > |p| is the size in bits of program p.
>
>
> That page does not make it clear that 'p halts' is w.r.t.
> Chaitin's particular UTM -- about the UTM, it says only
> that it's "a universal Turing machine". But a crucial
> aspect of Chaitin's UTM is that its domain is prefix-free
> -- otherwise the sum won't make sense (which is what you
> seem to have discovered).
>
> --r.e.s.

That's not an issue for most topics on UTMs, UTM in standard usage means
'for a particular UTM'. Few problems involve multiple simultaneous UTMs
that it has to be clarified.

To define it for a given UTM is ignoring the fact that there are other Omegas, except
by his usage of the notation Ou suggests another real Oz for UTM 'z'. But this
isn't omega-z, omega is Ou.

The error is whether it is a single probability.

If p ranges over the naturals for each unary parameter of UTM, then

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

To find the probability a given program f halts (for its size)
p must range from 2^floor(log-2(f+1))-1 to 2^(floor(log-2(f+1)+1))-2 for Omega to return a value between 0 and 1.

This gives a SEQUENCE OF PROBABILITIES

O1 = 0.5 p=1, p=2 SIZE 1 2 programs
O2 = 0.25 p=3...p=6 SIZE 2 4 programs
O3 = 0.75 p=7..p=14
O4 = 0 p=15...p=30
O5 = 1 p=31...p=62
O6 = 0.5 p=63..p=126 SIZE 6 64 programs
....

There is no real number probability Omega. Omega (All programs) = oo.

This is because if even a tiny percentage of large programs halt they will contribute
numbers much greater than 1 to Omega even for relatively few program sizes.

Program Size = 10 bits, program numbers 1023..2048

If 1% of these programs halt, then
Omega(10) = 1/2^10 *10 = 1%.

So Omega the single real number will be ATLEAST 1%, because 1% of programs
of size 10 halt.

Consider programs of size 1000 to size 2000 bits.

With 1% halt rate,

Omega > 0.01*1000

Omega > 10.

We have only summed over small programs up to 2KB, with only 1% halting.
Omega is already over 10, and it is supposed to be a probability??

If ALL programs halt

2 programs of size 1
4 programs of size 2
8 programs of size 3

omega = 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 ..
omega = 1 + 1 + 1 ..

If he actually meant to make a probability he should have used

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

If all programs halt, you get a probability value to reflect this.

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

Herc



From: r.e.s. on 29 Jan 2005 08:51
"|-|erc" <H(a)r.c> wrote ...
> "r.e.s." <r.s(a)ZZmindspring.com> wrote in
>> "|-|erc" <H(a)r.c> wrote ...
>> > http://mathworld.wolfram.com/ChaitinsConstant.html
>> > o = sum 2^(-|p|)
>> > (p halts)
>> >
>> > |p| is the size in bits of program p.
>>
>>
>> That page does not make it clear that 'p halts' is w.r.t.
>> Chaitin's particular UTM -- about the UTM, it says only
>> that it's "a universal Turing machine". But a crucial
>> aspect of Chaitin's UTM is that its domain is prefix-free
>> -- otherwise the sum won't make sense (which is what you
>> seem to have discovered).
>>
>> --r.e.s.
>
> That's not an issue for most topics on UTMs, UTM in standard usage means
> 'for a particular UTM'. Few problems involve multiple simultaneous UTMs
> that it has to be clarified.
-snip-

The UTM must have a prefix-free domain -- by not taking this
into account, your definition of Omega is incorrect. The
remainder of your posting is based on an _incorrect definition_.

--r.e.s.
 |  Next  |  Last
Pages: 1 2 3 4
Prev: higher-order logic
Next: Name the thesis: "Formal sentences capture informal ones"