Halting problem

Alan Turing proved the halting problem is undecidable

Alan Turing's 1937 proof established that no general algorithm can decide if every program halts. This result is fundamental in computability theory, showing the limits of what can be computed. The proof demonstrates that some functions, while mathematically definable, cannot be computed by any algorithm.

Example

Consider a program designed to determine if another program halts. If this program were to exist, it would contradict Turing's proof, as it would imply that the halting problem is decidable.

Remember this

Understanding Turing's proof is crucial for recognizing the inherent limitations of computational systems and the boundaries of what can be algorithmically determined.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

Kolmogorov complexity

Kolmogorov complexity is uncomputable

Overlapping subproblems

Ever calculated a huge Fibonacci sequence by hand?

Adam has bias correction: divides by (1-β^t) in early steps

Why do we sometimes need to fix mistakes in computer decisions?

ReLU and Leaky ReLU

Why do computers sometimes struggle with simple decisions?

O(n log n) is the lower bound for comparison-based sorting

Ever wonder why sorting can't be faster than a certain point?

most transformer operations are memory-bound, not compute-bound

Why do computers sometimes get tired?

Swipe through 100 ML concepts daily

Open Pocket Polymath