Aside from being a word that would be an excellent name for a rock band....

Consider the halting problem, posed by Alan Turing in regards to his own imagined Turing machine. No matter what program you feed into a Turing machine, it's impossible to compute in advance whether or not that machine will ever finish its task. You can only run the program and see whether or not it finishes, although you must understand it may take a billion years to do so. The question of whether or not the program will end is uncomputable.

In the 1960s Gregory Chaitin took up the halting problem from a standpoint of probability: What are the odds that a given Turing program, chosen at random from all possible Turing programs, will halt? This probability is a real number between zero and one, and Chaitin called it Omega (with a capital "O"). In binary, Omega represents itself as an unending and random string of 0s and 1s, as transcendental and unpatterned as pi or e -- but unlike those two famous numbers, Omega is as uncomputable as the halting problem.

But imagine that the halting problem could be solved. To solve it, you'd need a super-computer of infinite scope which could calculate whether a given Turing program will halt. Armed with this knowledge, it could also compute Omega. But how long would it take to make that computation? Could it make that computation in a finite amount of time? The probability of this would be a new Omega-like number, call it Omega' (say "Omega-prime").

Now imagine the computer you would need to compute the answer to the halting problem for that super-computer, and so compute Omega'. That computer has its own halting problem and a new probability, Omega'' ("Omega-double-prime"). And so on and so on ad infinitum. This unending series of Omega-like numbers is what Chaitin calls the "Super-Omegas".

These numbers would just be another mathematical novelty if they didn't have any relevance outside of these hypothetical situations. But it turns out they do. Many computer programs can produce an infinite amount of output using infinite computations -- your web browser, for example, can display an infinite variety of web pages. What is the probability that a given infinite computation will produce a finite amount of output? The answer, it turns out, is Omega'. And the probability that an infinite computation will fail to produce any output at all is Omega''.

Extracted and summarized from "The Omega Man" in New Scientist magazine, March 10, 2001

Log in or register to write something here or to contact authors.