On the Interplay Between Inductive Inference of
Recursive Functions, Complexity Theory andRecursive Numberings
Thomas Zeugmann
Division of Computer Science,
Hokkaido University, Sapporo 060-0814, Japanthomas@ist.hokudai.ac.jp

Abstract. The present paper surveys some results from the inductive
inference of recursive functions, which are related to the characterizationof inferrible function classes in terms of complexity theory, and in termsof recursive numberings. Some new results and open problems are also
included.

1

Introduction

Inductive inference of recursive functions goes back to Gold [11], who consideredlearning in the limit, and has attracted a large amount of interest ever since.
In learning in the limit an inference strategy S is successively fed the graphf (0), f (1), . . . of a recursive function in natural order and on every initial segmentof it, the strategy has to output a hypothesis, which is a natural number. These
numbers are interpreted as programs in a fixed Gödel numbering ϕ of all partial
recursive functions over the natural numbers. The sequence of all hypotheses
output on f has then to stabilize on a number i such that ϕi = f . A strategy
infers a class U of recursive functions, if it infers every function from U .
One of the most influential papers has been Blum and Blum [6], who introduced two types of characterizations of learnable function classes in terms ofcomputational complexity. The gist behind such characterizations is that classes
U of recursive functions are learnable with respect to a given learning criterion if
and only if all functions in U possess a particular complexity theoretic property.
The learning criterion considered is reliable inference on the set R , where R
denotes the set of all recursive functions. We denote the family of all classes
U which are reliably inferable by R-REL . Here reliability means the learnerconverges on any function f from R iff it learns f in the limit. In the firstversion, operator honesty classes are used. If O is a total effective operator
then a function f is said to be O -honest if O(f ) is an upper bound for thecomplexity Φi for all but finitely many arguments of ϕi , where ϕi = f . Then
Blum and Blum [6] showed that a class U is in R-REL iff there is a total
effective operator O such that every function f ∈ U is O -honest. Operatorhonest characterizations are also called a priori characterizations.

On the Interplay Between Inductive Inference

125

In the second version, one considers functions which possess a fastest program
modulo a general recursive operator O (called O -compression index). Now, thea posteriori characterization is as follows: A class U is in R-REL iff there isa general recursive operator O such that every function from U has an O compression index.
Combining these two characterizations yields that the family of operatorhonesty classes coincides with the family of the operator compressed classes.
While operator honesty characterizations have been obtained for many learning criterions (cf. [29] and the references therein), the situation concerning a
posteriori characterizations is much less satisfactory. Some results were shownin [27], but many problems remain open. In particular, it would be quite interesting to have an a posteriori characterization for T-REL . The learning criterion
T-REL is defined as R-REL , but reliability is required on the set T of all total
functions. Note that T-REL ⊂ R-REL . Also, we shall present an a posteriori
characterization for the function classes which are T -consistently learnable withδ -delay (cf. [1] for a formal definition). Intuitively speaking, a T -consistent δ delayed learning strategy correctly reflects all inputs seen so far except the last δones, where δ is a natural number.
Note that there are also prominent examples of learning criterions for whicheven a priori characterizations are missing. These include the behaviorally correct
learnable functions classes (cf. [9, 8] for more information). So in both cases wealso point to the open problem whether or not one can show the non-existenceof such desired characterizations.
Moreover, in Blum and Blum [6] the a posteriori characterization of R-REL
has been used to show that some interesting function classes are in R-REL ,e.g., the class of approximations of the halting problem. Stephan and Zeugmann [22] extended these results to several classes based on approximations
to non-recursive functions. Besides these results, our knowledge concerning thelearnability of interesting function classes is severely limited, except the recursively enumerable functions classes (or subsets thereof), and with respect tofunction classes used to achieve separations.
Finally, the problem of suitable hypothesis spaces is considered. That is,
instead of Gödel numberings one is interested in numberings having learnerfriendly properties. Again, we survey some illustrative results, present some newones, and outline open problems. Note that one can also combine the results
obtained in this setting with the results mentioned above, i.e., one can derivesome complexity theoretic properties of such numberings.

2

Preliminaries

Unspecified notations follow Rogers [21]. By N = {0, 1, 2, . . .} we denote theset of all natural numbers. The set of all finite sequences of natural numbers is. b to be a − b if a ≥ b and 0 ,denoted by N∗ . For a, b ∈ N we define a −otherwise.

126

T. Zeugmann

