## Chaitin's ConstantA 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. ## Related category• NOTABLE NUMBERS | |||||

Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact |