Halting Probability Omega

This post is also available in: Spanish

Halting probability Omega

The halting probability Omega is a number invented by the mathematician Gregory Chaitin. It expresses the probability that some program taken at random from the space of all possible programs will stop.

Omega has some properties that make it one of the most fascinating numbers in mathematics. Firstly, it contains every mathematical truth. This is so because every single mathematical theorem can be expressed as saying whether a program will halt or not. It is possible to use the halting probability to find out whether some algorithm will halt: therefore, it is possible to use it to know if a certain proposition is true.

Second, it is not computable. Since knowing Omega would enable us to solve the halting problem and the halting problem cannot be solved, it follows that Omega cannot be computed.

Since it cannot be computed, its bits have to be absolutely random. Otherwise, they could be computed by a shorter program.

More information about Omega can be obtained at Gregory Chaitin’s homepage.

Chaitin’s paper on the Halting Probability.

Chaitin’s video lecture on Leibniz, complexity and incompleteness.

Share and Enjoy:
  • Digg
  • del.icio.us
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • Bitacoras.com
  • Google Buzz
  • Meneame
  • Reddit
  • RSS

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>