The cardinality of a set S is denoted by |S| . We write ℘(S) for the power
set of set S . Let ∅, ∈, ⊂, ⊆ , ⊃ , ⊇ , and # denote the empty set, elementof, proper subset, subset, proper superset, superset, and incomparability of sets,
respectively.
By P and T we denote the set of all partial and total functions of one
variable over N , respectively. The classes of all partial recursive and recursivefunctions of one, and two arguments over N are denoted by P, P 2 , R , and R2 ,respectively. Furthermore, for any f ∈ P we use dom(f ) to denote the domainof the function f , i.e., dom(f ) =df {x | x ∈ N, f (x) is defined} . Additionally,by range(f ) we denote the range of f , i.e., range(f ) =df {f (x) | x ∈ dom(f )} .
Let f, g ∈ P be any partial functions. We write f ⊆ g if for all x ∈ dom(f )the condition f (x) = g(x) is satisfied. By R0,1 and Rmon we denote the set ofall {0, 1} -valued recursive functions (recursive predicates) and of all monotone
recursive functions, respectively.
Every function ψ ∈ P 2 is said to be a numbering. Let ψ ∈ P 2 , then we
write ψi instead of λx.ψ(i, x) , set Pψ = {ψi | i ∈ N} and Rψ = Pψ ∩ R .
Consequently, if f ∈ Pψ , then there is a number i such that f = ψi . If f ∈ P
and i ∈ N are such that ψi = f , then i is called a ψ -program for f . Let ψ be
any numbering, and let i ∈ N ; if ψi (x) is defined (abbr. ψi (x) ↓ ) then we also
say that ψi (x) converges. Otherwise, ψi (x) is said to diverge (abbr. ψi (x) ↑ ).
A numbering ϕ ∈ P 2 is called a Gödel numbering (cf. Rogers [21]) if Pϕ = P ,and for every numbering ψ ∈ P 2 , there is a c ∈ R such that ψi = ϕc(i)for all i ∈ N . Göd denotes the set of all Gödel numberings. Furthermore, wewrite (ϕ, Φ) to denote any complexity measure as defined in Blum [7]. Thatis, ϕ ∈ Göd , Φ ∈ P 2 and (1) dom(ϕi ) = dom(Φi ) for all i ∈ N and (2) the
predicate “ Φi (x) = y ” is uniformly recursive for all i, x, y ∈ N .
Moreover, let NUM = {U | ∃ψ[ψ ∈ R2 ∧ U ⊆ Pψ ]} denote the family of all
subsets of all recursively enumerable classes of recursive functions.
Furthermore, using a fixed encoding h. . .i of N∗ onto N we write f n insteadof h(f (0), . . . , f (n))i , for any n ∈ N, f ∈ R .
The quantifier ∀∞ stands for “almost everywhere” and means “all but finitely
many.” Finally, a sequence (jn )j∈N of natural numbers is said to converge to thenumber j if all but finitely many numbers of it are equal to j . Next we definesome concepts of learning.
Definition 1 (Gold [11, 12]). Let U ⊆ R and let ψ ∈ P 2 . The class U is
said to be learnable in the limit with respect to ψ if there is a strategy S ∈ Psuch that for each function f ∈ U ,(1) for all n ∈ N , S(f n ) is defined,(2) there is a j ∈ N such that ψj = f and the sequence (S(f n ))n∈N converges to j .
If a class U is learnable in the limit with respect to ψ by a strategy S , thenwe write U ∈ LIMψS(S) . Let LIMψ = {U | U is learnable in the limit w.r.t. ψ} ,and define LIM = ψ∈P 2 LIMψ .

On the Interplay Between Inductive Inference127

As far as the semantics of the hypotheses output by a strategy S is concerned,
whenever S is defined on input f n , then we always interpret the number S(f n )as a ψ –number. This convention is adopted to all the definitions below. Furthermore, note that LIMϕ = LIM for any ϕ ∈ Göd . In the above definition LIM
stands for “limit.”
Looking at Definition 1 one may be tempted to think that it is too general.
Maybe we should add some requirements that seem very natural. Since it may be
hard for a strategy to know which inputs may occur, it could be very convenient
to require S ∈ R . Furthermore, if the strategy outputs a program i such thatϕi ∈/ R , then this output cannot be correct. Hence, it seems natural to require thestrategy to output exclusively hypotheses describing recursive functions. Thesedemands directly yield the following definition:
Definition 2 (Wiehagen [24]). Let U ⊆ R and let ψ ∈ P 2 . The class U is
said to be R –totally learnable with respect to ψ if there is a strategy S ∈ Rsuch that(1) ψS(n) ∈ R for all n ∈ N ,(2) for each f ∈ U there is a j ∈ N such that ψj = f , and (S(f n ))n∈N
converges to j .
R-TOTALψ (S) , R-TOTALψ , and R-TOTAL are defined in analogy to theabove.
However, now it is not difficult to show that R-TOTAL = NUM (cf. Zeugmann and Zilles [29, Theorem 2]). This is the first characterization of a learning
type in terms of recursive numberings. This characterization shows how R -total
learning can be achieved, i.e., by using the well-known identification by enumeration technique.
Next, we recall the definition of reliable learning introduced by Blum andBlum [6] and Minicozzi [19]. Intuitively, a learner M is reliable provided it
converges if and only if it learns.
Definition 3 (Blum and Blum [6], Minicozzi [19]). Let U ⊆ R , M ⊆ T
and let ϕ ∈ Göd . The class U is said to be reliably learnable on M if there isa strategy S ∈ R such that
(1) U ∈ LIMϕ (S) , and(2) for all functions f ∈ M , if the sequence (S(f n ))n∈N converges, say to j ,then ϕj = f .
Let M-REL denote the family of all classes U that are reliably learnable on M .
Note that neither in Definition 1 nor in Definition 3 a requirement is madeconcerning the intermediate hypotheses output by the strategy S . The following definition is obtained from Definition 1 by adding the requirement that S
correctly reflects all but the last δ data seen so far.

