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 Free Access

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.

**[1]**Martin Davis,*Computability and unsolvability*, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR**0124208****[2]**Richard M. Friedberg,*Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication*, J. Symb. Logic**23**(1958), 309–316. MR**0109125****[3]**H. M. Friedman, Personal communication.**[4]**Hartley Rogers Jr.,*Gödel numberings of partial recursive functions*, J. Symb. Logic**23**(1958), 331–341. MR**0103821****[5]**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****[6]**M. Schönfinkel,*Über die Bausteine der mathematischen Logik*, Math. Ann.**92**(1924), no. 3-4, 305–316 (German). MR**1512218**, 10.1007/BF01448013**[7]**Raymond M. Smullyan,*Theory of formal systems*, Revised edition, Princeton University Press, Princeton, N. J., 1961. MR**0152429****[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]**H. R. Strong,*Algebraically generalized recursive function theory*, IBM J. Res. Develop.**12**(1968), 465–475. MR**0262079****[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.

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

Retrieve articles in all journals with MSC: 02.70

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9947-1969-0249297-9

Article copyright:
© Copyright 1969
American Mathematical Society