CONNECTIONS BETWEEN IDENTIFYING FUNCTIONALS, STANDARDIZING OPERATIONS, AND COMPUTABLE NUMBERINGS

Functionals and operations have been studied extensively in the theory of recursive functions (cf. [13]). We want to investigate here properties of idententifying functionals and standardizing operations, mainly concerning the classes of recursive functions on which these functionals and operations do exist. Let p be any acceptable Godel numbering of all partial recursive functions and let U be any class of recursive functions. A functional F on U is called an identifying functional iff pF(/) = f for any function f E U . An operation on U defined by a function s is called a standardizing operation iff p'r(i) = f for any function f E U and any i E N such that p, = f . Identifying functionals are an important object of investigation in the theory of inductive inference (cf. [I], [3], [lo], [12]> [IS]). On the other hand, though being their correspondence among the operations, as far as we know there are only a few results concerning standardizing operations (cf. [ll]). We consider identifying recursive functionals and Standardizing effective operations as well as identifying limit recursive functionals and standardizing limit effective operations. For these types of identifying functionals we present equivalent notions of standardizing operations and vice versa. We also compare the power of the four types of functionals and operations, respectively. However, our main intention is to characterize the domains of these functionals and operations, i.e. the classes of recursive functions which can be identified or standardized at all. While t,he domains of the partial recursive functions were described by enumerations of sets of numbers, it seems quite natural to us to describe the domains of functionals and operations by numberings of sets of functions. In doing this we were interested in providing these numberings with properties such as discreteness, reducibility, equivalence, and decidability. We note that for characterizing identifiable classes of functions discreteness was introduced in [17] and reducibility was first. used in [7]. Let Pk, R ' denote the set of all partial recursive and recursive functions of k variables, respectively. We write P, R instead of PI, R'. Let p, ptZ) be any acceptable Godel numbering of P, P2, respectively. Every function y E Pz is called a numbering. P, = {h y(i, 5 ) I i E N ) denotes the class of partial recursive functions enumerated by y. Instead of t y(i, x) we write y , or y ( i , .). A numbering y is said to be reducible to a numbering y' ( y 5 y') iff there is a function c E R such that y i = y:(,, for all i EN. A numbering y is called a one-one numbering iff y, + y j for all i, j E N, i + j . A numbering y is called a U-one-one numbering, where U s R iff for any function f E U, there is exactly one number i such that y, = f . A class V s P is called enumerable iff there is a numbering y such that P, = V ; then y is said to be a nzimbering of V . V is called (U-)om-one enumerable iff there is a (U-)one-one numbering of V .