A General Framework for Priority Arguments
Steffen Lempp, Manuel Lerman · Bulletin of Symbolic Logic · 1995
The degrees of unsolvability were introduced in the ground-breaking papers of Post [20] and Kleene and Post [7] as an attempt to measure theinformation contentof sets of natural numbers. Kleene and Post were interested in the relative complexity of decision problems arising naturally in mathematics; in particular, they wished to know when a solution to one decision problem contained the information necessary to solve a second decision problem. As decision problems can be coded by sets of natural numbers, this question is equivalent to: Given a computer with access to an oracle which will answer membership questions about a setA, can a program (allowing questions to the oracle) be written which will correctly compute the answers to all membership questions about a setB? If the answer is yes, then we say thatBisTuring reducibletoAand writeB≤TA. We say thatB≡TAifB≤TAandA≤TB. ≡Tis an equivalence relation, and ≤Tinduces a partial ordering on the corresponding equivalence classes; the poset obtained in this way is called thedegrees of unsolvability, and elements of this poset are calleddegrees. Post was particularly interested in computability from sets which are partially generated by a computer, namely, those for which the elements of the set can be enumerated by a computer.