The Halting Problem: A Task No Program Can Do · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

The question no program can answer

Computing · Algorithms & Data Structures · ages 17-18
Name ______________________   Date ____________

  1. What must the checker output for every program and input pair?

    • A nicer font for the code
    • The number of keyboards owned
    • Whether it finishes or loops forever

  2. What is the halting checker given?

    • The full text of a program and its input
    • A faster computer
    • The programmer's birthday

  3. A checker that is right on most programs is good enough.

    Circle one:   True   False

  4. Where does the contradiction appear?

    • In the price of computers
    • In the colour of the screen
    • At the self-asking step

  5. The checker says the trickster stops. What does the trickster do?

    • Stops politely at once
    • Loops forever, defying the verdict
    • Deletes the checker

  6. A problem needing a billion years is undecidable.

    Circle one:   True   False

  7. Lee says faster computers will one day solve the halting problem. What is wrong?

    • Speed cannot help, because no correct program exists at any speed
    • Computers will never get faster
    • Programmers dislike fast machines

  8. A loop detector works for every school program except one. Can it count as solving the halting problem?

    • Yes, because schools matter most
    • No, because one wrong answer breaks the guarantee
    • Yes, because one miss is tiny
LightMySky · lightmysky.comW1-mt_KeuKGHFWqr-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

The question no program can answer W1-mt_KeuKGHFWqr-s1

  1. Whether it finishes or loops forever · Stops or loops, correctly, for every pair.
  2. The full text of a program and its input · Program plus input in, stops or loops out.
  3. False · The guarantee needs every pair, and the trickster exploits the gap.
  4. At the self-asking step · The trickster feeds itself to the checker, and no verdict survives.
  5. Loops forever, defying the verdict · The trickster always does the opposite of the verdict.
  6. False · A correct program exists there, so the problem is slow, not undecidable.
  7. Speed cannot help, because no correct program exists at any speed · Undecidable resists every machine that will ever be built.
  8. No, because one wrong answer breaks the guarantee · The proof builds its trap exactly on the mishandled case.
Worksheet · LightMySky