0.007875474041752057

All About Omega

Business in Binary

Omega is a constant that concerns computer programs. If you are viewing this page, it is very obvious that you have used a computer program before. Although programs might initially strike you as very complicated things, they are really just a series of 0s and 1s. When we choose an interpreting language, it can turn these 0s and 1s into actions, pictures, and sounds.

Boiling it Down

Any given computer program does one of two things. It can halt, because it has come up with a result to output, or it will loop forever never arriving at a solution. A program that doesn't halt is a very bad thing, so programmers generally put in traps and error messages to prevent it from happening.

Halt! Who goes there?

This leads us to Turing’s famous halting problem, which was conceived by the mathematician and cryptographer Alan Turing (1912-1954). Turing also did code breaking for the British government during WWII. His halting problem asks whether there is a way to determine which programs will halt and which ones won’t.

When we run a program and it stops, we know that it halts. Simple enough. But, what if the program doesn't stop in the first 10 minutes or the first hour or even the first day? How long should we wait before we give up? If a program doesn’t halt, we would always be thinking that if we wait just a bit longer, the answer will reveal itself. Although we can determine whether a program will halt for special cases, there is no theory or algorithm that can solve the general case of which programs halt and which ones don't.

Chaitin's Constant

This brings us to the active mathematician and computer scientist Gregory Chaitin’s question. If we look at the set of all possible programs and we pick one, what is the probability that it is one that halts? Or, more precisely, what proportion of programs halt? This number is Chaitin’s constant omega.

Disclaimer

Although Chaitin’s constant depends on the programming language you are using, once you chose that language, omega has a defined and unchanging value. In addition, all the properties of omega carry over regardless of the language you choose.

Picking a Random Program

So, how do we find this mysterious probability called omega? Well, first we have to pick a program at random. Since a computer program is just a series of 0s and 1s, we can choose the individual bits by just flipping a coin. To determine the length of the program, we just keep providing bits until the computer stops asking for them.

Defining Omega

Omega is equal to an infinite sum, where each N-bit program that halts contributes exactly 1/2^N to the sum. This sum is the probability that a program chosen at random will halt.

Since there is no way to determine the bits of omega algorithmically, we say that omega is irreducible. So, we can find omega because we have a definition, but it's just not very easy thing to calculate.