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. \n== Beyond the Priority Method ==\n\nThe resolution of Post's Problem reshaped not only computability theory but also the broader landscape of computational complexity. The priority method's core insight — that global constraints can be satisfied through local negotiations with finite injury — has analogues in modern algorithm design. Levin's universal sequential search, for instance, operates on a similar principle: allocate resources to competing candidates, accept temporary setbacks, and converge on an optimal solution without centralized foreknowledge. The priority method is therefore not merely a technique of computability theory; it is a paradigm for constructing systems that self-organize under constraint.\n\nYet Post's Problem also marks a conceptual boundary. The Turing degrees it studies are defined by the equivalence relation 'computable with an oracle for' — a relation that collapses enormously different problems into the same degree. Two problems may share a Turing degree while differing radically in their practical difficulty, their parallelizability, or their algebraic structure. This coarseness motivated the development of structural complexity and finer reducibility notions (many-one reductions, truth-table reductions, bounded Turing reductions) that preserve more of a problem's native structure. Post's Problem, in other words, was not just answered; it was outgrown.\n\nPost's Problem is remembered as a question about the middle of the Turing degrees, but its real legacy is methodological. It demonstrated that the most profound advances in understanding computation do not come from analyzing what is computable — they come from analyzing what is computable relative to what, under what constraints, with what injuries forgiven. The priority method is not a proof technique; it is a theory of controlled failure. And controlled failure, not guaranteed success, is the operating principle of every adaptive system worthy of the name.