Maths●●●●●Difficulty 4 of 5

Why can no machine ever settle every question in mathematics?

In 1936 Alan Turing proved that one simple question, "will this program ever stop?", is one no computer can always answer.

▶ Start the story

Because some questions trap any machine that tries to answer them. In 1928 David Hilbert and Wilhelm Ackermann asked for an algorithm that could take any logical statement and answer "yes" or "no": is it valid? This was the Entscheidungsproblem, the "decision problem". In 1936 Alonzo Church and Alan Turing each proved that no such algorithm can exist.

Turing's route is the one that stuck, because it is about machines. He showed that a perfect math-deciding machine would also let you answer a simpler-sounding question: given any program and its input, will it eventually stop, or run forever? Today this is called the halting problem. Then he showed that question has no general answer.

The proof is a beautiful trap. Suppose someone hands you a program that always correctly predicts whether a program halts. Build a contrary program that asks the predictor about itself, then does the opposite: if the predictor says "you will stop", it loops forever; if the predictor says "you will loop", it stops at once. Now ask the predictor about the contrary program. Whatever it answers is wrong. So the perfect predictor cannot exist. The trick is a cousin of Cantor's diagonal argument about infinities.

A physical model of a Turing machine: a long tape wound between two reels, passing under a read-write head on a wooden base.
A working model of a Turing machine built by Mike Davey: a tape, a head that reads and writes, and a rule table. Turing imagined it to prove what machines cannot do.Photo: Rocky Acosta · CC BY 3.0

This was a blow to Hilbert, who as late as 1930 believed no problem was unsolvable and whose slogan was "we must know, we will know". It does not mean we can't ever tell whether programs stop: simple cases are easy, and real tools prove that particular programs finish. It means no single method works for every case.

The trap that breaks any halting predictor
  1. Step 1: Assume a perfect predictor H

    It says whether any program halts on any input.

  2. Step 2: Build Contrary

    It asks H about a program run on its own code, then does the opposite.

  3. Step 3: Feed Contrary to itself

    If H says "halts", it loops; if H says "loops", it halts.

  4. Step 4: Contradiction

    H is wrong either way, so H cannot exist.

Quiz me

0/3

  1. 1.How did Turing show that Hilbert's decision problem has no solution?
  2. 2.In the proof, what does the "contrary" program do?
  3. 3.What does the undecidability of the halting problem NOT mean?

Recap

Any would-be halting predictor can be fooled by a program that asks it about itself and does the opposite.

Surprising fact · Turing never used the word "halting": the name "halting problem" appeared around 1952.

Sources (6)

No source, no claim. Every fact in this lesson (26 claims) cites at least one of these.

  1. [1]Entscheidungsproblem · Wikipedia
  2. [2]Halting problem · Wikipedia
  3. [3]Alan Turing · Wikipedia
  4. [4]Ignoramus et ignorabimus · Wikipedia
  5. [5]David Hilbert · Wikipedia
  6. [6]Turing machine · Wikipedia
More lessons in ➗ Maths (3) See all maths lessons →

One more light on your map.

Get one lesson like this every day, about the things you love. Free, in two or five minutes.

Get the share card for this lesson ↗