UNIFORMLY REFLEXIVE STRUCTURES: ON THE NATURE OF GODELIZATIONS AND RELATIVE COMPUTABILITY
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 "godelization" of a set of functions on arbitrary infinite domain. It can be shown that (with a "standard g6delization") 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 godelizations, and (2) developing an intrinsic theory of relative com- putability. 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. 0. Introduction. In this paper we present the axioms of an abstract theory of computability (the theory of Uniformly Reflexive Structures) and employ it to establish a number of general results on godelizations and to develop an intrinsic approach to the study of relative computability. To a first approximation, a Uniformly Reflexive Structure (a U.R.S.) is a set of functions on an arbitrary infinite domain together with a special indexing of the functions by elements of the domain. We call these indexings g6delizations; this terminology is apt in that the partial recursive functions with a "standard g6deli- zation" (such as given by Davis (1)) form a U.R.S. For each element u of the domain, the indexing gives us a 1-ary function denoted