← Back to Issue 1: The Idea That Started Everything

The Halting Problem

A visual proof that some questions can never be answered

Illustration companion to Issue 1: The Idea That Started Everything

1

The Question

Can we build a machine that predicts if any program will halt? HALTING ORACLE the hypothetical machine INPUT SLOT program + input feed in any program HALTS LOOPS program finishes program runs forever Let's assume YES and see what happens... Tera
2

The Assumption

Suppose this machine exists. It always gives the correct answer. program input ORACLE oracle(program, input) HALTS LOOPS oracle(P, I) = HALTS or LOOPS for every possible program P and input I

We assume the Oracle is perfect — it never makes a mistake. Now we'll use it as a building block inside a new machine.

3

The Trick — Building the Paradox Machine

Now we build a devious new machine called PARADOX. It takes a program as input, feeds that program to itself as both arguments, and then does the opposite of what the Oracle predicts.

PARADOX MACHINE program (input) copies itself! ORACLE oracle(program, program) program input=program says HALTS says LOOPS LOOP FOREVER HALT How PARADOX works: function PARADOX(program): answer = oracle(program, program) if answer == HALTS: loop_forever() if answer == LOOPS: halt() do the opposite!

The key insight: PARADOX deliberately does the opposite of what the Oracle predicts. If the Oracle says the program halts, PARADOX loops. If the Oracle says it loops, PARADOX halts.

4

The Trap

Now comes the devastating move. What happens if we feed PARADOX its own code as input?

PARADOX (the program) feed it to itself! PARADOX MACHINE oracle(PARADOX, PARADOX) Oracle says HALTS then what? Oracle says LOOPS then what? ? ?

We call PARADOX(PARADOX). The Oracle inside must now answer: "Does PARADOX halt when given itself as input?" Let's follow both possible answers...

5

The Contradiction

Branch A Oracle says: "HALTS" PARADOX does the opposite: LOOPS FOREVER But Oracle said it halts... and it doesn't! BOOM! Branch B Oracle says: "LOOPS" PARADOX does the opposite: HALTS But Oracle said it loops... and it doesn't! BOOM! CONTRADICTION! Both answers are impossible. If the Oracle says HALTS, PARADOX loops. Wrong. If the Oracle says LOOPS, PARADOX halts. Wrong. There is no correct answer the Oracle can give. ? ?
6

The Conclusion

We assumed a perfect Halting Oracle exists. 1 We used it to build PARADOX, which does the opposite of what the Oracle predicts. 2 We fed PARADOX to itself. Both possible Oracle answers led to contradictions. 3 Therefore, our assumption was wrong. No such Oracle can exist. The Halting Problem is undecidable. This isn't a limitation of our technology. It's a limitation of mathematics itself. Tera
Some questions are provably unanswerable. No matter how powerful our computers become, no matter what programming language we use, no algorithm can ever solve the Halting Problem. This is not an engineering challenge — it is a mathematical certainty.

Alan Turing proved this in 1936, before any electronic computer was ever built.