128

T. Zeugmann

Definition 4 (Akama and Zeugmann [1]). Let U ⊆ R , let ψ ∈ P 2 and letδ ∈ N . The class U is called consistently learnable in the limit with δ -delay
with respect to ψ if there is a strategy S ∈ P such that
(1) U ∈ LIMψ (S) ,(2) ψS(f n ) (x) = f (x) for all f ∈ U , n ∈ N and all x such that x + δ ≤ n .
We define CONSδψ (S) , CONSδψ , and CONSδ analogously to the above.
We note that for δ = 0 Barzdin’s [4] original definition of CONS is obtained.
We therefore usually omit the upper index δ if δ = 0 . This is also done for theother version of consistent learning defined below. We use the term δ -delay,
since a consistent strategy with δ -delay correctly reflects all but at most thelast δ data seen so far. If a strategy S learns a function class U in the sense of
Definition 4, then we refer to S as a δ -delayed consistent strategy.
In Definition 4 consistency with δ -delay is only demanded for inputs that
correspond to some function f from the target class U . Note that for δ = 0
the following definition incorporates Wiehagen and Liepe’s [23] requirement on
a strategy to work consistently on all inputs.
Definition 5 (Akama and Zeugmann [1]). Let U ⊆ R , let ψ ∈ P 2 and letδ ∈ N . The class U is called T –consistently learnable in the limit with δ -delay
with respect to ψ if there is a strategy S ∈ R such that
(1) U ∈ CONSδψ (S) ,(2) ψS(f n ) (x) = f (x) for all f ∈ R , n ∈ N and all x such that x + δ ≤ n .
We define T - CONSδψ (S) , T - CONSδψ , and T - CONSδ analogously to the above.
We note that for all δ ∈ N and all learning types LT ∈ {CONSδ , T - CONSδ }we have LTϕ = LT for every ϕ ∈ Göd .
Finally, we look at another mode of convergence which goes back to Feldman [9], who called it matching in the limit and considered it in the setting oflearning languages. The difference to the mode of convergence used in Definition 1, which is actually syntactic convergence, is to relax the requirement thatthe sequence of hypotheses has to converge to a correct program, by semantic convergence. Here by semantic convergence we mean that after some point
all hypotheses are correct but not necessarily identical. Nowadays, the resulting
learning model is usually referred to as behaviorally correct learning. This term
was coined by Case and Smith [8]. As far as learning of recursive functions isconcerned, behaviorally correct learning was formalized by Barzdin [2, 3].
Definition 6 (Barzdin [2, 3]). Let U ⊆ R and let ψ ∈ P 2 . The class U is
said to be behaviorally correctly learnable with respect to ψ if there is a strategy
S ∈ P such that for each function f ∈ U ,(1) for all n ∈ N , S(f n ) is defined,(2) ψS(f n ) = f for all but finitely many n ∈ N .
If U is behaviorally correctly learnable with respect to ψ by a strategy S , wewrite U ∈ BCψ (S) . BCψ and BC are defined analogously to the above above.

On the Interplay Between Inductive Inference3

129Characterizations in Terms of Complexity

