Could you write a program that reads any other program, thinks for a while, and always correctly tells you: will this thing ever finish, or will it run forever?
Sounds like a solvable engineering problem, right? Just run it and watch. It isn't solvable. Not "we haven't figured it out yet," but proven, mathematically, permanently impossible. And the proof doesn't need advanced math. It needs one clever trick you're about to see with your own eyes.
What does it even mean for a program to "halt"?
A program halts if it eventually stops and gives you an answer. A program loops forever if it just... keeps going, no matter how long you wait.
Most programs you write halt. A function that adds two numbers halts almost instantly. But it's disturbingly easy to write one that doesn't, usually by accident. A while loop with a typo in its exit condition. A recursive function that forgot its base case. Every programmer has waited nervously in front of a frozen program, wondering: is this almost done, or is it never going to finish?
That nervous wait is the whole problem, in miniature.
Why can't we just run it and see?
Here's the trap. If a program halts, running it long enough eventually proves it, you just watch it stop. But if a program doesn't halt, running it never proves that. It just keeps running. Forever. You'd be waiting for a signal that never comes.
Watch it happen below. Three tiny programs, run step by step.
Pick a program and step through it. Notice that until it actually halts, you cannot tell the difference between “about to stop” and “never will.”
Try Collatz(7). It bounces up and down for sixteen steps before suddenly landing on 1 and stopping. Now try Forever. At step 16 it looks exactly as "not done yet" as Collatz did. At step 40 too. There is no step where "hasn't halted yet" turns into "will never halt." You'd need to watch forever to be sure, and forever is exactly the one thing you don't have.
So brute-force watching is out. What we actually want is a shortcut: a separate program, call it a checker, that looks at the code itself (never runs it) and instantly tells you HALTS or LOOPS FOREVER. Like a fortune teller for programs.
Could we build clever detection rules instead?
Sure, let's try. A reasonable first rule: if a loop's counter keeps shrinking toward zero, it'll probably halt. If it just grows forever, it probably won't. Simple, and it works on the easy cases.
But "probably" is doing a lot of quiet work in that sentence. Try fooling it below.
Detector's one rule: shrinking counter → guess HALTS, otherwise → guess LOOPS FOREVER. Read the code, guess first, then see who was right.
Notice Sneaky Halt. The counter just grows, no shrinking in sight, so the rule confidently guesses LOOPS FOREVER. It's wrong, the counter eventually hits its (very large) target and stops. And Disguised Loop fools it the other way: the counter shrinks just like a normal countdown, so the rule guesses HALTS, but it quietly resets itself right before hitting zero and loops forever. One rule, two different ways to be dead wrong.
What if we just keep adding smarter rules?
Fair question. Maybe one rule isn't enough, but a hundred rules would be? A rule for resets, a rule for nested loops, a rule for recursion depth...
Each dot is a program your detector needs to classify. Add rules and watch coverage climb, then click the glowing dot.
Slide the rule count up. Coverage climbs, more and more of these hypothetical programs get correctly classified. But click the glowing dot. It isn't just "a program we haven't handled yet." It's defined as whatever program specifically breaks whatever rule-set you're currently running. Patch a rule to catch it, and by its very definition, a new escaping program appears somewhere else. No matter how large your rule-set gets, there's always one program built to be exactly one step ahead of it.
...and that "built to dodge the checker, using the checker's own definition against it" idea isn't just a cute pattern in this toy example. It's the actual proof. Let's build it for real.
The trick that breaks every possible checker
Let's stop guessing and just assume the best possible case: somehow, someone built a perfect checker. Call it . Give any program and any input , and it always correctly tells you whether halts. No exceptions, no guessing, always right.
We write that as:
Now here's the move. Since can analyze any program, it can analyze programs that use itself. So we build a new, deliberately contrarian program called . Feed a program , and here's what it does: it asks what does when given itself as input, and then does the exact opposite.
Fine so far, weird but legal. Now for the killer move: what happens when we feed to itself?
Assume the checker H exists. Toggle what H claims about the program Weird, then step through what Weird actually does about it.
Toggle both claims above. If says " halts," then by its own definition, loops forever, making wrong. If says " loops forever," then immediately halts, making wrong again. There is no possible answer can give that turns out to be correct. Not because isn't clever enough. Because was built, on purpose, to contradict whatever says about it.
So the halting problem really is unsolvable?
Yes, and notice what we actually proved. We didn't say "nobody's smart enough to build yet." We assumed already existed, perfect and complete, and showed that assumption alone creates a logical contradiction. The only way out is that can never exist in the first place. This is called a proof by contradiction, and it's airtight regardless of how good our programming ever gets.
This isn't just a fun puzzle either. It's why your compiler can warn you about a probably-infinite loop but can never guarantee it caught every one. It's why no antivirus can perfectly detect every possible malicious program by analysis alone. It's why some problems in math and logic (like Gödel's incompleteness theorem) hit the exact same wall, for the exact same self-referential reason. The halting problem was the first hard proof that computation itself has permanent blind spots, discovered by Alan Turing in 1936, before a single electronic computer had even been built.
The short version
We wanted one program that could always tell us, for any other program, whether it halts or loops forever. Watching it run doesn't work, because non-halting never announces itself. Clever heuristics don't work either, every rule we tried had a program built to fool it. And that pattern generalizes into an actual proof: assume a perfect checker exists, build a program that asks the checker about itself and does the opposite, and you get a contradiction no matter what the checker says. So the perfect checker can't exist. Not yet, not ever, not with any amount of cleverness. Some questions about computation simply have no computable answer, and now you've seen exactly why.
All visualizations are interactive React components running entirely in your browser, computing every program trace, detector verdict, and contradiction live in plain JavaScript. No libraries beyond React.