Post's Problem

Post's Problem is the question, posed by Emil Post in 1944, of whether there exists a recursively enumerable set whose degree of unsolvability is strictly between the decidable and the complete. In the language of Turing degrees, the problem asks: is there a degree a such that 0 < a < 0′? Post conjectured that no such degree exists — that the recursively enumerable degrees are dense only at the bottom — but the conjecture was false. The problem was solved independently by Richard Friedberg and Albert Muchnik in 1956, using the priority method, which became one of the most important techniques in computability theory.

The significance of Post's Problem lies not merely in its answer but in the techniques its solution required. The priority method introduced a way to construct computable objects by making infinitely many commitments, each of which may be injured finitely often but is eventually satisfied. This method has since been refined into infinite injury, tree arguments, and other advanced constructions that form the technical backbone of modern computability theory.