Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-07T17:30:04.747Z Has data issue: false hasContentIssue false
  • English
  • Français

Recursion theory and the lambda-calculus

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 semantics for the lambda-calculus due to Friedman is used to describe a large and natural class of categorical recursion-theoretic notions. It is shown that if e1 and e2 are gödel numbers for partial recursive functions in two standard ω-URS's which both act like the same closed lambda-term, then there is an isomorphism of the two ω-URS's which carries e1 to e2.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 47 , Issue 1 , March 1982 , pp. 67 - 83
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]Byerly, R., Contributions to axiomatic recursion theory, Ph.D. dissertation, State University of New York at Buffalo, 1979.Google Scholar
[2]Byerly, R., An invariance notion in recursion theory, this Journal,vol. 47 (1982), pp. 48–66.Google Scholar
[3]Chang, C. C. and Keisler, H. J., Model theory, North-Holland, Amsterdam, 1973.Google Scholar
[4]Church, A., The calculi of lambda conversion, Princeton University Press, Princeton, New Jersey, 1941.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]Goodman, N., A simplification of combinatory logic, this Journal, vol. 37 (1972), pp. 225–246.Google Scholar
[7]Riccardi, G., The independence of control structures in theoretical programming systems, Journal of Computer and Systems Sciences (to appear).Google Scholar
[8]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[9]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