{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T08:05:25Z","timestamp":1775462725929,"version":"3.50.1"},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":14164,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1975,6]]},"abstract":"<jats:p>Partial degrees are equivalence classes of partial natural number functions under some suitable extension of relative recursiveness to partial functions. The usual definitions of relative recursiveness, equivalent in the context of total functions, are distinct when extended to partial functions. The purpose of this paper is to compare the upper semilattice structures of the resulting degrees.<\/jats:p><jats:p>Relative partial recursiveness of partial functions was first introduced in Kleene [2] as an extension of the definition by means of systems of equations of relative recursiveness of total functions. Kleene's relative partial recursiveness is equivalent to the relation between the graphs of partial functions induced by Rogers' [10] relation of relative enumerability (called enumeration reducibility) between sets. The resulting degrees are hence called enumeration degrees. In [2] Davis introduces completely computable or compact functionals of partial functions and uses these to define relative partial recursiveness of partial functions. Davis' functionals are equivalent to the recursive operators introduced in Rogers [10] where a theorem of Myhill and Shepherdson is used to show that the resulting reducibility, here called weak Turing reducibility, is stronger than (i.e., implies, but is not implied by) enumeration reducibility. As in Davis [2], relative recursiveness of total functions with range \u2286{0, 1} may be defined by means of Turing machines with oracles or equivalently as the closure of initial functions under composition, primitive re-cursion, and minimalization (i.e., relative \u03bc-recursiveness). Extending either of these definitions yields a relation between partial functions, here called Turing reducibility, which is stronger still.<\/jats:p>","DOI":"10.2307\/2271892","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:35:13Z","timestamp":1146951313000},"page":"130-140","source":"Crossref","is-referenced-by-count":19,"title":["A survey of partial degrees"],"prefix":"10.1017","volume":"40","author":[{"suffix":"Jr.","given":"Leonard P.","family":"Sasso","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200053676_ref014","doi-asserted-by":"publisher","DOI":"10.2307\/1969604"},{"key":"S0022481200053676_ref012","unstructured":"Sasso Leonard P. , Degrees of unsolvability of partial functions, Ph.D. Dissertation, University of California, Berkeley, 1971."},{"key":"S0022481200053676_ref008","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":"S0022481200053676_ref011","volume-title":"Annals of Mathematics Studies","author":"Sacks","year":"1963"},{"key":"S0022481200053676_ref010","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200053676_ref006","doi-asserted-by":"publisher","DOI":"10.2307\/1969708"},{"key":"S0022481200053676_ref003","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19590050703"},{"key":"S0022481200053676_ref005","volume-title":"Introduction to metamathematics","author":"Kleene","year":"1952"},{"key":"S0022481200053676_ref009","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1961-0125794-X"},{"key":"S0022481200053676_ref013","first-page":"388","article-title":"A minimal partial degree \u22640\u2032","volume":"38","author":"Sasso","year":"1973","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S0022481200053676_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(71)90003-9"},{"key":"S0022481200053676_ref002","volume-title":"Computability and unsolvability","author":"Davis","year":"1958"},{"key":"S0022481200053676_ref004","unstructured":"Gutteridge Lance , Some results on enumeration reducibility, Ph.D. Dissertation, Simon Fraser University, 1971."},{"key":"S0022481200053676_ref007","unstructured":"Lagemann Jay J. T. , Embedding theorems in the reducibility ordering of partial degrees, Ph.D. Dissertation, Massachusetts Institute of Technology, 1971."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200053676","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T19:40:40Z","timestamp":1559158840000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200053676\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975,6]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1975,6]]}},"alternative-id":["S0022481200053676"],"URL":"https:\/\/doi.org\/10.2307\/2271892","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1975,6]]}}}