We continue with characterizations in terms of computational complexity. Characterizations are a useful tool to get a better understanding of what different
learning types have in common and where the differences are. They may also help
to overcome difficulties that arise in the design of powerful learning algorithms.
Let us recall the needed definitions of several types of computable operators.
Let (Fx )x∈N be the canonical enumeration of all finite functions.
Definition 7 (Rogers [21]). A mapping O : P 7→ P from partial functions topartial functions is called a partial recursive operator if there is a recursively
enumerable set W ⊂ N3 such that for any y, z ∈ N it holds that O(f )(y) = z
if there is x ∈ N such that (x, y, z) ∈ W and f extends the finite function Fx .
Furthermore, O is said to be a general recursive operator if T ⊆ dom(O) ,and f ∈ T implies O(f ) ∈ T .
A mapping O : P 7→ P is called an effective operator if there is a functiong ∈ R such that O(ϕi ) = ϕg(i) for all i ∈ N . An effective operator O is said to
be total effective provided that R ⊆ dom(O) , and ϕi ∈ R implies O(ϕi ) ∈ R .
For more information about general recursive operators and effective operators we refer the reader to [14, 20, 28]. If O is an operator which maps functions
to functions, we write O(f, x) to denote the value of the function O(f ) at theargument x .
Definition 8. A partial recursive operator O : P 7→ P is said to be monotone
if for all functions f, g ∈ dom(O) the following condition is satisfied:If ∀∞ x[f (x) ≤ g(x)] then ∀∞ x[O(f, x) ≤ O(g, x)] .
Let O be any arbitrarily fixed operator and let M ⊆ P . Then the abbreviation “ O(M ) ⊆ M ” stands for “ M ⊆ dom(O) and f ∈ M implies thatO(f ) ∈ M .”Any computable operator can be realized by a 3-tape Turing machine T
which works as follows: If for an arbitrary function f ∈ dom(O) , all pairs(x, f (x)) , x ∈ dom(f ) are written down on the input tape of T (repetitions
are allowed), then T will write exactly all pairs (x, O(f, x)) on the output tapeof T (under unlimited working time).
Let O be a partial recursive operator, a general recursive operator or a total
effective operator. Then, for f ∈ dom(O) , m ∈ N we set: ∆O(f, m) = “theleast n such that, for all x ≤ n , f (x) is defined and, for the computation ofO(f, m) , the Turing machine T only uses the pairs (x, f (x)) with x ≤ n ; ifsuch an n does not exist, we set ∆O(f, m) = ∞ .”For any function u ∈ R we define Ωu to be the set of all partial recursive
operators O satisfying ∆O(f, m) ≤ u(m) for all f ∈ dom(O) . For the sake ofnotation, below we shall use id +δ , δ ∈ N , to denote the function u(x) = x + δ
for all x ∈ N .
Blum and Blum [6] initiated the characterization of learning types in termsof computational complexity. Here they distinguished between a priori characterizations and a posteriori characterizations. In order to obtain an a priori

130

T. Zeugmanncharacterization one starts from classes of operator honesty complexity classes,
which are defined as follows: Let O be a computable operator. Then we define
CO =df {f | ∃i[ϕi = f ∧ ∀∞ x[Φi (x) ≤ O(f, x)]]} ∩ R .

(1)

That is, every function in CO possesses a program i such that the complexityof program i is in a computable way bounded by its function values, namelyby O(f, x) almost everywhere. So let LT be any learning type, e.g., learning in
the limit. Then the general form of an a priori characterization of LT looks asfollows:
Theorem 1. Let U ⊆ R be any class. Then we have U ∈ LT if and only ifthere is a computable operator O such that U ⊆ CO , where the operator O has
to fulfill some additional properties.
Example 1. Consider the set of all operators which can be defined as follows:
For any t ∈ R we define O(f, x) =df t(x) for every f ∈ R and x ∈ N . Thenthe complexity classes defined in (1) have the form
Ct = {f | ∃i[ϕi = f ∧ ∀∞ x[Φi (x) ≤ t(x)]]} ∩ R .

(2)

and Theorem 1 yields the following a priori characterization of R-TOTAL :Let U ⊆ R be any class. Then we have U ∈ R-TOTAL if and only if there
is a recursive function t ∈ R such that U ⊆ Ct .
Since this theorem holds obviously also in case that U = Ct , we can directly
use the fact that R-TOTAL = NUM and conclude that Ct ∈ NUM for everyt ∈ R . Thus, using the a priori characterization of R-TOTAL we could easily
reprove Ct ∈ NUM , which was originally shown by McCreight and Meyer [17].
Example 2. Note that for every general recursive operator O there is a monotone general recursive operator M such that O(f, x) ≤ M(f, x) for every function f ∈ T and almost all x ∈ N (cf. Meyer and Fischer [18]). Furthermore,
Grabowski [13] proved the following a priori characterization of T-REL :Let U ⊆ R be any class. Then we have U ∈ T-REL if and only if there exists
a general recursive operator O such that U ⊆ CO .
Using that every function f ∈ R0,1 satisfies f (x) ≤ 1 for all x ∈ N we
directly see by an easy application of Meyer and Fischer’s [18] result that
T-REL ∩℘ (R0,1 ) = R-TOTAL ∩℘ (R0,1 ) = NUM ∩℘ (R0,1 ) ;(3)i.e., reliable learning on the total functions restricted to classes of recursive predicates is exactly as powerful as R -total learning restricted to classes of recursive
predicates. On the other hand, R-TOTAL ⊂ T-REL (cf. Grabowski [13]).
Moreover, Stephan and Zeugmann [22] showed that
NUM ∩℘ (R0,1 ) ⊂ R-REL ∩℘ (R0,1 ) .

