The Number That Encodes Every Open Problem

Added: 2026-05-12

[00:00:00]Generate a computer program one bit at a time. Flip a coin, heads is one, tails is zero. Each new bit comes up zero or one with equal probability independent of every other bit. When the program is complete, run it on a Turing machine.

[00:00:16]Eventually, it does one of two things.

[00:00:19]It halts and produces an answer or it runs forever. Question, what's the probability that this random program halts? That number has a name, capital Omega, Chaitin's Omega. It's a real number between zero and one. Decimal expansion goes on forever. It's irrational, provably uncomputable. There is no algorithm, current or ever, that outputs its digits in order. And every single new bit of Omega you somehow learn answers infinitely many open mathematical questions. Goldbach's conjecture, the Riemann hypothesis, twin primes, the Birch and Swinnerton-Dyer conjecture. All of them collapse if you can compute enough bits of Omega. That's the destination. Quick recap of the wall this number sits on. A program halts if it eventually stops and produces an answer. Print "Hello, world." Done.

[00:01:16]Three characters of code. Some programs run forever. While true, do nothing.

[00:01:22]Doesn't stop. Some programs are mysterious. Take this rule. While n is greater than one, if n is even half it.

[00:01:30]Otherwise, replace n with 3n + 1. Start with n = 6. Goes 6, 3, 10, 5, 16, 8, 4, 2, 1. Halts. For every starting value anyone has tried, this halts. We do not know if it halts for every starting value. The Collatz conjecture, 60 years open. The general halting problem asks, given any program and input, will it halt? Turing proved in 1936 that no algorithm answers this in finite time for every program. The proof is a clean diagonal argument. If a halting decider existed, you'd build a program that consults it and does the opposite of what it predicts. That program contradicts itself. The halting function exists. It takes programs to yes or no.

[00:02:20]It is forever beyond computation. Omega lives on the other side of that wall.

[00:02:26]Here's the twist. Forget asking about specific programs. Ask about all programs at once. Build a random program by independent coin flips, bit by bit.

[00:02:37]The longer the program, the less likely a specific bit string appears. A specific program of length n bits has probability 2 to the negative n. The probability that a random program halts is the sum over all halting programs of 2 to the negative bit length. That sum is omega. Tiny halting programs contribute big chunks. A halting program of length 1 contributes 1/2, of length 2, 1/4, of length 10, about a thousandth. A halting program of length 100 contributes about 10 to the negative 30. Long halting programs contribute almost nothing, but there are exponentially many of them. Add them all up, get a real number that lives strictly inside 0 to 1. That's the entire definition.

[00:03:30]For this sum to make sense, every program must be exactly a program. No initial chunk of one program can also be a complete program by itself. That's a prefix-free code. Every standard universal Turing machine encoding uses one. With prefix-free encoding, the halting programs form what's called an anti-chain. Their probabilities sum to a finite number, at most one, by Kraft's inequality. The contribution from non-halting programs would push the sum to one. The contribution from halting programs alone gives some number strictly less than one. Different universal Turing machines give different omegas. There isn't one omega. There's an omega for each machine. Every one of them has the same properties. Pick any universal Turing machine. The number that drops out is its omega.

[00:04:23]Now, the central claim. Omega cannot be computed. The proof is short. We'll do it now. Suppose we know the first n bits of omega. Truncate omega's true value to those first n bits. Call this number omega n. It's rational. It's a lower bound for the true omega within 2 to the negative n. We're going to use omega n to solve the halting problem for every program of length up to n bits. Run all programs of length up to n in parallel.

[00:04:54]There are at most 2 to the n of them.

[00:04:57]Use a dovetailing schedule that gives each program more steps over time.

[00:05:02]Whenever any of them halts, add its individual probability, 2 to the negative length of that program, into a running tally. The tally only grows. It never shrinks. It is always less than or equal to the true omega. Wait until the tally reaches or exceeds omega n. That eventually happens because the true omega is bigger than omega n by less than 2 to the negative n, and the tally grows toward the true omega. At the exact moment the tally crosses omega n, here's what's true. Every program of length up to n that's ever going to halt has already halted. Every program of length up to n that hasn't halted yet runs forever. We've decided the halting problem for every program of length up to n. That's roughly two to the n different halting decisions. All of that came from n bits of omega, but the halting problem is uncomputable. There is no algorithm that decides it. So, those n bits of omega cannot all come from any algorithm. Therefore, omega is uncomputable. The whole proof, two paragraphs. The number itself, forever opaque.

