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

An invariance notion in recursion theory1

Published online by Cambridge University Press:  12 March 2014

Robert E. Byerly
Robert E. Byerly*
Affiliation:
Ohio State University, Columbus, Ohio 43210
*
Texas Tech University, Lubbock, Texas 79409
Get access Rights & Permissions [Opens in a new window]

Abstract

A set of gödel numbers is invariant if it is closed under automorphisms of (ω, ·), where ω is the set of all gödel numbers of partial recursive functions and · is application (i.e., n · m ≃ φn(m)). The invariant arithmetic sets are investigated, and the invariant recursively enumerable sets and partial recursive functions are partially characterized.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 47 , Issue 1 , March 1982 , pp. 48 - 66
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.)

Footnotes

1

The author thanks the referee for a number of valuable suggestions.

References

REFERENCES

[1]Byerly, R., Ph.D. dissertation, State University of New York at Buffalo, 1979.Google Scholar
[2]Byerly, R., Some properties of invariant sets (to appear).Google Scholar
[3]Byerly, R., Invariance in recursion theory on admissible ordinals (to appear).Google Scholar
[4]Chang, C.C. and Keisler, H. J., Model theory, North-Holland, Amsterdam, 1973.Google Scholar
[5]Friedman, H., Axiomatic recursive function theory, Logic Colloquium '69 (Gandy, R.O. and Yates, C. M. E., Editors) North-Holland, Amsterdam, 1971, pp. 113–137.CrossRefGoogle Scholar
[6]Jockusch, C. and Soare, R., Post's problem and his hypersimple set, this Journal, vol. 38 (1973), pp. 446–452.Google Scholar
[7]Rogers, H., Some problems of definability in recursive function theory, Sets, models, and recursion theory (Crossley, J., Editor), North-Holland, Amsterdam, 1967, pp. 183–201.CrossRefGoogle Scholar
[8]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[9]Strong, H., Algebraically generalized recursive function theory, I. B. M. Journal of Research and Development, vol. 12 (1968), pp. 465–475.Google Scholar
[10]Wagner, E., Uniformly reflexive structures: On the nature of gödelizations and relative computability, Transactions of the American Mathematical Society, vol. 144 (1969), pp. 1–41.Google Scholar
[11]Case, J., Periodicity in generations of automata, Mathematical Systems Theory, vol. 8(1974), pp. 15–32.CrossRefGoogle Scholar
[12]Goodman, N., A simplification of combinatory logic, this Journal, vol. 37 (1972), pp. 225–246.Google Scholar