Halting problem
The question of whether a given program finishes on a given input or runs forever. Alan Turing proved that no program answers it correctly for every program and input. Rice’s theorem follows from it: checking any behavioural rule for every program is impossible too.
The judge gets a program and its input and must say whether it finishes or loops forever. For particular programs an answer can be found. Turing proved that there is no judge that answers correctly for every program at once.
Why there is no such judge. Suppose there is one. Write a contrarian program: it asks the judge about itself and does the opposite. If the judge says “halts”, the contrarian loops forever; if it says “doesn’t halt”, the contrarian stops at once. The judge is wrong either way, so it can’t exist. This is the same trick as in the barber paradox, about a barber who shaves everyone who doesn’t shave themselves.
Source: Wikipedia: Halting problem
Read more: Where to check an AI agent's work
Where it appears · 2
- Where to check an AI agent's work · Specs and context
- Rice's theorem in plain words · Specs and context