Chaitin's constant is a real number, represented by Ω (capital Omega) and also known as the Halting probability, whose digits are distributed so randomly that no attempt to find a rule for predicting them can ever be found. Discovered by Gregory Chaitin, Ω is definable but not computable. It has no pattern or structure to it whatsoever, but consists instead of an infinitely long string of 0's and 1's in which each digit is as unrelated to its predecessor as one coin toss is from the next. Although called a constant, it is not a constant in the sense that, for example, pi is, since its definition depends on the arbitrary choice of computation model and programming language. For each such model or language, Ω is the probability that a randomly produced string will represent a program that, when run, will eventually halt. To derive it, Chaitin considered all the possible programs that a hypothetical computer known as a Turing machine could run, and then looked for the probability that a program, chosen at random from among all the possible programs, will halt. The work took him nearly 20 years, but he eventually showed that this halting probability turns Turing's question of whether a program halts into a real number, somewhere between 0 and 1. Further, he showed that, just as there are no computable instructions for determining in advance whether a computer will halt, there are also no instructions for determining the digits of Ω. Ω is uncomputable and unknowable: we don't know its value for any programming language and we never will. This is extraordinary enough in itself, but Chaitin has found that Ω infects the whole of mathematics, placing fundamental limits on what we can know.

 

And Ω is just the beginning. There are more disturbing numbers – super-Omegas – whose degree of randomness is vastly greater even than that of Ω. If there were an omnipotent computer that could solve the halting problem and evaluate Ω, this mega-brain would have its own unknowable halting probability called Ω'. And if there were a still more God-like machine that could find Ω', its halting probability would be Ω". These higher Ωs, it has been recently discovered, are not meaningless abstractions. Ω', for instance, gives the probability that an infinite computation produces only a finite amount of output. Ω" is equivalent to the probability that, during an infinite computation, a computer will fail to produce an output – for example, get no result from a computation and move on to the next one – and that it will do this only a finite number of times. Ω and the Ω hierarchy are revealing to mathematicians an unsettling truth: the problems that we can hope ever to solve form a tiny archipelago in a vast ocean of undecidability.

 

Chaitin, Gregory (1947–)

Gregory Chaitin is an American mathematician and computer scientist at IBM's T. J. Watson Research Center who is the chief architect of a new subject known as algorithmic information theory, which has profound consequences for our ideas about randomness. In particular, because of the limitations of computers and the programs they run, Chaitin has shown that there is an inherent uncertainty or unknowability in mathematics that is similar to the uncertainty principle in physics. Although there are an infinite number of mathematical facts, they are, for the most part, unrelated to each other and impossible to tie together with unifying theorems. His powerful message is that most of mathematics is true for no particular reason: math is true by accident.