Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-24T12:36:47.386Z Has data issue: false hasContentIssue false
  • English
  • Français

Partial degrees and the density problem

Published online by Cambridge University Press:  12 March 2014

S. B. Cooper
S. B. Cooper*
Affiliation:
University of Leeds, Leeds, Great Britain
Get access Rights & Permissions [Opens in a new window]

Extract

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 Introduction to metamathematics [4]. Following Myhill [7], this was made more explicit in Hartley Rogers, Jr., Theory of recursive functions and effective computability [8, pp. 146, 279], where some basic properties of the partial degrees or (equivalent, but notationally more convenient) the enumeration degrees, 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 quasi-minimal partial degrees (that is, nonrecursive partial degrees with no nonrecursive total predecessors) is proved.

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 ‘consistent’ computation tree—cf. Sasso [10]). His construction of minimal ‘partial degrees’ [11], while of interest in itself, left open the analogous problem for the more standard partial degree structure.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 47 , Issue 4 , December 1982 , pp. 854 - 859
Copyright
Copyright © Association for Symbolic Logic 1982

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

References

REFERENCES

1.Case, John, Enumeration reducibility and partial degrees, Annals of Mathematical Logic, vol. 2 (1970/1971), pp. 419–439.CrossRefGoogle Scholar
2.Gutteridge, Lance, Some results on enumeration reducibility, Ph.D. Thesis, Simon Fraser University, 1971.Google Scholar
3.Gutteridge, Lance, The partial degrees are dense, preprint, 1971 (unpublished).Google Scholar
4.Kleene, S.C., Introduction to metantathematics, North-Holland, Amsterdam, 1952.Google Scholar
5.Lagemann, Jay J.T., Embedding theorems in the reducibility ordering of partial degrees, Ph.D. Thesis, Massachusetts Institute of Technology, 1971.Google Scholar
6.Medvedev, Yu. T., Degrees of difficulty of the mass problem, Doklady Academii Nauk SSSR, vol. 104 (1955), pp. 501–504. (Russian).Google Scholar
7.Myhill, John, A note on degrees of partial functions, Proceedings of the American Mathematical Society, vol. 12 (1961), pp. 519–521.CrossRefGoogle Scholar
8.Rogers, Hartley Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
9.Sasso, Leonard P. Jr., Degrees of unsolvability of partial functions, Ph.D. Thesis, University of California, Berkeley, 1971.Google Scholar