Introduction

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.

Approximate It From Below

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">Each row is a tiny random program with a <b>length</b> (so it carries
weight 2<sup>-length</sup>) and a hidden <b>halting time</b>. Press <b>Run a step</b> to let every
still-running program execute one more instruction. When one halts, it adds its weight to
our estimate of &Omega; — the bar only ever <b>rises</b>, and you can never tell which
running programs will ever stop.</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 <span id="step">0</span>)</span></div>
</div>
<div id="progs" class="progs"></div>
<div class="btns">
  <button id="run" type="button">Run a step</button>
  <button id="run10" type="button">Run 10 steps</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status">Some programs never halt — the estimate stays a lower bound forever.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Approximating Chaitin's Omega FROM BELOW. Omega = sum over halting programs p of
    // 2^(-length(p)). We can only ever discover halting programs (never prove non-halting),
    // so our estimate only rises and is always a lower bound. Programs that never halt
    // contribute nothing we can ever account for — that's why Omega is uncomputable.
//
// Each program here has a fixed length L (weight 2^-L) and a halting time H (steps to
    // halt) or H = Infinity (never halts). At each step every running program advances by 1.
const PROGRAMS = [
  { name: 'p1', len: 2, halt: 1 },        // weight .25
  { name: 'p2', len: 3, halt: 4 },        // weight .125
  { name: 'p3', len: 3, halt: Infinity }, // never halts
  { name: 'p4', len: 4, halt: 7 },        // weight .0625
  { name: 'p5', len: 4, halt: 2 },        // weight .0625
  { name: 'p6', len: 5, halt: Infinity }, // never halts
  { name: 'p7', len: 5, halt: 12 },       // weight .03125
  { name: 'p8', len: 6, halt: 9 },        // weight .015625
];
const MAXSTEP = 20; // we can only watch finitely long; non-halting stays "running"
const weight = (p) => Math.pow(2, -p.len);

let step = 0;
function omegaEstimate() {
  // sum of weights of programs KNOWN to have halted by now (halt <= step)
  let s = 0;
  for (const p of PROGRAMS) if (p.halt <= step) s += weight(p);
  return s;
}

function render() {
  document.getElementById('step').textContent = step;
  const est = omegaEstimate();
  document.getElementById('omega').textContent = est.toFixed(6);
  document.getElementById('fill').style.width = (est * 100).toFixed(2) + '%';
  const box = document.getElementById('progs'); box.innerHTML = '';
  let running = 0;
  for (const p of PROGRAMS) {
    const halted = p.halt <= step;
    if (!halted) running++;
    const row = document.createElement('div');
    row.className = 'prog ' + (halted ? 'halted' : 'running');
    const frac = halted ? 1 : Math.min(step / MAXSTEP, 0.96);
    row.innerHTML =
      '<span class="tag">' + p.name + ' (2<sup>-' + p.len + '</sup>)</span>' +
      '<span class="track"><span class="tip" style="left:' + (frac * 100) + '%"></span></span>' +
      '<span class="st">' + (halted ? fmt('halted +%weight%', { weight: weight(p).toFixed(4) }) : 'running…') + '</span>';
    box.appendChild(row);
  }
  const s = document.getElementById('status');
  if (running === 0) s.textContent = 'All observable programs halted. But in general you can NEVER be sure none are left.';
  else s.textContent = fmt('%running% program(s) still running — will they halt? Omega never tells you.', { running: running });
}

function stepOnce() { if (step < MAXSTEP) step++; render(); }
document.getElementById('run').addEventListener('click', stepOnce);
document.getElementById('run10').addEventListener('click', () => { for (let i = 0; i < 10; i++) stepOnce(); });
document.getElementById('reset').addEventListener('click', () => { step = 0; render(); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

Ω 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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/chaitins-omega/Content licensed under CC BY-NC 4.0.