Algorithmic information theory and undecidability (Q5926254)

Chaitin has proven that the halting probability \(\Omega=\sum\{2^{-|p|}\mid p\text{\;halts}\}\) of a universal Turing machine is not computable, and, moreover, that any recursively axiomatizable theory enables us to determine only finitely many digits of \(\Omega\). These interesting results have led to a lot of mathematical-sounding philosophical statements. The author shows that some of these statements, if interpreted literally, are actually false. For example, it is sometimes claimed that the non-computability of \(\Omega\) is stronger than the known result about the undecidability of a halting problem. In reality, these problems are reducible to each other: if we can solve the halting problem, then we can easily compute \(\Omega\) and vice versa. It is also sometimes claimed that the number of digits of \(\Omega\) determined by a theory can be used as a measure of this theory's complexity. The author gives a counterexample: an intuitively simple theory that determines many digits of \(\Omega\).