What Is an Undecidable Problem?

A decidable problem has an algorithm that always gives a correct yes/no answer in finite time. An undecidable problem cannot -- no algorithm exists that correctly answers all possible instances.

Undecidable is different from inefficient. An inefficient problem CAN be solved; it just takes a long time. An undecidable problem CANNOT be solved by any algorithm.

# We CANNOT write this correctly for all inputs:
def will_halt(program, input):
    # No algorithm can always return
    # True or False correctly here.
    # This is the Halting Problem.
    pass

{The halting problem asks:}
{Given any program P and input I,}
{will P eventually stop?}

{No algorithm can answer this}
{for ALL possible programs.}
{It is undecidable.}

The Halting Problem

Alan Turing proved in 1936 that no algorithm can determine, for every possible program and input, whether the program will halt or run forever. The proof uses a contradiction: assume a halting-checker H exists. Build a program P that does the opposite of what H predicts. P breaks H. Therefore H cannot exist.

AP exam point: The halting problem shows computing has fundamental mathematical limits. Some problems are not just hard -- they are provably impossible.

Practice Problems