(4)The latter result was already published in Grabowski [13], but the new proof
is much easier. It uses the class of approximations to the halting problem that

On the Interplay Between Inductive Inference131

has been considered in [6]. This class is defined as follows: Let (ϕ, Φ) be any
complexity measure, and let τ ∈ R be such that for all i ∈ N
if Φi (x) ↓ and Φx (x) ≤ Φi (x) ; 1,0,if Φi (x) ↓ and ¬[Φx (x) ≤ Φi (x)] ;ϕτ (i) (x) =df
↑,otherwise .
Now, we set B = {ϕτ (i) | i ∈ N and Φi ∈ Rmon } . Then in [22, Theorems 2
and 3] both results were proved B ∈/ NUM and B ∈ R-REL yielding (4). We
shall come back to this class.
Now, one can combine this with the a priori characterization of R-REL
obtained by Blum and Blum [6], which is as follows:
Let U ⊆ R be any class. Then we have U ∈ R-REL if and only if there
exists a total effective operator O such that U ⊆ CO .
Note that the difference between the a priori characterization of T-REL
and R-REL is that the operator O is general recursive and total effective,
respectively.
Putting this all together, we directly see that Meyer and Fischer’s [18] boundability theorem cannot be strengthened by replacing “general recursive operator”
by “total effective operator.” And it also allows to show that there is an operatorhonesty complexity class CO generated by a total effective operator O such thate
CO 6⊆ COe for every general recursive operator O . For an explicit construction ofsuch an operator O we refer the reader to [14, 28].
Furthermore, Theorem 1 can be precisely stated for LIM , CONSδ , andT - CONSδ by using techniques from Blum and Blum [6], Wiehagen [24] andAkama and Zeugmann [1]. The proofs can be found in [29, Theorems 37,35,34].
Let U ⊆ R , then we have Let U ⊆ R , then we have U ∈ LIM if and only ifthere exists an effective operator O such that O(U) ⊆ R and U ⊆ CO .
Let U ⊆ R and let δ ∈ N ; then we have(1) U ∈ CONSδ if and only if there exists an effective operator O ∈ Ωid+δ suchthat O(U) ⊆ R and U ⊆ CO .
(2) U ∈ T - CONSδ if and only if there is a general recursive operator O ∈ Ωid+δ
such that U ⊆ CO .
These a priori characterizations shed also additional light to the fact that thelearning types T-REL , R-REL , and T - CONSδ are closed under union, while
LIM and CONSδ are not. In the former the operator O maps R to R , and in
the latter we only have O(U) ⊆ R .
As we have seen, operator honesty characterizations have been found formany learning types, but some important ones are missing. These include BC ,TOTAL , and conform learning. The learning criterion TOTAL is obtained from
Definition 2 by replacing S ∈ R by S ∈ P and adding S(f n ) ∈ R for all f ∈ U
and all n ∈ N . Conform learning is a modification of consistent learning, where
the requirement to correctly reflect all the functions values seen so far is replacedby the demand that the hypothesis output does never convergently contradict
inputs already seen (cf. [29, Definition 22]).

132

T. Zeugmann

