{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T03:24:51Z","timestamp":1763436291262},"reference-count":9,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":11424,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1982,12]]},"abstract":"<jats:p>A notion of relative reducibility for partial functions, which coincides with Turing reducibility on the total functions, was first given by S.C. Kleene in <jats:bold><jats:italic>Introduction to metamathematics<\/jats:italic><\/jats:bold> [4]. Following Myhill [7], this was made more explicit in Hartley Rogers, Jr., <jats:bold><jats:italic>Theory of recursive functions and effective computability<\/jats:italic><\/jats:bold> [8, pp. 146, 279], where some basic properties of the partial degrees or (equivalent, but notationally more convenient) the <jats:italic>enumeration degrees<\/jats:italic>, were derived. The question of density of this proper extension of the degrees of unsolvability was left open, although Medvedev's result [6] that there are <jats:italic>quasi-minimal<\/jats:italic> partial degrees (that is, nonrecursive partial degrees with no nonrecursive total predecessors) is proved.<\/jats:p><jats:p>In 1971, Sasso [9] introduced a finer notion of partial degree, which also contained the Turing degrees as a proper substructure (intuitively, Sasso's notion of reducibility between partial functions differed from Rogers' in that computations terminated when the oracle was asked for an undefined value, whereas a Rogers computation could be thought of as proceeding simultaneously along a number of different branches of a \u2018consistent\u2019 computation tree\u2014cf. Sasso [10]). His construction of minimal \u2018partial degrees\u2019 [11], while of interest in itself, left open the analogous problem for the more standard partial degree structure.<\/jats:p>","DOI":"10.2307\/2273104","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:01:43Z","timestamp":1146938503000},"page":"854-859","source":"Crossref","is-referenced-by-count":23,"title":["Partial degrees and the density problem"],"prefix":"10.1017","volume":"47","author":[{"given":"S. B.","family":"Cooper","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200043723_ref007","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1961-0125794-X"},{"key":"S0022481200043723_ref006","first-page":"501","article-title":"Degrees of difficulty of the mass problem","volume":"104","author":"Medvedev","year":"1955","journal-title":"Doklady Academii Nauk SSSR"},{"key":"S0022481200043723_ref004","volume-title":"Introduction to metantathematics","author":"Kleene","year":"1952"},{"key":"S0022481200043723_ref003","unstructured":"Gutteridge Lance , The partial degrees are dense, preprint, 1971 (unpublished)."},{"key":"S0022481200043723_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(71)90003-9"},{"key":"S0022481200043723_ref009","unstructured":"Sasso Leonard P. Jr. , Degrees of unsolvability of partial functions, Ph.D. Thesis, University of California, Berkeley, 1971."},{"key":"S0022481200043723_ref005","unstructured":"Lagemann Jay J.T. , Embedding theorems in the reducibility ordering of partial degrees, Ph.D. Thesis, Massachusetts Institute of Technology, 1971."},{"key":"S0022481200043723_ref002","unstructured":"Gutteridge Lance , Some results on enumeration reducibility, Ph.D. Thesis, Simon Fraser University, 1971."},{"key":"S0022481200043723_ref008","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200043723","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T16:18:28Z","timestamp":1558714708000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200043723\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,12]]},"references-count":9,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1982,12]]}},"alternative-id":["S0022481200043723"],"URL":"https:\/\/doi.org\/10.2307\/2273104","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,12]]}}}