Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2025-01-03T10:36:00.409Z Has data issue: false hasContentIssue false
  • English
  • Français

A cornucopia of minimal degrees

Published online by Cambridge University Press:  12 March 2014

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

Extract

The first minimal degree construction is due to Spector [7]. To this Sacks [5] has added the priority method of Friedberg [1] and Muchnik [4] to obtain a minimal degree less than 0′. Sacks' methods have been modified in several directions to obtain minimal degrees satisfying various incomparability conditions.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 35 , Issue 3 , September 1970 , pp. 383 - 388
Copyright
Copyright © Association for Symbolic Logic 1971

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

[1]Friedberg, R. M., Two recursively enumerable sets of incomparable degrees of unsolvability, Proceedings of the National Academy of Sciences of the United States of America, vol. 43 (1957), pp. 236–238.CrossRefGoogle ScholarPubMed
[2]Fukuyama, M., A remark on minimal degrees, Science Reports of the Tokyo Kyoiku Daigaka. Section A, vol. 9 (1968), pp. 255–256.Google Scholar
[3]Kleené, S. C., Introduction to metamathematics, New York, 1952.Google Scholar
[4]Muchnik, A. A., On the unsolvability of the problem of reducibility in the theory of algorithms (Russian), Doklady Akademii Nauk SSSR, n.s., vol. 108 (1956), pp. 194–197.Google Scholar
[5]Sacks, G. E., Degrees of unsolvability, Princeton, 1961.Google Scholar
[6]Shoenfield, J. R., A theorem on minimal degrees, this Journal, vol. 31 (1966), pp. 539–544.Google Scholar
[7]Spector, C. M., On degrees of recursive unsolvability, Annals of mathematics, vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar
[8]Yates, C. E. M., Recursively enumerable degrees and the degrees less than 0′, Sets models, and recursion theory, ed. Crossley, J. N., Amsterdam (1967).Google Scholar