Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-29T15:04:23.365Z Has data issue: false hasContentIssue false
  • English
  • Français

A survey of partial degrees1

Published online by Cambridge University Press:  12 March 2014

Leonard P. Sasso Jr.
Leonard P. Sasso Jr.*
Affiliation:
University of California, Irvine, California 92664
Get access Rights & Permissions [Opens in a new window]

Extract

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.

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 ⊆{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 μ-recursiveness). Extending either of these definitions yields a relation between partial functions, here called Turing reducibility, which is stronger still.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 40 , Issue 2 , June 1975 , pp. 130 - 140
Copyright
Copyright © Association for Symbolic Logic 1975

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

Much of this work is contained in the author's doctoral dissertation at the University of California, Berkeley, California, and was carried out while the author was a National Science Foundation Graduate Trainee.

References

REFERENCES

[1]Case, John, Enumeration reducibility and partial degrees, Annals of Mathematical Logic, vol. 2 (1971), pp. 419–440.CrossRefGoogle Scholar
[2]Davis, Martin, Computability and unsolvability, McGraw-Hill, New York, 1958.Google Scholar
[3]Friedberg, Richard, A criterion for completeness of degrees of unsolvability, Zeitschrift für mathematische Logik unci Grundlagen der Mathematik, vol. 5 (1957), pp. 117–125.CrossRefGoogle Scholar
[4]Gutteridge, Lance, Some results on enumeration reducibility, Ph.D. Dissertation, Simon Fraser University, 1971.Google Scholar
[5]Kleene, Stephen C., Introduction to metamathematics, Van Nostrand, Princeton, New Jersey, 1952.Google Scholar
[6]Kleene, Stephen C. and Post, Emil, The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics (2), vol. 59 (1954), pp. 379–407.CrossRefGoogle Scholar
[7]Lagemann, Jay J. T., Embedding theorems in the reducibility ordering of partial degrees, Ph.D. Dissertation, Massachusetts Institute of Technology, 1971.Google Scholar
[8]Medvedev, Yu. T., Degrees of difficulty of the mass problem, Doklady Academii Nauk SSSR, vol. 104 (1955), pp. 501–504. (Russian)Google Scholar
[9]Myhill, John, Note on degrees of partial functions, Proceedings of the American Mathematical Society, vol. 12 (1961), pp. 519–521.CrossRefGoogle Scholar
[10]Rogers, Hartley Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[11]Sacks, Gerald E., Degrees of unsolvability, Annals of Mathematics Studies, No. 55, Princeton, New Jersey, 1963.Google Scholar
[12]Sasso, Leonard P., Degrees of unsolvability of partial functions, Ph.D. Dissertation, University of California, Berkeley, 1971.Google Scholar
[13]Sasso, Leonard P., A minimal partial degree ≤0′, Proceedings of the American Mathematical Society, vol. 38 (1973), pp. 388–392.Google Scholar
[14]Spector, Clifford, On degrees of recursive unsolvability, Annals of Mathematics, vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar