{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:53:20Z","timestamp":1759146800800},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":6803,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[1995,6]]},"abstract":"<jats:p>The degrees of unsolvability were introduced in the ground-breaking papers of Post [20] and Kleene and Post [7] as an attempt to measure the<jats:italic>information content<\/jats:italic>of 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 set<jats:italic>A<\/jats:italic>, can a program (allowing questions to the oracle) be written which will correctly compute the answers to all membership questions about a set<jats:italic>B<\/jats:italic>? If the answer is yes, then we say that<jats:italic>B<\/jats:italic>is<jats:italic>Turing reducible<\/jats:italic>to<jats:italic>A<\/jats:italic>and write<jats:italic>B<\/jats:italic>\u2264<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub><jats:italic>A<\/jats:italic>. We say that<jats:italic>B<\/jats:italic>\u2261<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub><jats:italic>A<\/jats:italic>if<jats:italic>B<\/jats:italic>\u2264<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub><jats:italic>A<\/jats:italic>and<jats:italic>A<\/jats:italic>\u2264<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub><jats:italic>B<\/jats:italic>. \u2261<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub>is an equivalence relation, and \u2264<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub>induces a partial ordering on the corresponding equivalence classes; the poset obtained in this way is called the<jats:italic>degrees of unsolvability<\/jats:italic>, and elements of this poset are called<jats:italic>degrees<\/jats:italic>.<\/jats:p><jats:p>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.<\/jats:p>","DOI":"10.2307\/421040","type":"journal-article","created":{"date-parts":[[2006,5,7]],"date-time":"2006-05-07T07:07:50Z","timestamp":1146985670000},"page":"189-201","source":"Crossref","is-referenced-by-count":5,"title":["A General Framework for Priority Arguments"],"prefix":"10.1017","volume":"1","author":[{"given":"Steffen","family":"Lempp","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Lerman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600008222_ref006","unstructured":"Groszek M. J. and Slaman T. A. , Foundations of the Priority Method, I: Finite and infinite injury, (manuscript)."},{"key":"S1079898600008222_ref004","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1990-15923-3"},{"key":"S1079898600008222_ref018","doi-asserted-by":"publisher","DOI":"10.2307\/1971035"},{"key":"S1079898600008222_ref015","volume-title":"Advances in Mathematics","author":"Lempp"},{"key":"S1079898600008222_ref016","unstructured":"Lempp S. and Lerman M. , Iterated trees of strategies and priority arguments, monograph: (to appear)."},{"key":"S1079898600008222_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(76)90016-4"},{"key":"S1079898600008222_ref013","volume-title":"Cambridge summer school in mathematical logic","author":"Lachlan","year":"1973"},{"key":"S1079898600008222_ref020","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1944-08111-1"},{"key":"S1079898600008222_ref010","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19910373104"},{"key":"S1079898600008222_ref005","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.43.2.236"},{"key":"S1079898600008222_ref029","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100052221"},{"key":"S1079898600008222_ref008","doi-asserted-by":"publisher","DOI":"10.2307\/2274665"},{"key":"S1079898600008222_ref007","doi-asserted-by":"publisher","DOI":"10.2307\/1969708"},{"key":"S1079898600008222_ref017","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1007\/978-1-4612-0325-4_17","volume-title":"Logical methods, in honor of Anil Nerode's 60th birthday","author":"Lempp","year":"1993"},{"key":"S1079898600008222_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90065-A"},{"key":"S1079898600008222_ref009","unstructured":"Kontostathis K. , Topological framework for infinite injury, (to appear)."},{"key":"S1079898600008222_ref028","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1966-0184855-9"},{"key":"S1079898600008222_ref021","volume-title":"Degrees of unsolvability","author":"Sacks","year":"1963"},{"key":"S1079898600008222_ref026","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S1079898600008222_ref025","unstructured":"Slaman T. A. and Woodin H. , Definability in degree structures, (to appear)."},{"key":"S1079898600008222_ref024","doi-asserted-by":"publisher","DOI":"10.2307\/2273376"},{"key":"S1079898600008222_ref027","unstructured":"Solovay R. M. , Degrees of models of true arithmetic, (preliminary version, unpublished)."},{"key":"S1079898600008222_ref003","volume-title":"Proceedings of the international congress for logic, methodology and the philosophy of science","author":"Cooper"},{"key":"S1079898600008222_ref022","doi-asserted-by":"crossref","first-page":"171","DOI":"10.4064\/fm-49-2-171-179","article-title":"Undecidable and creative theories","volume":"49","author":"Shoenfield","year":"1961","journal-title":"Fundamenta Mathematica"},{"key":"S1079898600008222_ref011","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19920380114"},{"key":"S1079898600008222_ref012","doi-asserted-by":"publisher","DOI":"10.2307\/1970579"},{"key":"S1079898600008222_ref019","first-page":"194","article-title":"On the unsolvability of the problem of reducibility in the theory of algorithms","volume":"108","author":"Mu\u010dnik","year":"1956","journal-title":"Doklady Akademii Nauk SSSR, N.S."},{"key":"S1079898600008222_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90048-7"},{"key":"S1079898600008222_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90048-5"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600008222","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T14:33:10Z","timestamp":1586874790000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600008222\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["S1079898600008222"],"URL":"https:\/\/doi.org\/10.2307\/421040","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}