One question is of course if there is any value in attempting to estimate uncomputable
objects such as Ω numbers or uncomputable functions such as the Busy Beaver functions
that we saw in the last unit that were also uncomputable.
We will see that we have found them a use that no one thought possible but to answer
in a more general fashion let's take an extreme position.
Let's say that we had all the digits of an Ω number, how would it be useful?
Well, we would have the exact halting time for every possible computer program, because
even though Ω depends on the choice of Turing machine we also know that, because Turing
universality, any universal Turing machine used to calculate Ω also calculate all the
computer programs of the programs enumerated by any other universal Turing machine.
In other words, having access to the infinite digits of Ω does not only give us the Halting
probability of a universal Turing machine, but in some fundamental way it gives us access
to all of them, and under the Church-Turing thesis it also means that we have access to
basic knowledge about all the computer programs that are possible.
And computer programs can be anything, from a simulation of our solar system to the answer
of any mathematical problem, including those for which we would know there is no answer
if the computer program that encodes such problem will never halt.
This is why the Ω number is also known as the infinite wisdom number.
It is similar to Jorge Luis Borges' infinite library where you had
all possible knowledge.
However, it is also of a very different nature to the books contained in Borges infinite
library, because in Borges library, if you remember his short story, books can be conceived
as having all possible permutations of letters or words but here we only have those permutations
that have computational content, that are the result of a computation and so it is a
more meaningful subset of all possible statistical combinations.
In other words, if you were given the choice to look into an infinite library either containing
an infinite number of books from all possible permutations of words and letters or an infinite
library with all possible computer programs you should definitely get into the library
of infinite computer programs as you would more easily find answers to questions such
as Fermat's last theorem.
Also notice how knowing the Busy Beaver values that we explored in the previous unit would
also give us information of the halting probability because it would tell us that for certain
computer program size we can decide whether they will halt or not and then calculate some
digits of Ω, so hopefully you are seeing how everything starts to get connected.
A different question is of course how to know which program is which, and which program
encodes the question we want Chaitin's Ω to answer.
However, you already know that short computer programs encode most of the meaningful objects
that we care about, such as the mathematical constant pi, compared to arbitrarily long
programs, because arbitrarily long computer programs relative to their output may be encoding
random objects that may be good applications for pseudo-random generation useful in a casino
and not much else.
So by looking at the length of computer programs relative to what they produce you may have
some sort of hint as to what they may be encoding to look for interesting questions and answers.
Now you may start seeing how algorithmic complexity is deeply related to knowledge and meaning
in a very profound manner and very different to the way in which computation is often portrayed
as incapable to deal with deep questions about meaning and epistemology, specially as if
these concepts were trivial generalisations of classical information theory, which they
are not, because Shannon entropy is missing the most important ingredient, precisely the
concept of computation.
But we also saw how even Shannon entropy itself is related to meaning even if in simpler ways.
One could think of having access to any digit of a Chaitin Ω number in finite time as
having access to some sort of oracle, because one can always formulate questions in terms
of whether a computer program will halt with only yes and no questions that Chaitin's Ω
would be able to answer.
In fact, one would have the answers to all mathematical questions including simulations
of real-world phenomena.
In some way, the Chaitin Ω oracle is of similar nature to the computer Deep Thought
in Douglas Adams's story The Hitchhiker's Guide to the Galaxy.
In a fundamental way asking questions using the Chaitin Ω number is like the asking
Deep Thought the Ultimate Question of Life, the Universe, and Everything.
Just as Deep Thought, Chaitin's Ω number holds all answers for all questions but we
would still need to figure out how to formulate those answers correctly.
But just as in this science fiction story where the computer Deep Thought gave the answer
"42" to the ultimate question, any answer given by a Chaitin Ω number would be hard
to understand and, in principle, impossible to follow by mechanic computation.
And again, just like in Adams's story, one would need to rely on another more powerful
computer to verify the answer, which in turn may provide a more puzzling and impossible-to-follow
answer.
This is at the heart of Godel's and Turing's proofs of degrees of undecidability and uncomputability.
However, only knowing the first n bits of Ω would enable us to decide whether or not
each program up to n bits in length ever halts, so knowing all digits would enable you to
decide the halting problem of all possible computer programs but even knowing a few bits
would give us a lot of power.
For example, Calude himself has found how large the computer programs would need to
be to solve mathematical problems such as Riemann's hypothesis and Golbach's conjecture
to mention two famous problems.
When thinking of Chaitin's Ω in terms of a wisdom number containing infinite knowledge,
including the answers to all questions that can be formulated as a computer program (e.g.
all open mathematical problems and more), it is very interesting to find out that the
digits of Ω are unattainable and incompressible, meaning that there are no shortcuts to reach
that knowledge.
No process can overrun Ω because it cannot be derived by any means simpler than the sequence
of bits in Ω itself.
That doesn't mean one cannot calculate a few digits of Ω for a number of cases.
For example, if we knew that computer programs 0, 10 and 110 all halt (notice they
are prefix-free), then we would know that the first digits of Ω are 0.111, which in
turn, if we had started with 0.111 from this Ω number, we would know that the programs
0, 10 and 110 halt.
In this sense, Ω encodes and maximally "compresses" the information of the halting state of all
possible computer programs.
Therefore, by knowing Chaitin's Ω one could solve the halting problem but knowing Chaitin's
Ω we also know how to compress all possible programs and so because Chaitin's Ω cannot
be further compressed then it is also algorithmic random.