So far we have mostly talked about finite sequences or strings but let's now momentarily
move to the subfield of algorithmic complexity that studies the algorithmic randomness of
infinite objects . One such object is the so-called halting probability number (Chaitin,
1975), also known as Chaitin's Ω (omega) number also often wrongly called a constant,
defined as follows:
where p is a computer program running on a universal Turing machine U and the sum is
a probability between 0 and 1 for computer programs running on U to halt or not.
So clearly calling Ω a constant is misleading because it depends on the choice of universal
Turing machine U and for different choices there will be a different Ω number.
However, the Turing machine has to be somehow special, a type of universal Turing machine
that is often called prefix-free Turing machine.
Let me explain you what is a prefix-free machine.
There is a special type of computer called prefix-free that has to be used for objects
such as Chaitin's Ω and is also sometimes used to define algorithmic complexity.
Its need stems from the fact that you don't want to trivially count the same program more
than once.
The problem is that it is very easy to generate an infinite number of programs as an extension
of a program.
Take the program that prints s and then prints an extra 1 at the end only to delete it before
halting.
The new program prints s, but it is only a spurious variation of a more compact program,
the number of this spurious program to produce the same output is infinite and for a measure
to be called a probability the sum of the probabilities has to be 1, it would not have
any mathematical meaning to say that something has more than 100% of chances to happen.
To circumvent this problem Leonid Levin in 1974 and then Gregory Chaitin in 1977 devised
a way to consider only significant programs according to some rule.
The rule is that new programs should never be initial subprograms of any other programs.
These types of sets are called "prefix-free domains".
A classic example is the set of telephone numbers.
The only way to reach a person by calling their telephone number is if no telephone
number is part of any other telephone number because imagine that Alice's number is 12345
and Bob's telephone number is 123, then no one could reach Alice because as soon as you
start typing her number you would be connected to Bob as soon as you finish dialing 123.
Different ways to avoid this are possible; for example, telephone numbers are all of
the same length so any other phone number of different length is not a valid telephone
number, another way is to choose a special character as an indication of a number termination.
For example, some online banking systems ask customers to use the # sign to indicate that
they have finished introducing their bank account numbers.
Prefix codes are guaranteed to exist for a countable set and the so-called Kraft, or
Kraft-Chaitin, inequality guarantees that taking the sum of all the probabilities of
the series will converge to 1, which is the necessary condition for a probability measure.
For algorithmic complexity or Kolmogorov-Chaitin complexity there are versions that can be
defined both on regular universal Turing machines and also on prefix-free Turing machines, but
they do not differ much from each other and do not dramatically affect the definition
of algorithmic complexity.
However, it does change more fundamentally this probability measure.
Coming back to the definition of Chaitin's Ω
every time that a computer program p halts it contributes to the value of Ω by determining
a binary sequence that can be seen as the binary expansion of a real number between
0 and 1 because remember this is a probability.
For example, in 2007, one of my former PhD co-advisors, Cristian Calude computed the
first 43 bits of a Chaitin Ω for a certain universal Turing machine, the first digits
of this Ω look as follows:
0.00010000000100001010011101110000111110101
The longer the program length
|p|,
the smaller contribution to Ω, so the sequence is not only very difficult to calculate for
increasing program lengths but it is also uncomputable because we know that because
of the Halting problem one can never really know which computer programs will halt, this
is why this Ω number is also called the Halting probability.
From the formula it can be seen that short programs have the greatest weight in the fraction
because the smaller the denominator gets the larger the values will be and so the shortest
computer programs contribute the most significant values of Ω.
But just as algorithmic complexity, Ω is also semi-computable, meaning that one can
estimate it by, for example, fixing a programming language framework and running random programs
just as Calude, and later myself, did also in 2007.