Chaitin's Omega

Imagine a machine that feeds itself a program built from coin flips — bit by random bit — and then runs it. Some of those random programs eventually halt; most spin forever. The probability that this random program halts is a single real number between 0 and 1. The mathematician Gregory Chaitin named it Omega (Ω), and it is one of the strangest objects in all of mathematics.

Ω is not vague or hand-wavy. For a fixed programming language it is one specific number, as definite as π or √2. You could, in principle, write down its first digit, its second, its third.

And yet you can't. No algorithm, no supercomputer, no amount of cleverness will ever print those digits in order. Ω is uncomputable — and it is random in the deepest sense we know how to define. This article is about how one honest little number can be so perfectly defined and so completely out of reach.

Here is a tiny universe of programs, each with its own halting time. Press Run a step to let every still-running program execute one more instruction. Whenever a program halts, it contributes its weight to our running estimate of Ω, and the bar creeps up.

<p class="hint">{{hint}}</p>
<div class="meter">
  <div class="bar"><div id="fill" class="fill"></div></div>
  <div class="readout">&Omega; &ge; <span id="omega">0.000000</span> &nbsp;
    <span class="muted">({{step_label}} <span id="step">0</span>)</span></div>
</div>
<div id="progs" class="progs"></div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="run10" type="button">{{btn_run10}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status">{{status_init}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.meter { margin: .4rem 0 .8rem; }
.bar { height: 22px; background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 6px; overflow: hidden; }
.fill { height: 100%; width: 0%; background: linear-gradient(90deg,#1d3557,#3a6ea5); transition: width .25s; }
.readout { font: 600 1rem ui-monospace, monospace; margin-top: .4rem; color: #1d3557; }
.muted { color: #788; font-weight: 400; }
.progs { display: grid; gap: 5px; margin: .4rem 0; }
.prog { display: grid; grid-template-columns: 70px 1fr 96px; align-items: center; gap: 8px;
        font: 600 13px ui-monospace, monospace; }
.tag { color: #1d3557; }
.track { height: 14px; background: #c9ccd1; border: 1px solid #adb1b8; border-radius: 7px; position: relative; overflow: hidden; }
.tip { position: absolute; top: 0; bottom: 0; width: 6px; background: #1d3557; transition: left .2s; }
.prog.halted .track { background: #d6f0df; border-color: #9ad3ad; }
.prog.halted .tip { background: #0a7d33; }
.prog.running .track { background: #fff3d6; border-color: #e6c878; }
.st { font: 600 12px system-ui, sans-serif; text-align: right; }
.prog.halted .st { color: #0a7d33; }
.prog.running .st { color: #a06a00; }
.status { font-size: .92rem; font-weight: 600; margin: .5rem 0; min-height: 1.3em; color: #555; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch what happens. The estimate only ever rises — each newly halting program adds a little, none can ever subtract. That is what "approximating Ω from below" means. But notice the cruelty: at any moment, programs are still running, and you have no way to tell whether one of them will halt on the next step or never halt at all. The number you see is always a lower bound, never the true value — and you can never know how close you are. To learn more about that wall, see the halting problem and the busy beaver.

How hard is Ω, really? It is not "hard" like a slow computation — it is beyond computation entirely.

• It is well-defined. Fix a universal prefix-free machine, and Ω is the exact sum, over every halting program p, of 2 to the power of minus its length. One precise real number.
• It is uncomputable. There is no algorithm that, given n, outputs the first n digits of Ω. Chaitin proved this in the 1970s, building directly on Turing's halting problem.
• Its digits encode every halting answer. If a genie handed you the first n bits of Ω, you could decide whether every program shorter than roughly n bits halts. A few thousand digits would resolve an astronomical number of open mathematical questions at once.
• It is algorithmically random. The bits of Ω are incompressible: no program meaningfully shorter than the digits themselves can generate them. There is no pattern, no shortcut, no formula. It is the gold standard of true randomness.

That is the punchline. Ω is a perfectly legitimate number — you can name it in a sentence — yet it concentrates all the undecidability of computation into a single string of bits. It is uncomputable, full stop, and that status will never change.

Ω is not a tool you run — it is a landmark that maps the edge of the knowable:

• Algorithmic information theory: Ω is the headline example of a number whose information content is maximal and incompressible, the core idea behind Kolmogorov complexity.
• Limits of mathematics: because its digits encode halting facts, any fixed system of axioms can prove only finitely many of Ω's bits. It is a sharp, concrete form of Gödel's incompleteness.
• Defining randomness: Ω gives mathematicians a rigorous yardstick for what "truly random" means — passing every computable statistical test, by construction.
• Teaching the uncomputable: Ω turns the abstract halting problem into a single object you can almost reach out and touch, which makes it a favorite way to explain why some things are forever out of reach.

Understand Omega and you have met the ceiling of computation itself — the same ceiling behind the halting problem and the wildly fast-growing busy beaver.

Chaitin's Omega is a quiet paradox you can state in one breath: a definite number between 0 and 1, as real as π, whose digits answer every question about which programs halt — and which no algorithm can ever reveal. We can creep toward it from below, watching our estimate rise forever, but the true value stays just out of reach, one halting program at a time.

So Ω is not a puzzle waiting for a clever trick. It is uncomputable and random by its very nature, a permanent monument at the border of mathematics. The next time someone says a number is just a number, remember that one of them quietly holds the answer to everything that can or cannot finish — and keeps it forever to itself.