Halting Problem

Noun · Development

Definitions

  1. The proven impossibility of writing a general algorithm that determines whether any given program will eventually stop (halt) or run forever. Alan Turing proved this in 1936 using a diagonalization argument. Has practical implications — no compiler can detect all infinite loops.

    In plain English: The mathematical proof that it's impossible to write a program that can always tell whether another program will finish or loop forever.

    Example: "The linter catches some infinite loops, but it can't catch them all — that's literally the halting problem."

Etymology

1936
Alan Turing proved the undecidability of the halting problem in his foundational paper on computability.

Related Terms