Blum and Blum [6] also initiated the study of a posteriori characterizationsof learning types. In particular they showed that any class U ∈ R-REL can becharacterized in a way such that there exists a general recursive operator O forwhich every function from U is everywhere O -compressed.
For the sake of completeness we include here the definition of everywhere
O -compressed.
Definition 9 (Blum and Blum [6]). Let (ϕ, Φ) be a complexity measure, let
f ∈ R , and let O be a general recursive operator. Then a program i ∈ N is said
to be an O -compression index of f ( relative to (ϕ, Φ) ) if
(1) ϕi = f ,(2) ∀j[ϕj = f → ∀x Φi (x) ≤ O(Φj , max {i, j, x})] .
In this case we also say that the function f is everywhere O -compressed.
We note that Definition 9 formalizes the concept of a fastest program (modulo an operator O ) in a useful way. The O -compression index i satisfies thecondition Φi (x) ≤ O(Φj , x) for all but finitely many x ∈ N and all programs jcomputing the same function as program i does. Additionally, it also provides
an upper bound for the least argument n such that Φi ≤ O(Φj , x) for all x > n ,i.e., max {j, i} , and a computable majorante for those values m ≤ n for which
possibly Φi (m) > O(Φj , m) ; i.e., the value O(Φj , max {i, j} .
Of course, one can also consider the notion of everywhere O -compressed
functions for total effective operators or any other type of computable operator O
provided that all considered complexity functions Φj are in dom(O) .
Theorem 2 (Blum and Blum [6]). For every class U ⊆ R we have thefollowing: U ∈ R-REL if and only if there is a general recursive operator O
such that every function from U is everywhere O -compressed.
However, in [6] it remained open whether or not one can also reliably learn on
R an O -compression index for every function f in the target class U . We wereable to show (cf. [26]) that this is not always the case, when using the algorithm
described in [6]. Furthermore, in [27] we provided a suitable modification ofDefinition 9 resulting in a reliable O -compression index, and then showed thatsuch reliable O -compression indices are reliable learnable on R .
On the other hand, Blum and Blum [6, Section 8] used Theorem 2 to showthat several interesting functions classes are contained in R-REL including theclass B of approximations to the halting problem. Using different techniques, thisresult was extend in [22]. Conversely, one can also consider any particular general recursive operator op and ask for the resulting funcion class of everywhere
op -compressed functions, which are, via Theorem 2, known to be in R-REL .
Unfortunately, almost nothing is known in this area. Therefore, we would liketo encourage research along these two lines, i.e., considering interesting function
classes and figuring out to which learning type they belong, or to study special
general recursive operators with respect to the learning power they generate.
In order to characterize the learning type T - CONSδ , the following modification of Definition 9 turned out to be suitable:

On the Interplay Between Inductive Inference

133

Definition 10. Let (ϕ, Φ) be a complexity measure, let f ∈ R , and let O bea general recursive operator. Then a program i ∈ N is said to be an absolute
O -compression index of f ( relative to (ϕ, Φ) ) if
(1) ϕi = f ,(2) ∀j∀x[ϕj (y) = f (y) for all y ≤ ∆O(Φj , max{i, x})→ Φi (x) ≤ O(Φj , max{i, x})] .
In this case we also say that the function f is absolutely O -compressed.
To show the following lemma we have to restrict the class of complexity
measures a bit. We shall say that a complexity measure (ϕ, Φ) satisfies Property(+) if for all i, x ∈ N such that Φi (x) is defined the condition Φi (x) ≥ ϕi (x) is
satisfied.
Note that Property (+) is not very restrictive, since various “natural” complexity measures satisfy it.
Lemma 1. Let (ϕ, Φ) be a complexity measure satisfying Property (+) , andlet δ ∈ N be arbitrarily fixed. Furthermore, let U ∈ T - CONSδ . Then there isa general recursive operator O ∈ Ωid +δ such that every function from U isabsolutely O -compressed.
The following lemma shows that the condition presented in Lemma 1 is alsosufficient. Furthermore, this lemma holds for all complexity measures.
Lemma 2. Let (ϕ, Φ) be any complexity measure, let δ ∈ N be arbitrarily fixed,
let O ∈ Ωid +δ , and let U ⊆ R such that every function from U is absolutely
O -compressed. Then there is a strategy S ∈ R such that
(1) U ∈ T - CONSδϕ (S) ,(2) for every f ∈ U the sequence (S(f n ))n∈N converges to an absolute O compression index of f .
Furthermore, Lemmata 1 and 2 directly allow for the following theorem:
Theorem 3. Let (ϕ, Φ) be a complexity measure satisfying Property (+) , letδ ∈ N be arbitrarily fixed, and let U ⊆ R . Then we haveU ∈ T - CONSδϕ (S) if and only if there is an operator O ∈ Ωid +δ such thatevery function f from U is absolutely O -compressed. Furthermore, for everyf ∈ U the sequence (S(f n ))n∈N converges to an absolute O -compression index
of f .
Though we succeeded to show an a posteriori characterization for the learning
type T - CONSδ , it is not completely satisfactory, since it restricts the class ofadmissible complexity measures. Can this restriction be removed?
Nevertheless, combining the a priori characterization of T - CONSδ with thea posteriori characterization provided in Theorem 3 shows that the family of
operator honesty classes coincides for every δ ∈ N with the family of absolutely
operator compressed classes.
In this regard, it would be very nice to have also an a posteriori characterization of T-REL .

134

4

T. Zeugmann

Characterizations in Terms of Computable Numberings

The reader may be curious why our definitions of learning types include a numbering ψ with respect to which we aim to learn. After all, if one can learn a class
U with respect to some numbering ψ , then one can also infer U with respect
to any Gödel numbering ϕ . However, ψ may possess properties which facilitate
learning. For example, since R-TOTAL = NUM , for every class U ∈ R-TOTAL
there is numbering ψ ∈ R2 such that U ⊆ Rψ , and so the identification by
enumeration technique over ψ always succeeds.
Next, one may consider measurable numberings, which are defined as follows:
A numbering ψ ∈ P 2 is said to be measurable if the predicate “ ψi (x) = y ” is uniformly recursive in i, x, y (cf. Blum [7]). So, if ψ ∈ P 2 is a measurable numberingand U ⊆ R is such that U ⊆ Pψ , then the identification by enumeration technique is still applicable. A prominent example is the class U = {Φi | i ∈ N} ∩ R ,where (ϕ, Φ) is a complexity measure. Note that the halting problem for thenumbering Φ ∈ P 2 is undecidable (cf. [25, Lemma 3]).
Blum and Blum [6] also considered P-REL and P-REL (cf. Definition 3
for M = P and M = P , respectively) and showed that P-REL = P-REL .
Furthermore, they proved that a class U ⊆ R is in P-REL if and only if there
is measurable numbering ψ such that U ⊆ Pψ . Furthermore, the reliably on P
learnable function classes are characterized as the h -honesty function classes,
i.e., U ⊆ Ch , where the operator O is defined as O(f, n) = h(n, f (n)) (for amore detailed proof see [29, Theorems 12, 27]).
Note that these results also allow for a first answer of how inductive inference
strategies discover their errors. This problem was studied in detail in Freivalds,
Kinber, and Wiehagen [10]. The results obtained clearly show the importance ofcharacterizations in terms of computable numberings and related techniques.
One such technique is the amalgamation technique, which is given implicitly
in Barzdin and Podnieks [5] and then formalized in Wiehagen [24]. It was also
independently discovered by Case and Smith [8], who gave it its name. Let amal
be a recursive function mapping any finite set I of ψ -programs to a ϕ -program
such that for any x ∈ N , ϕamal(I) (x) is defined by running ϕi (x) for every i ∈ I
in parallel and taking the first value obtained, if any.
In order to have a further example, let us take a closer look at R-REL .
Here we have the additional problem that the strategy S has to diverge on
input initially growing finite segments of any function f it cannot learn. We
are interested in learning of how this can be achieved. We need the following
notation: For every f ∈ R and n ∈ N we write f [n] to denote the tuple(f (0), · · · , f (n)) . Moreover, for any f ∈ R , d ∈ R , and ψ ∈ P 2 we define
Hf = {i | i ∈ N, f [d(i)] ⊆ ψi } . In [15, Theorem 44] the following was shown:
Let U ⊆ R be any function class. Then U ∈ R-REL if and only if there isa numbering ψ ∈ P 2 and a function d ∈ R such that(1) for every f ∈ R , if Hf is finite, then Hf contains a ψ -program of thefunction f , and(2) for every f ∈ U , the set Hf is finite.

On the Interplay Between Inductive Inference

135

The proof of this theorem instructively answers where the ability to infer aclass U reliably on R may be come from. On the one hand, it comes from a wellchosen hypothesis space ψ . For any function f ∈ U there are only finitely many“candidates” in the set Hf including a ψ -program of f . So, in this case, theamalgamation technique succeeds. On the other hand, the infinity of this set Hffor every function which is not learned, then ensures that the strategy provided in
the proof has to diverge. This is also guaranteed by the amalgamation technique,since the sets of “candidates” forms a proper chain of finite sets and so arbitrarylarge hypotheses are output on every function f ∈ R with Hf being infinite.
There are many more characterization theorems in terms of computable numberings including some for LIM and BC (cf., e.g., [29, Section 8] and the references therein), and consistent learning with δ -delay (cf. [1, Section 3.2]).
However, there are also many open problems. For example, Kinber and Zeugmann [16] generalized reliable learning in the limit as defined in this paper toreliable behaviorally correct learning and reliable frequency inference. All theselearning types share the useful properties of reliable learning such as closure under recursively enumerable unions and finite invariance (cf. Minicozzi [19]). But
we are not aware of any characterization of reliable behaviorally correct learningand reliable frequency inference in terms of computable numberings or in termsof computational complexity.

References[1] Akama, Y., Zeugmann, T.: Consistent and coherent learning with δ -delay. Information and Computation 206(11) (2008) 1362–1374[2] Barzdin, J.M.: Prognostication of automata and functions. In Freiman, C.V.,
Griffith, J.E., Rosenfeld, J.L., eds.: Information Processing 71, Proceedings of
IFIP Congress 71, Volume 1 - Foundations and Systems, Ljubljana, Yugoslavia,
August 23-28, 1971, North-Holland (1972) 81–84[3] Barzdin, J.M.: Dve teoremy o predel~nom sinteze funkciĭ. In Barzdin,J.M., ed.: Teori Algoritmov i Programm. Volume I. Latvian State University (1974) 82 – 88
[4] Barzdin, J.M.: Inductive inference of automata, functions and programs. In:
Proc. of the 20-th International Congress of Mathematicians, Vancouver, Canada.
(1974) 455–460 (republished in Amer. Math. Soc. Transl. (2) 109, 1977, pp.107112).
[5] Barzdin~, . M., Podnieks, K. M.: K teori induktivnogo vyvoda.
In: Mathematical Foundations of Computer Science: Proceedings of Symposium
and Summer School, Strbské Pleso, High Tatras, Czechoslovakia, September 3-8,
1973., Mathematical Institute of the Slovak Academy of Sciences (1973) 9–15
[6] Blum, L., Blum, M.: Toward a mathematical theory of inductive inference. Information and Control 28(2) (1975) 125–155[7] Blum, M.: A machine-independent theory of the complexity of recursive functions.
Journal of the ACM 14(2) (1967) 322–336[8] Case, J., Smith, C.: Comparison of identification criteria for machine inductive
inference. Theoretical Computer Science 25(2) (1983) 193–220[9] Feldman, J.: Some decidability results on grammatical inference and complexity.
Information and Control 20(3) (1972) 244–262

136

T. Zeugmann[10] Freivalds, R., Kinber, E.B., Wiehagen, R.: How inductive inference strategies
discover their errors. Information and Computation 118(2) (1995) 208–226[11] Gold, E.M.: Limiting recursion. Journal of Symbolic Logic 30 (1965) 28–48[12] Gold, E.M.: Language identification in the limit. Information and Control 10(5)(1967) 447–474[13] Grabowski, J.: Starke Erkennung. In Linder, R., Thiele, H., eds.: Strukturerkennung diskreter kybernetischer Systeme. Volume 82. Seminarberichte der Sektion
Mathematik der Humboldt-Universität zu Berlin (1986) 168–184[14] Helm, J.: On effectively computable operators. Zeitschrift für mathematische
Logik und Grundlagen der Mathematik (ZML) 17 (1971) 231–244[15] Jain, S., Kinber, E., Wiehagen, R., Zeugmann, T.: On learning of functions
refutably. Theoretical Computer Science 298(1) (2003) 111–143[16] Kinber, E., Zeugmann, T.: One-sided error probabilistic inductive inference andreliable frequency identification. Inform. Comput. 92(2) (1991) 253–284[17] McCreight, E.M., Meyer, A.R.: Classes of computable functions defined by bounds
on computation: Preliminary report. In: Proceedings of the 1st Annual ACM
Symposium on Theory of Computing, Marina del Rey, California, United States,
ACM Press (1969) 79–88[18] Meyer, A., Fischer, P.C.: On computational speed-up. In: Conference Recordof 1968 Ninth Annual Symposium on Switching and Automata Theory, Papers
Presented at the Ninth Annual Symposium Schenectady, New York. October 1518, 1968, IEEE Computer Society (1968) 351–355[19] Minicozzi, E.: Some natural properties of strong identification in inductive inference. Theoretical Computer Science 2 (1976) 345–360[20] Odifreddi, P.: Classical Recursion Theory. North Holland, Amsterdam (1989)[21] Rogers, H.: Theory of Recursive Functions and Effective Computability. McGrawHill (1967) Reprinted, MIT Press 1987.
[22] Stephan, F., Zeugmann, T.: Learning classes of approximations to non-recursivefunctions. Theoretical Computer Science 288(2) (2002) 309–341[23] Wiehagen, R., Liepe, W.: Charakteristische Eigenschaften von erkennbaren
Klassen rekursiver Funktionen. Elektronische Informationsverarbeitung und Kybernetik 12(8/9) (1976) 421–438[24] Wiehagen, R.: Zur Theorie der Algorithmischen Erkennung. Dissertation B,
Humboldt-Universität zu Berlin (1978)[25] Wiehagen, R., Zeugmann, T.: Ignoring data may be the only way to learn efficiently. J. of Experimental and Theoret. Artif. Intell. 6(1) (1994) 131–144[26] Zeugmann, T.: Optimale Erkennung. Diplomarbeit, Sektion Mathematik,
Humboldt-Universität zu Berlin (1981)[27] Zeugmann, T.: A-posteriori characterizations in inductive inference of recursivefunctions. Elektronische Informationsverarbeitung und Kybernetik 19(10/11)(1983) 559–594[28] Zeugmann, T.: On the nonboundability of total effective operators. Zeitschrift fürmathematische Logik und Grundlagen der Mathematik (ZML) 30 (1984) 169–172[29] Zeugmann, T., Zilles, S.: Learning recursive functions: A survey. TheoreticalComputer Science 397(1-3) (2008) 4–56