Conjectures and questions from Gerald Sacks's \textit{Degrees of unsolvability} (Q1387091)

This paper provides a broad and useful overview of the growth and complexity of the theory of degrees. Shore looks at ``the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's \textit{Degrees of unsolvability} have had in the development of recursion theory over the past thirty years''. They concerned \({\mathcal R}\), the r.e. degrees, and \({\mathcal D}\), the full set of degrees, each partially ordered by Turing reducibility. In his 1963 edition (Zbl 0143.25302), Sacks offered six conjectures and five questions, noting that each seemed to call for a ``new idea''. In fact, they led to the development of the subject's most powerful techniques, including infinite injury arguments, tree constructions, and the full approximation method. Sacks's 1964 Density Theorem verified one conjecture about \({\mathcal R}\); 1966 results of Lachlan and Yates sustained two more, existence of a minimal pair of r.e. degrees and a pair with no g.l.b. in \({\mathcal R}\). The other conjectures concerned embedding in \({\mathcal D}\). Still open is the characterization of those partially ordered sets that are so embeddable. Sacks's five questions dealt with degrees below \(\underset\widetilde{} 0'\); all were answered by 1972. The 1966 edition made three further conjectures, all of which have been refuted; e.g., the elementary theory of \({\mathcal R}\) was proved undecidable, in fact recursively isomorphic to the theory of true first-order arithmetic. There were four new questions posed, two dealing with aspects of Post's problem, one with metarecursively enumerable degrees. Three of the questions have not been answered completely. Throughout, the author emphasizes that what has been found testifies to the unexpectedly great complexity of both \({\mathcal R}\) and \({\mathcal D}\).