Chaitin's Omega
wikipedia :
"a construction by Gregory Chaitin which describes
the probability that a randomly generated program
for a given model of computation will halt."
Definition
- Pick a specific universal Turing machine Uand an encoding of machines and bits (0,1) L = with the property that no element of L isthe prefix of another element.
- This is sometimes called "Huffman coding",and amounts to the fact that if say "00111" is in L,then no other word in L is "00111...".)
- It can be shown thatyou can always adapt an encoding to have this property, andyou need this to make the sum defined below converge.
- Let P be the set of all elements of L which halt,and let |p| be the length of any p in P. ThenΩ can be defined as
Notes
It can be shown that Ω is a real number between 0 and 1
which is the probability that a randomly produced bit string
encodes a halting program.