[00:06:13]Stronger statement, omega is random in the sharpest sense math has built, Martin-Löf random. The technical definition, there is no computably enumerable test that omega's bits fail with positive measure. The intuitive version, no algorithm running for any finite time with any amount of memory can predict the next bit better than 50/50. No statistical pattern that any computable test could ever detect.

[00:06:43]Compare to the digits of pi. Pi's digits look random. They pass every standard randomness test we've designed. They appear normal in base 10, but pi is computable. There's an algorithm to print its digits. So, pi is not Martin-Löf random. Its digits are statistically random as far as we can tell, but algorithmically completely determined. Compress them by giving the algorithm. Omega is past that line. Its bits have no shorter description than themselves. There is no algorithm, no compression, no pattern. The first thousand bits of omega require in any encoding at least about a thousand bits to describe. There is no formula that gives them, and yet omega is a single specific real number. We can write its definition in two lines. We can prove things about it. We just cannot compute it.

[00:07:40]Earlier we showed the first n bits of Omega solve the halting problem for every program of length up to n. So, how much mathematics does that buy us? A lot. Almost any open problem in arithmetic can be encoded as a single program of a few hundred bits. Goldbach conjecture: Every even integer greater than two is a sum of two primes. Encode it. Loop n equals four, six, eight, and so on. For each n, search for two primes p and q with p plus q equals n. If you ever find an n with no such pair, halt and report it. The program halts if and only if Goldbach is false. Source code, maybe 300 bits. 300 bits of Omega would tell you whether that program halts.

[00:08:30]That settles Goldbach one way or the other. The Riemann hypothesis can be encoded the same way. Lagarias proved an elementary reformulation: RH holds if and only if a specific divisor sum inequality holds for every n. Loop, check, halt on counterexample. A few hundred more bits. Twin prime conjecture, the same. The first thousand bits of Omega contain the answer to essentially every famous open problem in arithmetic whose statement is for all integers n blah. The first 10,000 bits would settle most of mathematics that's been written down. Omega is information about the structure of all of mathematics packed into a single number.

[00:09:16]So, how many bits of Omega do we actually know? Christian Calude, Michael Dehnert, and Kaikho Shu in 2002 computed the first 64 bits of Omega for one specific universal Turing machine. The bit string is 1000001000000100, and it continues for 48 more bits. Each of those bits required hours of computation, classifying programs into definitely halts or still running. The next bit, bit 65, depends on whether certain specific programs of length around 65 bits halt. Nobody knows. It might be zero, it might be one. We have no way to find out, even in principle, beyond doing the equivalent computation for those specific programs. The number is irrational, well-defined, and past the edge.

[00:10:14]Step back from the math. Omega is a real number with an explicit two-line definition. The first n bits of it solve the halting problem for every program shorter than n bits. It is algorithmically random, no description shorter than itself, and it tells us something deep about the real numbers themselves. There are real numbers, specific, definable, mathematically central, whose digit sequences are forever closed off from computation. We have constants we know to over a hundred trillion digits, pi, e, square root of two. We have other constants whose first hundred digits will likely never be known by anyone, ever, no matter how much compute the universe contains.

[00:10:58]Omega is the canonical example. There are infinitely many other reals like it.

[00:11:03]They form a set of full measure. Almost every real number is uncomputable in the omega sense, the real number line is mostly inaccessible to algorithms. The numbers we can name and write down, the rationals, the algebraic numbers, the standard transcendentals, make up a measure zero set inside it. The boundary between computable and uncomputable doesn't sit out at infinity. It runs through every neighborhood of every real number.

[00:11:32]Generate a random program by flipping coins. The probability that it halts is omega. That number is real. It lives in zero to one. It is irrational. It is single-valued for any fixed universal Turing machine. It cannot be computed.

[00:11:50]No Turing machine, present or future, can produce its digits in order. It is Martin-Löf random. No algorithm and no test will ever detect a pattern in its bits. And it is the densest object in mathematics. Every new bit is the answer to a question we want to know. We have 64 bits. The next one is out of reach.