Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Archive for Mathemat...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Archive for Mathematical Logic
Article . 1997 . Peer-reviewed
License: Springer TDM
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article
Data sources: zbMATH Open
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Conjectures and questions from Gerald Sacks's Degrees of Unsolvability

Conjectures and questions from Gerald Sacks's \textit{Degrees of unsolvability}
Authors: Shore, Richard A.;

Conjectures and questions from Gerald Sacks's Degrees of Unsolvability

Abstract

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}\).

Related Organizations
Keywords

History of mathematics in the 20th century, Recursively (computably) enumerable sets and degrees, History of mathematical logic and foundations, Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations, Other degrees and reducibilities in computability and recursion theory, Undecidability and degrees of sets of sentences, degrees of unsolvability, Computability and recursion theory on ordinals, admissible sets, etc.

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    5
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
5
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!