The Halting Problem and Computability

One of the most profound results in Computer Science is that there are problems which no computer can ever solve, regardless of how much time or memory is available. The most famous example is the Halting Problem, proved undecidable by Alan Turing in 1936.

---

Decidable vs Undecidable Problems

Classification	Definition	Example
Decidable	A problem for which an algorithm exists that always terminates with the correct Yes/No answer	"Is this number prime?"
Undecidable	No algorithm exists that can always terminate with the correct answer for all possible inputs	The Halting Problem

A decidable problem has an algorithm that:

1. Always halts (terminates)
2. Always gives the correct answer

An undecidable problem has no such algorithm — for any proposed algorithm, there will always be some inputs for which it gives the wrong answer or never terminates.

---

The Halting Problem

Statement

Given a description of a program P and an input I, determine whether P will eventually halt (terminate) or run forever when executed on input I.