Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Uniformly reflexive structures: On the nature of gödelizations and relative computability

Author: Eric G. Wagner
Journal: Trans. Amer. Math. Soc. 144 (1969), 1-41
MSC: Primary 02.70
MathSciNet review: 0249297
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we present an axiomatic theory within which much of the theory of computability can be developed in an abstract manner. The paper is based on the axiomatically defined concept of a Uniformly Reflexive Structure (U.R.S.). The axioms are chosen so as to capture what we view to be the essential properties of a ``gödelization'' of a set of functions on arbitrary infinite domain. It can be shown that (with a ``standard gödelization") both the partial recursive functions and the meta-recursive functions satisfy the axioms of U.R.S. In the first part of this paper, we define U.R.S. and develop the basic working theorems of the subject (e.g., analogues of the Kleene recursion theorems). The greater part of the paper is concerned with applying these basic results to (1) investigating the properties of gödelizations, and (2) developing an intrinsic theory of relative computability. The notion of relative computability which we develop is equivalent to Turing reducibility when applied to the partial recursive functions. Applied to appropriate U.R.S. on arbitrary domains, it provides an upper-semi-lattice ordering on the set of all functions (both total and partial) on that domain.

References [Enhancements On Off] (What's this?)

  • [1] M. Davis, Computability and unsolvability, McGraw-Hill, New York, 1958. MR 0124208 (23:A1525)
  • [2] R. M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309-316. MR 0109125 (22:13)
  • [3] H. M. Friedman, Personal communication.
  • [4] H. Rogers, Jr., Gödel numberings of partial recursive functions, J. Symbolic Logic 23 (1958), 331-341. MR 0103821 (21:2585)
  • [5] -, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 0224462 (37:61)
  • [6] M. Schönfinkel, Über die Bausteine der Mathematischen Logik, Math. Ann. 92 (1922), 305-316. MR 1512218
  • [7] R. M. Smullyan, Theory of formal systems, Ann. of Math. Studies, No. 47, Princeton Univ. Press, Princeton, N. J., 1961. MR 0152429 (27:2409)
  • [8] H. R. Strong, Jr., An algebraic approach through uniformly reflexive structures to generalized recursive function theory, Doctoral Dissertation, Univ. of Washington, Seattle, Wash., 1967.
  • [9] -, Algebraically generalized recursive function theory, IBM J. Res. Develop. 12. (1968), 465-475. MR 0262079 (41:6689)
  • [10] E. G. Wagner, Uniformly reflexive structures: Toward an abstract theory of computability, Doctoral Dissertation, Columbia Univ., New York, 1963. Also, IBM Res. Rep. RC 934, 1963.
  • [11] -, Uniformly reflexive structures. II, IBM Res. Rep. RC 1135, 1964.
  • [12] -, Uniformly reflexive structures. III; Constructible and highly constructible U.R.S., IBM Res. Rep. RC 1341, 1964.
  • [13] -, Uniformly reflexive structures. IV; Many-one reducibility and strongly creative functions, IBM Res. Rep. RC 1397, 1965.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02.70

Retrieve articles in all journals with MSC: 02.70

Additional Information

Article copyright: © Copyright 1969 American Mathematical Society

American Mathematical Society