skip to content

How does assuming a perfect halting decider let you build a program that contradicts it?

level: middleimportance: must knowfreq 55%

answer

  1. assume the oracle exists
  2. program text is data too
  3. feed a program its own text
  4. branch, then do the opposite
  5. both answers come out wrong

basics

~20 s

Assume a routine that always terminates and correctly reports whether any program halts on any input. Write a program that asks it about itself and then does the opposite. Running that program on its own text makes the routine wrong either way.

solid answer

~40 s

Suppose `WOULD_STOP(program, input)` always terminates and correctly answers whether that program stops on that input. Program text is just data, and a program can be handed its own text, so you can write `TRAP(p)`: call `WOULD_STOP(p, p)`, loop forever if the answer is "stops", return immediately if the answer is "never stops". Now run `TRAP` on the text of `TRAP`. If the oracle said "stops", `TRAP` loops - so the oracle was wrong. If it said "never stops", `TRAP` returns - wrong again. Both branches are contradictions and they are exhaustive, so the assumed routine cannot exist. It is a diagonal argument: the self-application is where the constructed program disagrees with every candidate decider.

code

pseudocode · 16 lines
pseudocode
# assumed: always returns, always correct
function WOULD_STOP(program_text, input):
    return true if running program_text on input eventually stops
    return false otherwise

function TRAP(program_text):
    if WOULD_STOP(program_text, program_text):
        loop forever
    else:
        return

# now run TRAP on its own text:
TRAP(text_of(TRAP))

# case true : TRAP loops forever -> it did NOT stop -> oracle wrong
# case false: TRAP returns at once -> it DID stop   -> oracle wrong

go deeper

for a junior

Know that the impossibility is proved by contradiction: assume the perfect checker, then build a program that asks it about itself and does the opposite. Recognising the shape is enough at this stage.

for a middle

Be able to construct it live: the oracle call on the argument applied to itself, the inverted branch, the self-application, and both cases spelled out. State exactly which assumed properties - totality and correctness - the contradiction discharges.

for a senior

Show why the standard patches fail - refusing to answer, a third answer, simulating instead of analysing - and connect that to why your own tooling reports unknown rather than pretending to a verdict.

for a principal

Use the argument as a boundary marker when evaluating a proposed analysis capability: if a proposal implies a total correct decision over arbitrary submitted code, it is not a roadmap item, and the conversation should move to restricting the input language.

## The assumption we are about to destroy Suppose someone hands you `WOULD_STOP`: a routine taking the text of a program plus an input, which **always returns in finite time** and returns true **exactly when** running that program on that input eventually stops. Note precisely what is assumed - **totality** (it always answers) and **correctness** (the answer is right), for every pair. Its speed is irrelevant to the argument, and so is how it works inside. Two further facts do quiet work, and neither is controversial: - A program's text is **data**: it can be stored, copied and passed as an argument, including to a routine that analyses it. - A program can be handed **its own text** as input. Nothing prevents it; the text is just bytes. ## The construction 1. Write a program `TRAP` that takes one argument: the text of some program. 2. Inside, `TRAP` calls `WOULD_STOP(argument, argument)` - it asks the oracle what the argument does when run on itself. 3. If the oracle answers "it stops", `TRAP` enters an endless loop. 4. If the oracle answers "it never stops", `TRAP` returns immediately. 5. Now run `TRAP` on the text of `TRAP`. `TRAP` is an ordinary program - a call, a branch, a loop. If `WOULD_STOP` exists as assumed, `TRAP` can be written, because the oracle is by hypothesis a routine you may call. ## Reading the contradiction Everything turns on the single call `WOULD_STOP(TRAP, TRAP)`, which by assumption returns one of exactly two answers. | The oracle returns | `TRAP(TRAP)` takes | So `TRAP(TRAP)` actually | The oracle's answer was | |---|---|---|---| | true, "it stops" | the endless loop | never stops | wrong | | false, "it never stops" | the immediate return | stops | wrong | Both rows are contradictions and together they are exhaustive, so the assumption that produced them is false: no routine with those properties exists. This is a **diagonal** argument. Line up every candidate decider against every program, and the constructed program is built to disagree with each candidate on the diagonal entry - the candidate's own verdict about self-application. It is the same shape as the argument that no list of infinite binary sequences can contain them all: you build the sequence that differs from the first at position one, the second at position two, and so on. ## What the argument proves, and what it does not - It refutes a **universal** decider. It does not say the behaviour of any particular program is unknowable; most programs you will ever read are easy to classify, and many have outright termination proofs. - It does not depend on the machine model, the source language, or unlimited memory in any exotic sense. Any setting rich enough to run a program on its own text and branch on the result supports the construction. - It is not about weird or malicious programs. `TRAP` is short and utterly ordinary. Its only unusual feature is that it reads a prediction about itself and then falsifies it. ## Why you cannot patch the decider Every proposed repair fails in the same way, and it pays to have one of these ready: - **"Detect self-reference and refuse."** Refusing is not answering, and the assumed routine had to answer for every input. A decider that declines has already lost totality - and the construction can be rebuilt around any fixed detection rule. - **"Return a third answer, unknown."** Same objection. The object being refuted is a two-answer **total** decider; a three-answer procedure is easy to build and useless for deciding. - **"Run the program rather than analyse it."** Then the routine inherits the program's non-termination and is no longer total. - **"Make the decider larger than anything that can call it."** The construction embeds the decider inside `TRAP`, so `TRAP` is a fixed amount larger than whatever the decider is. There is no size at which you escape. ## Saying it in an interview The whole argument is four sentences, and compressing it well is much of what is being tested. Assume a routine that always terminates and correctly reports whether any program halts on any input. Write a program that asks that routine what it itself does on its own text, then does the opposite. Running it on its own text makes the routine wrong either way. Therefore the routine cannot exist. Then add the consequence, which is what turns a recitation into an engineering answer: since the universal decider is impossible, every tool in this space must choose between missing cases, false alarms, and not always answering.

  • Why is this called a diagonal argument?
    Imagine a grid with one row per candidate decider and one column per program, each cell holding that decider's verdict about running that program on its own text. The constructed program is designed to disagree with the diagonal entry - each decider's verdict about self-application - so no row can be correct everywhere.
  • Could the decider escape by refusing to answer for programs that call it?
    No. The refutation targets a routine that answers for every input, so declining is already a failure of the assumed property. Worse, any fixed detection rule can be routed around: the construction only needs to read the verdict somehow and then contradict it.
  • Does the argument depend on the program being able to inspect its own source?
    It needs the text to be obtainable, not introspection magic. Since a program is data, a construction can build a copy of the text and pass it in as an ordinary argument, which is all the argument uses. No self-inspection facility of any particular runtime is required.

It is a weather forecaster who must publish a prediction about one particular contrarian, who reads the forecast each morning and then deliberately does the opposite. No forecast about that person can ever be right, however good the forecaster is at everyone else.

saying these in an interview costs you the question

  • Says the decider just needs to detect self-reference and refuse.
  • Claims the contradiction only shows the decider is too slow.
  • Thinks the argument needs an infinite or exotic machine.
  • Believes individual self-referential programs are the undecidable objects.
  • Assumes a program cannot receive its own text as input.