TCS -TR-A-08-32

TCS Technical Report

Learning Recursive Functions

by

Thomas Zeugmann and Sandra Zilles

Division of Computer Science
Report Series A
November 18, 2007

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

thomas@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7684+81-011-706-7684

Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

3. Defining a Learning Model . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3.1. The Learning Types R- TOTALarb and R- TOTAL . . . . . . . . . . . .

7

4. Learning and Consistency – Part I . . . . . . . . . . . . . . . . . . . . . . 17
5. Defining More Learning Models . . . . . . . . . . . . . . . . . . . . . . . 21
5.1. Varying the Mode of Convergence . . . . . . . . . . . . . . . . . . . . . 22
5.2. Varying the Set of Admissible Strategies . . . . . . . . . . . . . . . . . . 28
5.3. Varying the Information Supply . . . . . . . . . . . . . . . . . . . . . . 31
5.4. Coherence and Consistency of Learning Strategies . . . . . . . . . . . . 35
6. Characterizations in Terms of Complexity . . . . . . . . . . . . . . . . . . 36
6.1. Characterizing T- CONSδ and CONSδ . . . . . . . . . . . . . . . . . . . 37
6.2. Characterizing T-REL, R-REL and LIM . . . . . . . . . . . . . . . . . 38
7. Learning and Consistency – Part II . . . . . . . . . . . . . . . . . . . . . 42
8. Characterizations in Terms of Computable Numberings . . . . . . . . . . 51
9. Further Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
9.1. Robust Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
9.2. Assisting the Learner . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
9.3. Complexity of Learning Problems . . . . . . . . . . . . . . . . . . . . . 62
9.4. Uniformity of Learning Problems . . . . . . . . . . . . . . . . . . . . . . 64
10. Summary and Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Learning Recursive Functions
Thomas Zeugmann

Sandra Zilles

Division of Computer Science

Department of Computing Science

Hokkaido University

University of Alberta

N-14, W-9

Edmonton

Sapporo 060-0814, Japan

Alberta, Canada T6G 2E8

thomas@ist.hokudai.ac.jp

zilles@cs.ualberta.ca

November 18, 2007
Abstract
Studying the learnability of classes of recursive functions has attracted considerable interest for at least four decades. Starting with Gold’s (1967) modelof learning in the limit, many variations, modifications and extensions havebeen proposed. These models differ in some of the following: the mode of convergence, the requirements intermediate hypotheses have to fulfill, the set ofallowed learning strategies, the source of information available to the learner
during the learning process, the set of admissible hypothesis spaces, and thelearning goals.
A considerable amount of work done in this field has been devoted to thecharacterization of function classes that can be learned in a given model, theinfluence of natural, intuitive postulates on the resulting learning power, the incorporation of randomness into the learning process, the complexity of learning,among others.
On the occasion of Rolf Wiehagen’s 60th birthday, the last four decadesof research in that area are surveyed, with a special focus on Rolf Wiehagen’s
work, which has made him one of the most influential scientists in the theoryof learning recursive functions.

1. Introduction
Emerging from the pioneering work of Gold [47, 48], Solomonoff [92, 93], Barzdin [15], Thiele [95], Blum and Blum [19], and the work done in Riga [11, 12, 13],
inductive inference of recursive functions has fascinated many researchers.
By definition, inductive inference is the process of generating hypotheses for describing an unknown object from finitely many data points about the unknown object.
For example, when exploring a physical phenomenon by performing experiments,a physicist obtains a finite sequence of pairs (x0 , f(x0 )), (x1 , f(x1 )), . . . , (xn , f(xn )).

2Thomas Zeugmann and Sandra Zilles

From these examples the physicist tries to infer the law f describing the connection
between x and f(x). Usually f is a mathematical expression, a formula, i.e., in a very
general scenario an algorithm computing the function f. Using more and more examples, the hypothesis on hand may be confirmed or falsified. If it is falsified, usually a
new hypothesis is generated.
Many philosophers have studied inductive inference during the last 2000 years,
too, and several of their findings and principles have served as philosophical basisof the mathematical theory of inductive inference which in turn shed more light onthese findings and principles or has suggested alternatives and refinements (cf., e.g.,
William of Ockham [78], Freivalds [36], Board and Pitt [21], Popper [84], Case andSmith [27] as well as Klette and Wiehagen [63]).
The mathematical basis for the work presented in this survey goes back to Solomonoff [92, 93] who proposed criteria for selecting a hypothesis explaining given data best,
Putnam [85] who anticipated several of the earlier results (though on an informal basis)
and Gold [47, 48] who has provided a thorough recursion theoretic basis of inductive
inference.
Gold [48] considers inductive inference to be an infinite process. The objects to
be inferred are recursive functions. In every step n = 0, 1, 2, . . . of the inference
process the inference algorithm has access to successively growing initial segments(x0 , f(x0 )), (x1 , f(x1 )), . . . , (xn , f(xn )) of the graph of the target function. Using these
initial segments, the inference algorithm computes hypotheses hn which are interpreted as numbers of programs in a given computable numbering of (all) partial recursive functions. We refer to such a given numbering as a hypothesis space. Usually it
is required that the hypothesis space contains a program that is correct for the targetfunction. If hn 6= hn+1 , then we say that a mind change occurred. The sequence of all
hypotheses is required to converge to a correct program for the target function. Thatis, beyond some point, no further mind change occurs, and the hypothesis repeatedfrom that point on is a program that computes the target function without errors.
The model just described is Gold’s [48] identification in the limit (cf. Definition 8).
Based on identification in the limit, a huge variety of inference models has been
proposed and studied. Possible modifications comprise the specification of correctness,the mode of convergence, requirements on the intermediate hypotheses output, theset of allowed inference algorithms, the set of admissible hypothesis spaces, and thesource of information available, among others.
Nowadays there is a largely developed mathematical theory and many results havefound their way into monographs [11, 12, 13, 70], books [79, 55], and surveys [5,6, 30, 63]. On the one hand, the results obtained have considerably enlarged ourunderstanding of inference processes and learning and their connections to philosophy,
cognitive science, psychology, and artificial intelligence. On the other hand, younger
counterparts of learning theory and machine learning share with inductive inference
several methods, approaches, ideas, techniques and even algorithms and throughout
this survey we shall occasionally point to them.

Learning Recursive Functions

3

Whenever one tries to survey such a large field, one has to make a certain selection.
In the present survey we focused to a larger part on the earlier work done in the field
and on research performed by Rolf Wiehagen and his co-workers. An obvious reason
for this choice is of course Rolf Wiehagen’s 60th birthday which inspired this project.
Another aspect has been the availability of the relevant literature and presence andnon-existence, respectively, of surveys covering already part of the research undertaken in inductive inference of recursive functions. For example, there are beautiful
surveys concerning the learnability of recursive functions via queries (cf. Gasarch andSmith [45]), by teams of inductive inference machines (cf. Smith [89]), or probabilistic
inductive inference (cf., e.g., Pitt [81], Ambainis [3]). So, these parts of the theory
are only touched in the present paper as is the material presented in Angluin andSmith [5, 6]. Likewise, we had no intention to rewrite the comprehensive paper by
Case and Smith [27] which covers many earlier theoretical results of the inductive
inference of recursive functions. But of course, some overlapping occasionally occurs.
After introducing some basic notions and notations in Section 2, we start witha list of desiderata seemingly arising naturally when one wishes to define a learningmodel. In Section 3, we study the resulting learning model, provide different characterizations of it and point to its strengths and weaknesses. We continue with possible
alternatives to enlarge the learning power of the first model. This directly leads us
to the notion of consistent learning. Consistency, which here means that inference
algorithms always return hypotheses agreeing with the information they have seen sofar, is often presupposed in applications. The question to which extent this affects
learning – and the resulting (in)consistency phenomenon – are studied in this survey
in more detail (cf. Section 4 and 7).
This study performed in Section 4 as well as the results obtained earlier suggest to
introduce further learning models, among them Gold’s [48] original model of learningin the limit (cf. Section 5). Here we also look at different variations of learning in thelimit by changing the mode of convergence, by varying the set of admissible strategies
and the information supply.
For gaining a better understanding of the similarities and differences of the various
learning types presented so far, we then continue with characterizations in terms ofcomplexity and of computable numberings (cf. Sections 6 and 8, respectively).
While having provided a rather comprehensive treatment of the material mentioned
so far, in Section 9 we briefly survey additional research such as learning from good
examples, intrinsic complexity and uniformity. The reason we only sketch these areasis the same mentioned above, i.e., there are already comprehensive articles in printthat cover these areas. Finally, we provide a summary and discuss open problems.

2. Preliminaries
Unspecified notations follow Rogers [86]. In addition to or in contrast with [86] we
use the following. By N = {0, 1, 2, . . . } we denote the set of all natural numbers. We

4Thomas Zeugmann and Sandra Zilles

set N+ = N \ {0}. The set of all finite sequences of natural numbers is denoted by N∗ .
The cardinality of a set S is denoted by |S|. We write ℘(S) for the power set ofset S. Let ∅, ∈, ⊂, ⊆, ⊃, ⊇, and # denote the empty set, element of, 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. The set of all partial recursive and recursive functions of one respectively two variables over N is denoted by P, R, P2 , R2 , respectively. Let f ∈ P, then we use dom(f)to denote the domain of the function f, i.e., dom(f) = {x | x ∈ N, f(x) is defined}.
Additionally, by Val(f) we denote the range of f, i.e., Val(f) = {f(x) | x ∈ dom(f)}.
We use R{0,1} to denote the set of all f ∈ R satisfying Val(f) ⊆ {0, 1}. We refer toR{0,1} as to the set of recursive predicates. A function f ∈ P is said to be monotone
provided for all x, y ∈ N with x 6 y we have, if both f(x) and f(y) are defined thenf(x) 6 f(y). By Rmon we denote the set of all monotone recursive functions.
Any function ψ ∈ P2 is called a numbering. Moreover, let ψ ∈ P2 , then we write ψiinstead of λx.ψ(i, x) and set Pψ = {ψi | i ∈ N} as well as 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 i, x ∈ 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) ↑ ).
For any functions f, g ∈ P and any number m ∈ N we write f =m g iff {(x, f(x)) |x 6 m and f(x) ↓ } = {(x, g(x)) | x 6 m and g(x) ↓ }; otherwise we write f 6=m g.
A numbering ϕ ∈ P2 is called a Gödel numbering (cf. Rogers [86]) iff Pϕ = P, andfor any numbering ψ ∈ P2 , there is a compiler c ∈ R such that ψi = ϕc(i) for alli ∈ N. Göd denotes the set of all Gödel numberings. Let ϕ ∈ Göd and let f ∈ P;
then we use minϕ f to denote the least number i such that ϕi = f.
Furthermore, let NUM = {U | (∃ψ ∈ R2 ) [U ⊆ Pψ ]} denote the family of all subsets
of all recursively enumerable classes of recursive functions.
Following [67] we call any pair (ϕ, Φ) a measure of computational complexity provided ϕ is a Gödel numbering of P and Φ ∈ P2 satisfies Blum’s [20] axioms. That is,(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. We refer to a measure of computational complexity as to
a complexity measure for short.
Sometimes it will be suitable to identify a recursive function with the sequence ofits values, e.g., let α = (a0 , . . . , ak ) ∈ N∗ , j ∈ N, and p ∈ R{0,1} ; then we write αjp todenote the function f for which f(x) = ax , if x 6 k, f(k+1) = j, and f(x) = p(x−k−2),
if x > k + 2. Let g ∈ P and α = (a0 , . . . , ak ) ∈ N∗ ; we write α v g iff α is a prefixof the sequence of values associated with g, i.e., for any x 6 k, g(x) is defined andg(x) = ax . If U ⊆ R, then we denote by [U] the set of all prefixes of functions in U.
Also, it is convenient to have a notation for the set of all finite variants of functions
in U. We use [[U]] for this set, i.e., [[U]] = {f | f ∈ R, ∃f 0 ∈ U ∧ ∀∞ x[f(x) = f 0 (x)]}.
The quantifier ∀∞ , as used here, means “for all but finitely many.”

Learning Recursive Functions

5

Furthermore, using a fixed encoding h. . .i of N∗ onto N we write fn instead ofh(f(0), . . . , f(n))i, for any n ∈ N, f ∈ R. Furthermore, the set of all permutations of
N is denoted by Π(N). Any element X ∈ Π(N) can be represented by a unique sequence(xn )n∈N that contains each natural number precisely once. Let X ∈ Π(N), f ∈ P andn ∈ N. Then we write fX,n instead of h(x0 , f(x0 ), . . . , xn , f(xn ))i provided f(xk ) isdefined for all k 6 n.
Finally, a sequence (jn )n∈N of natural numbers is said to converge to the number jiff all but finitely many numbers of it are equal to j. A sequence (jn )n∈N of natural
numbers is said to finitely converge to the number j iff it converges in the limit to j
and for all n ∈ N, jn = jn+1 implies jk = j for all k > n.
In the following section, we introduce the subject of this survey, i.e., learning ofrecursive functions. For making this survey self-contained, first we briefly outline
what we have to specify in order to arrive at a learning model for recursive functions.
Then we provide an important example.

3. Defining a Learning ModelIn the following, the learner will be an algorithm. We refer to it as a strategy S.
That is, we shall require S ∈ P. The objects to be learned are recursive functions.
Thus, the next question we have to address is from what information recursive functions should be learned. The information fed to the strategy are finite lists of pairs“argument-value,” i.e., lists (x0 , f(x0 )), . . . , (xn , f(xn )). So, for technical convenience
we describe this information by using the notation fX,n defined above. If the order inwhich examples are presented does not matter, then we restrict ourselves to present
examples in natural order, i.e., we consider lists (0, f(0)), (1, f(1)), . . . , (n, f(n)). If
examples are presented in natural order, the argument is redundant. Thus, we canuse the notation fn defined above to describe the information fed to the strategy.
Additionally, we require that the entirety of the local information completely describes the function f to be learned. That means, for every n ∈ N there must be a
finite list containing (n, f(n)).
Using the local information fX,n , the strategy computes a number i which is referred
to as a hypothesis. Thus, when successively fed the sequence (fX,n )n∈N , the strategy
computes a sequence of hypotheses which is interpreted with respect to a suitablychosen hypothesis space. Hypothesis spaces are numberings ψ ∈ P2 which are required
to contain at least one program for every function to be learned.
Finally, we require the sequence of hypotheses formed in the way described above
to converge to a program that correctly computes the target function.
Usually, we consider sets U of recursive functions. Given a class U ⊆ R we thenhave to ask whether or not the resulting learning problem is solvable. For obtaining
an affirmative answer we have to provide a strategy S learning every function in U.
Otherwise, we have to show that there is no strategy S which can learn every function
in U.

6

Thomas Zeugmann and Sandra Zilles

In order to have some examples, it is useful to define some function classes which
we shall use quite often throughout this survey. First, let
U0 = {f | f ∈ R and ∀∞ n[f(n) = 0]}
be the class of all functions that are almost everywhere zero. This class is also known
as the class of functions of finite support. It is easy to see that U0 ∈ NUM.
Next, let (ϕ, Φ) be any fixed complexity measure. We setU(ϕ,Φ) = {Φi | ϕi ∈ R}
and refer to U(ϕ,Φ) as to the class of all recursive complexity functions.
Another quite popular class is the class of self-describing functions defined as follows. Let ϕ ∈ P2 be any fixed Gödel numbering; we set
Usd = {f | f ∈ R and ϕf(0) = f} .
Note that neither U(ϕ,Φ) nor Usd belong to NUM as we shall prove next.
Lemma 1. U(ϕ,Φ) , Usd ∈/ NUM
Proof. For showing that U(ϕ,Φ) ∈/ NUM we first observe that for every class U ∈NUM there is a function b ∈ R such that ∀∞ x[f(x) 6 b(x)] for every function f ∈ U.
This can be seen as follows. Let ψ ∈ R2 be such that U ⊆ Rψ . Then it suffices to setb(x) = max{ψi (x) | i 6 x}. Supposing U(ϕ,Φ) ∈ NUM there would be such a function
b for the class U(ϕ,Φ) . The desired contradiction is obtained by the following claim.
Claim 1. Let f ∈ R be arbitrarily fixed. Then there is a ϕ-program i such thatϕi = f and Φi (x) > b(x) for all x ∈ N.
Let s ∈ R be chosen such thatϕs(j) (x) =f(x),ϕj (x) + 1,

if ¬[Φj (x) 6 b(x)]if Φj (x) 6 b(x) .

By the fixed point theorem (cf., e.g., Smith [88]) there is a number i such thatϕs(i) = ϕi . Suppose there is an x such that Φi (x) 6 b(x). By construction
ϕi (x) = ϕs(i) (x) = ϕi (x) + 1, a contradiction. So, this case cannot happen and
we get ϕi = ϕs(i) = f. This proves the claim.
Consequently, U(ϕ,Φ) ∈/ NUM.
In order to show that Usd ∈/ NUM we first prove that R ∈/ NUM. Suppose the2converse, i.e., there is a numbering ψ ∈ R such that R ⊆ Rψ . We define a function
f by setting f(x) = ψx (x) + 1 for all x ∈ N. Since ψ ∈ R2 we obtain f ∈ R. Hence,
there should be a ψ-program for f, say j, i.e., ψj = f. But ψj (j) = f(j) = ψj (j) + 1, acontradiction. So we have R ∈/ NUM.
Now the proof of Usd ∈/ NUM is obtained by the following claim.

7

Learning Recursive Functions

Claim 2. For every f ∈ R there is an i ∈ N such that ϕi (0) = i and ϕi (x+1) = f(x)for all x ∈ N.
Let f ∈ R be any function and let s ∈ R be chosen such that for all j ∈ N
ϕs(j) (x) =j,f(x − 1),

if x = 0
if x > 0 .

Again, by the fixed point theorem there is a number i such that ϕs(i) = ϕi . By
construction, ϕi (0) = i and ϕi (x + 1) = f(x) for all x ∈ N. This proves Claim 2.
Now, if Usd ∈ NUM, then, by erasing the first argument, one can directly obtaina numbering ψ such that R = Rψ , a contradiction to R ∈/ NUM.
The following classes are due to Blum and Blum [19]. Let (ϕ, Φ) be any complexity
measure, and let τ ∈ R be such that for all i ∈ N
if Φi (x) ↓ and Φx (x) 6 Φi (x), 1,0,if Φi (x) ↓ and ¬[Φx (x) 6 Φi (x)],ϕτ(i) (x) =↑,otherwise.
Now we set
Umahp = {ϕτ(i) | i ∈ N and Φi ∈ Rmon }(the class of monotone approximations to the halting problem) andUahp = {ϕτ(i) | i ∈ N and Φi ∈ R}(the class of approximations to the halting problem).
Note that Umahp , Uahp ∈/ NUM. For a proof, we refer the reader to Stephan and
Zeugmann [94].
Whenever appropriate, we shall use these function classes for illustration of thelearning models defined below, by analyzing whether or not the corresponding learning
problem is solvable.
Next, we exemplify the definition of a learning model and characterize the collectionof all function classes U for which the learning problem is solvable.
3.1. The Learning Types R- TOTALarb and R- TOTALLet us start with a list of desiderata. First, we do not make any assumption
concerning the order in which examples are presented. Second, our strategy should
be defined on all inputs, i.e., we require S ∈ R. This may seem convenient, since it
may be hard to know which inputs to the strategy may occur. Third, every hypothesis
should describe a recursive function. Again, this looks natural, since any hypothesis
not describing a recursive function cannot be correct. Thus allowing a strategy tooutput hypotheses not describing recursive functions may be a source of potential
errors which we avoid by our requirement. Moreover, this requirement is also nicely

8Thomas Zeugmann and Sandra Zilles

in line with Popper’s [84] refutability principle requiring that we should be able torefute every incorrect hypothesis.
Definition 1 (Wiehagen [99]). Let U ⊆ R and let ψ ∈ P2 . The class U is said
to be R–totally arb-learnable with respect to ψ if there is a strategy S ∈ R such that(1) ψS(n) ∈ R for all n ∈ N,(2) for all f ∈ U and every X ∈ Π(N), there is a j ∈ N such that ψj = f, and(S(fX,n ))n∈N converges to j.
If U is R–totally arb-learnable with respect to ψ by a strategy S, we write U ∈R- TOTALarb
TOTALarb= {U | U is R–totally arb-learnableψ (S). Moreover, let RψS
arb
w.r.t. ψ}, and let R- TOTAL = ψ∈P2 R- TOTALarbψ .
Some remarks are mandatory here. Let us start with the semantics of the hypotheses produced by a strategy S. As described above, we always interpret the number
S(fX,n ) as a ψ–number. This convention is adopted to all the definitions below. The“arb” in arb-learnable points to the fact that we require learnability with respect toany arbitrary order of the input. Moreover, according to the definition of convergence,
only finitely many data points of the graph of a function f were available to the strategy S up to the unknown point of convergence. Therefore, some form of learning musthave taken place. Thus, the use of the term “learn” in the above definition is indeed
justified.
Note that R- TOTALarb is sometimes also called PEX, where the EX stands for
explain and P refers to Popperian strategies, i.e., strategies that can directly use
Popper’s [84] refutability principle (cf. [27]). But we think this interpretation of Popper’s [84] refutability principle is too narrow. A more detailed discussion is provided
throughout this survey.
In order to study the impact of the requirement to learn with respect to any orderof the input, next we relax Definition 1 by demanding only learnability from input
presented in natural order.
Definition 2 (Wiehagen [99]). Let U ⊆ R and let ψ ∈ P2 . The class U is said
to be R–totally learnable with respect to ψ if there is a strategy S ∈ R such 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(fn ))n∈N converges to j.
R- TOTALψ (S), R- TOTALψ , and R- TOTAL are defined analogously to the above.
It is technically advantageous to start with the following result showing that, as
far as R–total learning is concerned, the order in which the graph of the function isfed to the learning strategy does not matter.
Theorem 1. R- TOTAL = R- TOTALarb

Learning Recursive Functions

9

Proof. Obviously, if we can learn from arbitrary input then we can learn from input
presented in natural order, i.e., R- TOTALarb ⊆ R- TOTAL.
For the opposite direction, let U ∈ R- TOTAL. Hence there is a numbering ψ ∈ P2
and a strategy S ∈ R such that U ∈ R- TOTALψ (S). The desired strategy S 0 is
obtained from S by adding a preprocessing. If S 0 receives an encoded list fX,n it looks
for the largest number m such that (0, f(0)), . . . , (m, f(m)) are all present in fX,n . If
this number m exists, then S0 simulates S on input fm and outputs the hypothesis
computed. Otherwise, i.e., if (0, f(0)) does not occur in fX,n , then S0 simply returns
a fixed program of the constant zero function as an initial auxiliary hypothesis.
0
Now it is easy to see that U ∈ R- TOTALarb
ψ (S ). We omit the details.

The following lemma is both of technical and of epistemological importance. It
actually states that, if we can R-totally learn with respect to some numbering, thenwe can also learn with respect to any Gödel numbering. As we shall see later, its
proof directly transforms to almost every learning type considered in this survey.
Lemma 2. Let U ⊆ R, let ψ ∈ P2 be any numbering and let S ∈ R be such thatU ∈ R- TOTALψ (S). Furthermore, let ϕ ∈ P2 be any Gödel numbering. Then there
is a strategy Ŝ ∈ R such that U ∈ R- TOTALϕ (Ŝ).
Proof. By the definition of a Gödel numbering there is a compiler function c ∈ Rsuch that ψi = ϕc(i) for all i ∈ N. Thus, we can define Ŝ(fn ) = c(S(fn )) and thelemma follows.
Expressed differently, we have just shown that R- TOTAL = R- TOTALϕ for everyGödel numbering ϕ. But it is often advantageous to use special numberings having
special properties facilitating learning. A first example is provided by Theorem 2
below. Additionally, this theorem also characterizes the classes in R- TOTAL.
Theorem 2. R- TOTAL = NUM
Proof. The proof is done by showing two claims.
Claim 1. R- TOTAL ⊆ NUM
Let U ∈ R- TOTAL. Then there is a strategy S ∈ R and a numbering ψ ∈ P2
such that U ∈ R- TOTALψ (S). We have to construct a numbering τ ∈ R2 such thatU ⊆ Rτ .
For all i, x ∈ N we define τ(i, x) = ψS(i) (x). By Condition (1) of Definition 2 weknow that ψS(i) ∈ R. Thus, we directly obtain τ ∈ R2 . It remains to show thatU ⊆ Rτ . Let f ∈ U. By Condition (2) of Definition 2 there exists a j such that ψj = f
and (S(fn ))n∈N converges to j. Let k be minimal such that S(fn ) = j for all n > k.
Thus, for i = fk we obtain
τi = ψS(i) = ψS(fk ) = ψj = f ,and consequently, U ⊆ Rτ . This proves Claim 1.

10Thomas Zeugmann and Sandra Zilles

Claim 2. NUM ⊆ R- TOTALLet U ∈ NUM. Hence there is a numbering ψ ∈ R2 such that U ⊆ Rψ . Essentially,
Claim 2 is proved by using Gold’s [48] famous identification by enumeration strategy.
The idea behind the identification by enumeration strategy to learn a function f ∈ U
is to search for the least index j in the enumeration ψ0 , ψ1 , ψ2 , . . . such that ψj = f.
n
So on input fn one looks for the least i such that ψn
i = f .
The only difficulty we have to overcome is to ensure that S satisfies Condition (1)of Definition 2 for all f ∈ R, that is, also in case f ∈ R \ U. Then there may be nonprogram i at all such that ψn
i = f .
Therefore, using a fixed enumeration of N∗ (cf. Rogers [86]) we define a numbering χ
as follows. Let α be the ith tuple of N∗ enumerated. We set χi = α0∞ . Thus, χ ∈ R2
and U0 = Rχ .
Next, we define a numbering τ ∈ R2 by setting τ2i = ψi and τ2i+1 = χi for alli ∈ N. Now, taking into account that [U0 ] = [R] = N∗ , we can directly use theidentification by enumeration strategy by using the numbering τ to R-totally learn
the class U. This proves Claim 2.
Claim 1 and Claim 2 together yield the theorem.
On the one hand, NUM is a rich collection of function classes. As a matter of fact,
the class of all primitive recursive functions is in NUM. Moreover, the characterization
obtained by Theorem 2 directly allows a very strong corollary, which first requires thefollowing simple definition.
Definition 3. Let LT be any learning type and let (Si )i∈N be a recursive enumeration of strategies fulfilling the requirements of the learning type LT . We call LT closed
under recursively enumerable union if there is a strategy S fulfilling the requirements
Sof LT such that i∈N LT (Si ) ⊆ LT (S).
Corollary 3. R- TOTAL is closed under recursively enumerable union.
On the other hand, none of the classes U(ϕ,Φ) , Usd , Umahp , and Uahp is in NUM
as pointed out above.
So, we have to explore some ways to enlarge the learning capabilities of R- TOTAL.
Before doing this, we also characterize R- TOTAL in terms of complexity, since it may
help to gain a better understanding of the properties making a function class learnable
or non-learnable, respectively.
The idea behind the following characterization can be explained easily. Suppose
we want to learn a class U with respect to any fixed Gödel numbering ϕ. Then anstrategy may try to find a program i such that ϕni = f . Though this search will
succeed, the strategy may face serious difficulties to converge. To see this, suppose
on input fn a program i as described has been found. Next, the strategy sees alsof(n + 1). Now it may try to compute ϕi (n + 1) and, in parallel to find again an index,
say j, such that ϕn+1
= fn+1 . Once j is found and the computation of ϕi (n + 1)
j

Learning Recursive Functions

11

has not stopped yet, the strategy must make a decision. Either it tries to computeϕi (n + 1) further or it switches its hypothesis to j. The latter would be a bad idea if
ϕj 6= f but ϕi = f. On the other hand, it would be a good idea if ϕi (n + 1) ↑ . Since
the halting problem is undecidable, without any additional information, the strategy
cannot decide which case actually occurs. Thus, it is intuitively clear that information
concerning the computational complexity of the functions to be learned can only help.
We illustrate this by reproving Barzdin’s and Freivalds’ [14] Extrapolation Theorem
here in our setting.
Let t ∈ R, and let (ϕ, Φ) be any fixed complexity measure. Following McCreightand Meyer [74], we define the complexity class
Rt = {ϕi | ∀∞ n[Φi (n) 6 t(n)]} ∩ R .
For further information concerning these complexity classes, we refer the interested
reader to e.g., [22, 28, 67, 105].
Theorem 4 (Barzdin and Freivalds [14]). For every class U ⊆ R we have:U ∈ R- TOTAL if and only if there is a function t ∈ R such that U ⊆ Rt .
Proof. Necessity. Let U ∈ R- TOTAL. Then, by Theorem 2, we know that there isa numbering ψ ∈ R2 such that U ⊆ Rψ . Now let c ∈ R be any fixed compiler suchthat ψi = ϕc(i) for all i ∈ N. We set t(n) = max{Φc(i) (n) | i 6 n}. Clearly, U ⊆ Rt .
Sufficiency. Suppose U ⊆ Rt . By Theorem 2, it suffices to show that Rt ∈ NUM.
For proving this, we use the observation that f ∈ Rt if and only if there are j, n, k ∈ Nsuch that f = ϕj , Φj (x) 6 k for all x 6 n and Φj (x) 6 t(x) for all x > n. Now let c3
be the canonical enumeration of N × N × N. For c3 (i) = (j, n, k) and x ∈ N we define
if x 6 n and Φj (x) 6 k
 ϕj (x),ϕj (x),
if x > n and Φj (x) 6 t(x)
ψ(i, x) =0,otherwise.
By construction, we clearly have ψ ∈ R2 . Now let f ∈ Rt . Using the observation madeabove, choose i such that c3 (i) = (j, n, k), where f = ϕj , Φj (x) 6 k for all x 6 n
and Φj (x) 6 t(x) for all x > n. Hence, ψi = ϕj = f and thus f ∈ Rψ . Consequently,
Rt ∈ NUM.
There is another nice characterization of R- TOTAL in terms of a different learningmodel which we would like to include. First we define the learning model which has
been introduced by Barzdin [15].
Definition 4 (Barzdin [15]). A class U ⊆ R of functions is said to be predictable
if there exists a strategy S ∈ R such that S(fn ) = f(n + 1) for all f ∈ U and all but
finitely many n ∈ N.
The resulting learning type is denoted by NV. Here, NV stands for “next-value.”So, in NV learning we have to correctly predict the next value of the target function
for almost all n.

12Thomas Zeugmann and Sandra Zilles

Theorem 5 (Barzdin [15]). NV = R- TOTAL
We do not prove this theorem here but refer the interested reader to Case andSmith [27] (cf. Theorem 2.19).
But we would like to discuss another interesting aspect. If the value predictedby an NV learner is wrong, i.e., if S(fn ) 6= f(n + 1), then we say that a prediction
error occurs. Analogously, if an R- TOTAL learner changes its hypothesis, i.e., if
S(fn ) 6= S(fn+1 ), then S performs a mind change.
Now, when using the identification by enumeration strategy, in order to learn thenth function enumerated in the numbering ψ, one needs n mind changes in the worst
case and this approach also leads to n prediction errors in the worst case. Therefore,
it is only natural to ask whether or not we can do any better. In fact, an exponential
speed-up is possible. For the sake of simplicity, we present the solution here only forclasses of recursive predicates, i.e., U ⊆ R{0,1} and for prediction errors.
Theorem 6 (Barzdin and Freivalds [17]). Let ψ ∈ R2 such that ψi ∈ R{0,1}for all i ∈ N. Then there exists an NV learner FP for U making at most O(log n)prediction errors for every function f ∈ U, where n is the least number j such thatψj = f.
Proof. Let f ∈ U be the target function. The desired NV learner works in stages.
i
In each Stage i it considers the subset of the block of functions Bi = {ψk | 22 + 1 6
i+1
k 6 22 } that coincide with all the data seen so far. Then it makes its predictionin accordance with the majority of the functions still in the block. After having readthe true value, it eliminates the functions not coinciding with the new value fromblock Bi . If all functions are eventually eliminated, Stage i is left and Stage i + 1
is started. Clearly, if the target function f belongs to block Bi , Stage i is never left.
Before analyzing this prediction algorithm we give a formal description of it. In orderto make it better readable, we also add the arguments to the data presentation.
Algorithm FP: “On successive input h0, f(0), 1, f(1), 2, f(2), . . . i do the following:
Execute Stage 0:
Stage 0: Set V0 = {0, 1, 2, 3, 4}, x0 = 0.
While V0 6= ∅ execute (A) else goto Stage 1.
(A) Read x0 . Compute V00 = {k | k ∈ V0 , ψk (x0 ) = 0}, and
V01 = {k | k ∈ V0 , ψk (x0 ) = 1}.
If |V00 | > |V01 | then predict 0; otherwise predict 1.
Read f(x0 ), and increment x0 . If f(x0 ) = 0 set V0 = V00 ; otherwise set
V0 = V01 .
Stage i, i > 1: Set xi = xi−1 , and computeii+1
Vi = {k ∈ N | 22 + 1 6 k 6 22 , ψk (x) = f(x) for all 0 6 x 6 xi }.
(* Vi is the set of those indices of functions in block i that coincide with all thedata seen so far. *)Learning Recursive Functions

13

While Vi 6= ∅ execute (B) else goto Stage i + 1.
(B) Read xi . Compute Vi0 = {k | k ∈ Vi , ψk (xi ) = 0}, and
Vi1 = {k | k ∈ Vi , ψk (xi ) = 1}.
If |Vi0 | > |Vi1 | then predict 0; otherwise predict 1.
Read f(xi ), and increment xi . If f(xi ) = 0 set Vi = Vi0 ; otherwise set
Vi = Vi1 .
We start our analysis by asking how many stages the algorithm FP has to execute. Letn be the least number j such that ψj = f. Furthermore, let i be the least number msuch that n ∈ Vm . Thus, i = dlog log ne − 1. The total number of prediction mistakesis the sum of all the prediction mistakes made on each of the blocks V0 , V1 , . . . Vi .
The number of prediction mistakes made on V0 is 3. For every 1 6 z < i the numberof prediction mistakes made on Vz will be at most dlog(|Vz |)e. To see this, rememberthat each prediction is made in accordance with the majority of computed values for
all the remaining indices in Vz . Thus, whenever a prediction error occurs, at least
half of the indices in Vz is deleted. Since all indices are eventually deleted, we arriveat the stated bound. Analogously, the number of prediction mistakes made on Vi iszz
at most dlog |Vi |e − 1. Obviously, |Vz | = 22 (22 − 1), and thus dlog |Vz |e 6 2z+1 .
Therefore, the maximum number of prediction mistakes is upper bounded by
21 + · · · + 2i+1 = 2i+2 − 1
6 2dlog log ne−1+2 − 1
6 4 · 2log log n= 4 log n= O(log n) .
The algorithm FP invented by Barzdin and Freivalds is nowadays usually referred
to as the halving algorithm which has found many applications in machine learning.
This algorithm can be modified to totally learn every class of recursive predicateswith at most O(log n) mind changes. However, in order to achieve this result, theresulting strategy must use a Gödel numbering as its hypothesis space and not the
numbering ψ. Furthermore, all these results can be generalized to learn or to predict
arbitrary classes from NUM, thereby still achieving the O(log n) bound. For a detailed
presentation and further information, we refer the reader to Freivalds, Bārzdiņš andPodnieks [37].
The results obtained so far provide some insight concerning the problem how toextend the learning capabilities of R- TOTAL. First, we could restrict our demands tothe strategy to hold only on initial segments from [U] instead of from [R]. Second we
could modify our demands to the intermediate hypotheses. The demand to output
only programs computing recursive functions seems rather strong.

14

Thomas Zeugmann and Sandra Zilles

Third, we could have a closer look at the identification by enumeration strategy.
The most obvious point here is that we do not need the requirement ψi ∈ R. For
example, if the predicate “ψi (x) = y” was uniformly recursive for all i, x, y ∈ N it
would still work. But as we shall see, there is more we can do.
Fourth, looking at the definition of the complexity class Rt , we see that the bound t
does not depend on the functions f to be learned. So, some modifications are suggesting themselves.
We finish this chapter, by trying the first approach. The other modifications are
discussed later. So, let us relax the definition of R- TOTAL as described above.
Definition 5 (Freivalds and Barzdin [34]). Let U ⊆ R and let ψ ∈ P2 . The
class U is said to be totally learnable with respect to ψ if there is a strategy S ∈ Psuch that for each function f ∈ U,(1) for all n ∈ N, S(fn ) is defined and ψS(fn ) ∈ R,
(2) there is a j ∈ N such that ψj = f, and (S(fn ))n∈N converges to j.
TOTALψ (S), TOTALψ and TOTAL are defined analogously as above.
Note that any strategy that learns in the sense of TOTAL can directly use Popper’s [84] refutability principle. But obviously, Usd ∈ TOTAL and thus total learning
is more powerful than R-total inference.
Theorem 7. R- TOTAL ⊂ TOTAL
But the price paid is rather high, since, in contrast to Corollary 3, now we caneasily prove that TOTAL is not closed under union.
Theorem 8. U0 ∪ Usd ∈/ TOTAL
Proof. Suppose the converse. Then there must exist a strategy S such that U0 ∪Usd ∈ TOTAL(S). Since [U0 ] = [R], we can conclude S ∈ R and ϕS(i) ∈ R for alli ∈ N. Hence, S would witness U0 ∪ Usd ∈ R- TOTAL(S). So, by Theorem 2, we
obtain U0 ∪ Usd ∈ NUM, a contradiction to Lemma 1.
TOTAL has another interesting property. Modifying Definition 5 in the opposite way we have obtained R- TOTAL from R- TOTALarb , we get the learning type
TOTALarb . Then, using the same ideas as in the proof of Theorem 1, one can easily
show the following theorem first announced in Jantke and Beick [59].
Theorem 9. TOTAL = TOTALarb
Next, we characterize TOTAL in terms of computable numberings.
Theorem 10 (Wiehagen [99]). Let U ⊆ R. Then we have: U ∈ TOTAL if andonly if there exists a numbering ψ ∈ P2 such that
(1) U ⊆ Pψ ,

Learning Recursive Functions

15(2) There is a function g ∈ R such that ψi =g(i) f implies ψi ∈ R for every functionf ∈ U and every program i.
Proof. Necessity. Let U ∈ TOTAL and let ϕ ∈ Göd. By Lemma 2 we can assume
that there is a strategy S ∈ P such that U ∈ TOTALϕ (S). Let d ∈ R be chosen suchthat d enumerates dom(S) without repetitions. Furthermore, for i ∈ N let n be thelength of the tuple enumerated by d(i). We set ψ(i, x) = ϕS(d(i)) (x) and g(i) = n.
Definition 5 directly implies that Conditions (1) and (2) are satisfied.
Sufficiency. First we describe the basic idea for a strategy. Suppose f ∈ U and wehave already found a program i such that ψi =g(i) f. Then Condition (2) allows tocheck whether or not f(x) = ψi (x) for all x provided the strategy knows f(x). So, if
f = ψi , the strategy will converge. Otherwise it will find a witness proving f 6= ψi andit can restart its search. So, the main problem is to verify ψi =g(i) f. For overcoming
it, let c ∈ R be such that ψi = ϕc(i) for all i ∈ N. Now the idea is to use the input
length to provide a bound on Φc(i) (x).
The desired strategy S is formally defined as follows. Let z be any fixed number
such that ψz ∈ R.
S(fn ) = “Compute M = {i | i 6 n, g(i) 6 n, Φc(i) (x) 6 n and ψi (x) = f(x) for all
x 6 g(i)}. Execute Instruction (I).
(I) If M = ∅ then output z.
If M 6= ∅ then let i = min M and compute ψi (x) for all x such thatg(i) < x 6 n. If one of these values is not defined, then S(fn ) is notdefined, either.
Otherwise check whether or not ψi =n f. If this is the case, output i.
In case ψi 6=n f execute (I) for M := M \ {i}.”It remains to show that U ∈ TOTALψ (S). Let f ∈ U. If M = ∅ then we haveψS(fn ) = ψz ∈ R. If M 6= ∅, then the definition of M ensures that we already know
ψi =g(i) f. Hence by Condition (2) we also have ψi ∈ R. Thus, S(fn ) is defined andψS(fn ) ∈ R for all n ∈ N. Finally, the definition of S directly implies that (S(fn ))n∈N
converges to the least number i with ψi = f.
We finish this section by showing that U(ϕ,Φ) ∈/ TOTAL provided the complexity
measure (ϕ, Φ) fulfills a certain intuitive property.
A complexity measure (ϕ, Φ) is said to satisfy Property ext provided for alli, n ∈ N such that Φi (0) ↓ , . . . , Φi (n) ↓ there is a Φz ∈ R such that Φi =n Φz .
Note that the following proof uses an idea from Case and Smith [27].
Theorem 11.
Property ext.

U(ϕ,Φ) ∈/ TOTAL for all complexity measures (ϕ, Φ) fulfilling

Proof. Let r ∈ R be chosen such that Φi = ϕr(i) for all i ∈ N. Furthermore, by
the padding lemma r can be chosen in a way such that r is strongly monotonously

16

Thomas Zeugmann and Sandra Zilles

increasing, i.e., r(i) < r(i + 1) for all i ∈ N (cf. Smith [88]). Hence, Val(r) is recursive.
Next, choose s ∈ R such thatϕs(j) (0) =0,↑,

if there is an i such that r(i) = j
otherwise .

In order to define ϕs(j) for all j and all x > 0, suppose there is a strategy S ∈ P suchthat U(ϕ,Φ) ∈ TOTALϕ (S). For all x > 0 let

if ϕj (y) ↓ , for all y 6 x and S(ϕxj ) ↓ and 0,
ϕkx (x + 1) ↓ < ϕj (x + 1), where kx = S(ϕxj )ϕs(j) (x + 1) =↑,otherwise .
By the fixed point theorem (cf. Smith [88]) there is a number i such that ϕs(r(i)) = ϕi .
We continue to show inductively that ϕi ∈ R and that S fails to totally learn Φi .
For the induction base, by construction, ϕs(r(i)) (0) = 0, since j = r(i). Hence,
ϕi (0) = 0 and thus Φi (0) = ϕr(i) (0) ↓ .
Next, consider the definition of ϕi (1).
if Φi (0) ↓ and S(Φ0i ) ↓ 0,
and ϕk0 (1) ↓ < Φi (1), where k0 = S(Φ0i )
ϕi (1) = ϕs(r(i)) (1) =↑,otherwise .
Since Φi (0) ↓ we know by Property ext that there is a Φz ∈ R such that Φi (0) =Φz (0). Consequently, S(Φ0i ) ↓ and ϕk0 ∈ R, where k0 = S(Φ0i ). Thus, by Property (2)of the definition of complexity measure, one can effectively decide whether or not
ϕk0 (1) < Φi (1). Clearly, if ϕk0 (1) < Φi (1), then ϕi (1) = 0 and hence defined. On
the other hand, if ϕk0 (1) > Φi (1) then Φi (1) ↓ , too, but, by construction, ϕi (1) ↑ , acontradiction to Property (1) of the definition of complexity measure. Hence ϕi (1) isdefined.
The induction step is done analogously. That is, 0, if Φi (y) ↓ , for all y 6 x and S(Φxi ) ↓ andϕkx (x + 1) ↓ < Φi (x + 1), where kx = S(Φxi )ϕi (x + 1) = ϕs(r(i)) (x + 1) =
↑ , otherwise .
By the induction hypothesis, Φi (y) ↓ for all y 6 x and thus, by Property ext, there
is a Φz ∈ R such that Φi =x Φz and therefore S(Φxi ) ↓ . Let kx = S(Φxi ), thenϕkx ∈ R and one can effectively decide whether or not ϕkx (x + 1) < Φi (x + 1). If itis, ϕi (x + 1) = 0 and thus Φi (x + 1) ↓ . If it is not, we have ϕkx (x + 1) > Φi (x + 1) but
ϕi (x + 1) ↑ , a contradiction to Property (1) of the definition of complexity measure.
Hence, ϕi (x + 1) is defined.
Therefore, we obtain ϕi ∈ R and hence Φi ∈ R, too. Consequently, Φi ∈ U(ϕ,Φ) .
By supposition, S has to learn Φi , i.e., the sequence (kx )x∈N has to converge, say to k,
and k must be a ϕ-program for Φi . But by construction we have ϕk (x+1) < Φi (x+1)
for all but finitely many x ∈ N, a contradiction.

Learning Recursive Functions

17

Now we are ready to explore the other ways mentioned above to enlarge the learning
capabilities of R- TOTAL. This brings us directly to another subject Rolf Wiehagen
has been interested in for many years, i.e., learning and consistency.

4. Learning and Consistency – Part I
Looking back at the proof of Theorem 2, we see that an R-total strategy is always
completely and correctly reflecting the data seen so far. Such a hypothesis is called
consistent. Hypotheses not behaving thus are said to be inconsistent. Consequently,
if a strategy has already seen the examples (x0 , f(x0 )), . . . , (xn , f(xn )) and is hypothesizing the function g and if g is inconsistent, then there must be a k 6 n such thatg(xk ) 6= f(xk ). Note that there are two possible reasons for g to differ from f onargument xk . Either g(xk ) ↑ or g(xk ) ↓ but does not equal f(xk ). In any way, an
inconsistent hypothesis is not only wrong but it is wrong on an argument for which
the learning strategy does already know the correct value. Thus, one may be tempted
to completely exclude strategies producing inconsistent hypotheses. So, let us follow
this temptation and let us see what we get. We start with the strongest version of
consistent learning which has already been considered in [19]. Note that Blum andBlum [19] called this form of consistency the overkill property.
Definition 6 (Blum and Blum [19]). Let U ⊆ R and let ψ ∈ P2 .
U ∈ T- CONSarb
ψ if there is a strategy S ∈ R such that(1) for all f ∈ U and every X ∈ Π(N), there is a j ∈ N such that ψj = f, and(S(fX,n ))n∈N converges to j,(2) ψS(fX,n ) (xm ) = f(xm ) for every permutation X ∈ Π(N), f ∈ R, n ∈ N, andm 6 n.
arb
T- CONSarb
are defined in analogy to the above.
ψ (S) as well as T- CONS

That means a T- CONSarb strategy is required to return consistent hypotheses even
if the input does not belong to any function in the target class U.
Next, we introduce a new family of complexity classes. Let h ∈ R2 ; then
Rh = {ϕi | ∀∞ n[Φi (n) 6 h(n, ϕi (n))]} ∩ R
is called honesty complexity class. So, honesty means that every function f ∈ Rh does
possess a ϕ-program i computing it, i.e., ϕi = f and the complexity of this ϕ-program
can be bounded by using the function h ∈ R2 and the function values f(n).
Furthermore, we introduce a new family of numberings.
Definition 7. A numbering ψ ∈ P2 is said to be measurable if the predicate“ψi (x) = y” is uniformly recursive in i, x, y.
The next theorem completely characterizes T- CONSarb in terms of complexity andof computable numberings. The proof presented below is a combination of results

18

Thomas Zeugmann and Sandra Zilles

from Blum and Blum [19] (Assertion (1) and (2)) and from McCreight and Meyer [74]who showed the equivalence of Assertion (2) and (3).
Theorem 12 (Blum and Blum [19], McCreight and Meyer [74]).
Let (ϕ, Φ) be any complexity measure and let U ⊆ R. Then the following conditions
are equivalent.
(1) U ∈ T- CONSarb .
(2) There is a function h ∈ R2 such that U ⊆ Rh .
(3) There is a measurable numbering ψ ∈ P2 such that U ⊆ Pψ .
Proof. The proof is done by showing three claims.
Claim 1. (1) implies (2).
Let U ∈ T- CONSarb
ϕ (S) be witnessed by S ∈ R and ϕ ∈ Göd. Furthermore, let
c2 : N × N 7→ N be the standard Cantor coding of all pairs of natural numbers. We
define an order ≺ on N × N. Let (x1 , y1 ), (x2 , y2 ) ∈ N × N. Then(x1 , y1 ) ≺ (x2 , y2 ) if and only if c2 (x1 , y1 ) < c2 (x2 , y2 ) .
Clearly, ≺ is computable.
Furthermore, for (x, y) we denote by SEQ(x , y) the set of all finite sequences
σ = ((x0 , y0 ), . . . , (xn , yn ), (x, y)) for which (x0 , y0 ) ≺ · · · ≺ (xn , yn ) ≺ (x, y). Notethat for every pair (x, y) the set SEQ(x , y) is finite and computable. Since S isconsistent in the sense of T- CONSarb we additionally haveϕS(hσi) (x) = y

for all σ ∈ SEQ(x , y) .

(1)

Now we are ready to define the desired function h. For all x, y ∈ N leth(x, y) = max{ΦS(hσi) (x) | σ ∈ SEQ(x , y)} .
Since for every pair (x, y) the set SEQ(x , y) is finite and computable, by (1) we
directly get h ∈ R2 .
Now let f ∈ U. We have to show f ∈ Rh . Note that ≺ induces precisely one enumeration (x0 , f(x0 )), (x1 , f(x1 )), . . . of the graph of f. By the definition of T- CONSarb
the strategy S has to converge to a number j with ϕj = f when successively fed thisenumeration. Thus, for all sufficiently large n we haveS(h(x0 , f(x0 )), . . . , (xn , f(xn ))i) = j .
By the definition of h we can directly conclude Φj (xn ) 6 h(xn , ϕj (xn )) for all sufficiently large n. Consequently, f ∈ Rh , and Claim 1 is shown.
Claim 2. (2) implies (3).

19

Learning Recursive Functions

Let h ∈ R2 and let f ∈ Rh . Then there exists a triple (j, n, k) such that ϕj = f,
Φj (x) 6 k for all x 6 n and Φj (x) 6 h(x, ϕj (x)) for all x > n. Using ideas similar
to those applied in the proof of the sufficiency part of Theorem 4 we can define thedesired numbering ψ. Again, let c3 be the canonical enumeration of N × N × N. For
c3 (i) = (j, n, k) and x ∈ N we define
if [x 6 n → Φj (x) 6 k and ϕj (x) = y] y,or [x > n → Φj (x) 6 h(x, y) and ϕj (x) = y]ψ(i, x) =↑,otherwise.
Obviously, we have ψ ∈ P2 and by the observation made above it is easy to seethat U ⊆ Pψ . It remains to show that ψ is measurable. So, we have to provide analgorithm uniformly deciding on input i, x, y whether or not ψ(i, x) = y. The desiredalgorithm is displayed in Figure 1. Note that rounded rectangles denote tests. This
proves Claim 2.
x6n

yes

no
computeh(x, y)Φj (x) 6 h(x, y)yesΦj (x) 6 kyesϕj (x) = ynono

output 0

output 0

ϕj (x) = ynono

output 0

output 0

yes

yes

output 1

output 1

Figure 1: An algorithm uniformly deciding on input i, x, y whether or not ψ(i, x) = y;here (j, n, k) = c3 (i).
Claim 3. (3) implies (1).
Let U ⊆ R and let ψ ∈ P2 be a measurable numbering such that U ⊆ Rψ .
Moreover, as in the proof of Theorem 2 we chose χ ∈ R2 such that U0 = Rχ . Again,
we set τ2i = ψi and τ2i+1 = χi for all i ∈ N. Obviously, τ ∈ P2 , τ is measurable, andU ⊆ Rτ . Now let X ∈ Π(N) and n ∈ N. We defineS(fX,n ) = “Search the least i such that τi (xm ) = f(xm ) for all 0 6 m 6 n. If suchan i has been found, output i.”
Since τ is measurable, it is easy to see that S ∈ R. Moreover, if f ∈ U, then thesequence (S(fX,n ))n∈N has to converge, since the search can never go beyond the leastτ-program j with τj = f. When converging, say to j, the strategy yields τj = f. Thus,
U ∈ T- CONSarb
τ (S).
This proves Claim 3, and hence the theorem is shown.

20

Thomas Zeugmann and Sandra Zilles

This theorem directly allows the following corollary.
Corollary 13 (Blum and Blum [19]).
(1) R- TOTAL ⊂ T- CONSarb and(2) R- TOTAL ∩ ℘(R{0,1} ) = T- CONSarb ∩ ℘(R{0,1} ).
(3) T- CONSarb is closed under recursively enumerable union.
Proof. For the first part, by Lemma 1 and Theorem 2 we have U(ϕ,Φ) ∈/ R- TOTAL.
2
On the other hand, for every complexity measure (ϕ, Φ), Φ ∈ P is measurable. Hence
U(ϕ,Φ) ∈ T- CONSarb . Consequently, T- CONSarb \ R- TOTAL 6= ∅. Furthermore,
R- TOTAL ⊆ T- CONSarb by Theorem 2 and Theorem 12.
For the second part, if U ∈ T- CONSarb then there is a function h ∈ R2 such thatU ⊆ Rh . But since U ⊆ R{0,1} , we can define t(x) = h(x, 0) + h(x, 1) for all x ∈ N.
Hence, we get U ⊆ Rt , and thus by Theorem 2 we know U ∈ NUM = R- TOTAL.
Assertion (3) is proved by using Theorem 12. Let (Si )i∈N be a recursive enumeration of strategies fulfilling the requirements of T- CONSarb . Without loss ofgenerality we can assume that all strategies Si learn with respect to some fixedGödel numbering ϕ. As the proof of Claim 1 in the demonstration of Theorem 12shows, for every strategy Si we can effectively obtain a function hi ∈ R2 such that
T- CONSarb
ϕ (Si ) ⊆ ℘(Rhi ). We defineh(x, y) = max{hi (x, y) | i 6 x} for all x, y ∈ N .
S
Clearly, h ∈ R2 and by construction i∈N Rhi ⊆ Rh . Applying again Theorem 12
we get that there is a strategy S such that Rh ∈ T- CONSarb
ϕ (S). Consequently,
S
arb
arb
i∈N T- CONSϕ (Si ) ⊆ T- CONSϕ (S).
Furthermore, TOTAL and T- CONSarb both extend the learning capabilities of
R- TOTAL but in different directions. Before showing this, we consider the variant of T- CONSarb where the strategy is only required to learn from input presented
in natural order. The resulting learning type is denoted by T- CONS.
Corollary 14. TOTAL # T- CONSarb
Proof. By Theorem 11 we have U(ϕ,Φ) ∈ T- CONSarb \ TOTAL. On the other
hand, Usd ∈ TOTAL. We claim that Usd ∈/ T- CONS, and thus we also have Usd ∈/arb
T- CONS .
Let ϕ be any fixed Gödel numbering. Suppose there is a strategy S ∈ R suchthat Usd ∈ T- CONSϕ (S). By an easy application of the fixed point theorem we canconstruct a function f such that f = ϕi , f(0) = i and for all n ∈ N
f(n + 1) =0, if S(fn 0) 6= S(fn )1, if S(fn 0) = S(fn ) and S(fn 1) 6= S(fn ).

Note that one of the two cases in the definition of f must happen for all n > 1.
Thus, we clearly have f ∈ Usd . On the other hand, S(fn ) 6= S(fn+1 ) for all n ∈ N acontradiction to Usd ∈ T- CONSϕ (S). Hence Usd ∈/ T- CONS.

21

Learning Recursive Functions

Note that the proof of this Corollary also showed that for every T-consistent strategy S ∈ R one can effectively construct a function f such that {f} ∈/ T- CONSϕ (S).
We finish this section by mentioning that for T-consistent learning identificationfrom arbitrarily ordered input and learning from input presented in natural ordermakes a difference. Thus, the following theorem nicely contrasts with Theorems 1
and 9. For a proof we refer the reader to Grieser [50].
Theorem 15. T- CONSarb ⊂ T- CONS
We continue by defining some more concepts of learning. This is done in the next
section.

5. Defining More Learning Models
So far, we have started from a learning model which, at first glance looked quite
natural, i.e., R- TOTALarb and continued by looking for possibilities to enlarge its
learning power. Though, conceptually, we shall follow this line of presentation, it istechnically advantageous to introduce several new concepts of learning at once in thissection.
The following learning model is the one with which it all started, i.e., Gold’s famous
learning in the limit model. In this model, all requirements on the intermediate
hypotheses such as being ψ-programs of recursive functions or being consistent are
dropped.
Definition 8 (Gold [47, 48]). Let U ⊆ R and let ψ ∈ P2 . The class U is said tobe learnable in the limit with respect to ψ if there is a strategy S ∈ P such that foreach function f ∈ U,(1) for all n ∈ N, S(fn ) is defined,(2) there is a j ∈ N such that ψj = f and the sequence (S(fn ))n∈N converges to j.
If U is learnable in the limit with respect to ψ by a strategy S, we write U[∈ LIMψ (S).
Let LIMψ = {U | U is learnable in the limit w.r.t. ψ}, and let LIM =LIMψ .
ψ∈P2

Again, some remarks are mandatory here. Note that LIMϕ = LIM for any Gödelnumbering ϕ. This can be shown by using exactly the same ideas as above (cf.
Lemma 2). In the above definition LIM stands for “limit.” There are also othernotations around to denote the learning type LIM. For example, in [11, 12, 13] thenotation GN is used. Here GN stands for Gödel numbering. Case and Smith [27]coined the notation EX which stands for “explain.”
As we have seen above when studying the learning types R- TOTAL and TOTAL,
it can make a difference with respect to the resulting learning power whether or not
we require the strategy to be in R or in P (cf. Theorem 7). On the other hand, thelearning type LIM is invariant to the demand S ∈ R instead of S ∈ P. This has

22Thomas Zeugmann and Sandra Zilles

already been shown by Gold [47] and for the sake of completeness we include thisresult here.
Theorem 16 (Gold [47]). Let (ϕ, Φ) be a complexity measure. There is afunction s ∈ R such that ϕs(i) ∈ R and LIMϕ (ϕi ) ⊆ LIMϕ (ϕs(i) ) for all i ∈ N.
Proof. For every (y0 , . . . , yn ) ∈ N∗ we set0,if Φi (h(y0 , . . . , yx )i) > nfor all x 6 nϕs(i) (h(y0 , . . . , yn )i) =
0
ϕ
(h(y
,
.
.
.
,
y
)i),
if
x 0 is the biggest x 6 n such

i
0
x


that Φi (h(y0 , . . . , yx )i) 6 n .
Now let f ∈ R be such that (ϕi (fn ))n∈N converges, say to j, and ϕj = f. Then,by construction, the sequence (ϕs(i) (fn ))n∈N also converges to j, but possibly with acertain delay. Thus, ϕs(i) learns f in the limit, too.
Hence, there exists a numbering ψ ∈ R2 such that for every U ∈ LIM there is a
strategy S ∈ Rψ satisfying U ∈ LIM(S). Clearly, it suffices to set ψi = ϕs(i) . Thisin turn implies that there is no effective procedure to construct for every strategy
ϕs(i) a function fi ∈ R such that {fi } ∈/ LIM(ϕs(i) ). In order to see this, suppose
the converse. Hence, the class {fi | i ∈ N} would be in NUM \ LIM, a contradiction,
since we obviously have NUM ⊆ LIM.
Furthermore, a straightforward modification of Definition 8 yields LIMarb , i.e.,learning in the limit from arbitrary input. Using the same idea as in the proof of
Theorem 1 one can easily show that LIM = LIMarb .
5.1. Varying the Mode of Convergence
Note that in general it is not decidable whether or not a strategy has alreadyconverged when successively fed some graph of a function. With the next definition
we consider a special case where it has to be decidable whether or not a strategy
has already learned its input function. That is, we replace the requirement that thesequence of all created hypotheses “has to converge” by “has to converge finitely.”
Definition 9 (Gold [48], Trakhtenbrot and Barzdin [96]). Let U ⊆ R andlet ψ ∈ P2 . The class U is said to be finitely learnable with respect to ψ if there is a
strategy S ∈ P such that for any function f ∈ U,(1) for all n ∈ N, S(fn ) is defined,(2) there is a j ∈ N such that ψj = f and the sequence (S(fn ))n∈N finitely converges
to j.
If U is finitely learnable with respect to ψ by a strategy S, we write U ∈ FINψ (S). Let
SFINψ = {U | U is finitely learnable w.r.t. ψ}, and let FIN = ψ∈P2 FINψ .

Learning Recursive Functions

23

Though the following result is not hard to prove, it provides some nice insight into
the limitations of finite learning. For stating it, we need the notion of accumulation
point. Let U ⊆ R; then a function f ∈ R is said to be an accumulation point of U if
for every n ∈ N there is a function f̂ ∈ U such that f =n f̂ but f 6= f̂.
Theorem 17 (Lindner [71]). Let U ⊆ R be any class such that U ∈ FIN. Then
U cannot contain any accumulation point.
Proof. Suppose the converse, i.e., there is a class U ∈ FIN containing an accumulation point f. Let S ∈ P such that U ∈ FIN(S). Then there must exist an n ∈ Nsuch S(fn ) = S(fn+1 ) = j. That is, the sequence (S(fn ))n∈N has finitely converged
to j and ϕj = f must hold. On the other hand, since f is an accumulation point,
there must be an f̂ ∈ U such that f =n+1 f̂ but f 6= f̂. Clearly, by the definitionof finite convergence we have S(f̂n ) = S(f̂n+1 ) = j, too, but ϕj = f 6= f̂. This is acontradiction to U ∈ FIN(S).
This theorem directly yields the following corollary.
Corollary 18. R- TOTAL # FIN
Proof. FIN \ R- TOTAL 6= ∅ is witnessed by Usd . Moreover, the function 0∞ ∈ U0
is clearly an accumulation point of the class U0 . Thus, by Theorems 17 and 2 we get
U0 ∈ R- TOTAL \ FIN.
Note that Theorem 50 provides a complete answer to the question under which
circumstances a class U ⊆ R is finitely learnable.
Next, we look at another mode of convergence which goes back to Feldman [31]who called it matching in the limit and considered it in the setting of learning languages. The difference to the mode of convergence used in Definition 8, which isactually syntactic convergence, is to relax the requirement that the sequence of hypotheses has to converge to a correct program by semantic convergence. Here bysemantic 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 has been coined by Case and Smith [27].
As far as learning of recursive functions is concerned, behaviorally correct learning
was formalized by Barzdin [9, 16].
Definition 10 (Barzdin [9, 16]). Let U ⊆ R and let ψ ∈ P2 . The class U is said
to be behaviorally correctly learnable with respect to ψ if there is a strategy S ∈ Psuch that for each function f ∈ U,(1) for all n ∈ N, S(fn ) is defined,(2) ψS(fn ) = f for all but finitely many n ∈ N.
If U is behaviorally correctly learnable with respect to ψ by a strategy S, we writeU ∈ BCψ (S). BCψ and BC are defined analogously to the above above.

24

Thomas Zeugmann and Sandra Zilles

Clearly, we have LIM ⊆ BC. On the other hand, even BC learning is not trivial,
i.e., we have R ∈/ BC. This is a direct consequence of the next theorem which showsthe even stronger result that BC is not closed under union. In the proof below we
use the convention that 0k denotes the empty string for k = 0. When we identify
a function with the sequence of its values then we mean by i00 20∞ the function f
expressed by i20∞ , i.e., f(0) = i, f(1) = 2 and f(x) = 0 for all x > 2.
Theorem 19 (Barzdin [16]). BC is not closed under finite union.
Proof. For showing the theorem it suffices to prove that Usd ∪ U0 ∈/ BC. The proof
is done indirectly. Suppose the converse, i.e., there is a strategy S ∈ P such thatUsd ∪ U0 ∈ BC(S). Then we can directly conclude S ∈ R.
Now we have to fool the strategy S such that it would have to “change its mind
semantically” infinitely often in order to learn the function to be constructed. For alli ∈ N we define a function fi as follows. Set fi (0) = i for all i ∈ N. The definition
continues in stages.
Stage 1. Try to compute ϕS(hii) (1), ϕS(hi0i) (2), . . . , ϕS(hi0k i) (k + 1), . . . , until thefirst value k1 is found such that ϕS(hi0k1 i) (k1 + 1) ↓ .
Let y1 = ϕS(hi0k1 i) (k1 + 1). Then we set fi (x) = 0 for all 1 6 x 6 k1 andfi (k1 + 1) = y1 + 1.
Goto Stage 2.
If none of the values ϕS(hii) (1), ϕS(hi0k i) (k + 1), k ∈ N+ , is defined, then Stage 1 is
not left. But in this case we are already done, since then {i0∞ } ∈/ BC(S).
For making the proof easier to access, we also include Stage 2 here.
Stage 2. Try to compute ϕS(hi0k1 f(k1 +1)i) (k1 + 2) , ϕS(hi0k1 f(k1 +1)0i) (k1 + 3), . . . ,ϕS(hi0k1 f(k1 +1)0k i) (k1 + k + 2), . . . , until the first value k2 is found such thatϕS(hi0k1 f(k1 +1)0k2 i) (k1 + k2 + 2) ↓ .
Let y2 = ϕS(hi0k1 f(k1 +1)0k2 i) (k1 + k2 + 2). Then we set fi (x) = 0 for all k1 + 2 6
x 6 k1 + k2 + 1 and fi (k1 + k2 + 2) = y2 + 1.
Goto Stage 3.
Again, if none of the values ϕS(hi0k1 f(k1 +1)i) (k1 + 2), ϕS(hi0k1 f(k1 +1)0k i) (k1 + k + 2),
k ∈ N+ , is defined, then Stage 2 is not left. But in this case we are again done, sincethen {i0k1 f(k1 + 1)0∞ } ∈/ BC(S).
Now this construction is iterated. We assume that Stage n, n > 1 has been left.
Then numbers k1 , . . . , kn have been found such thatϕS(fk1 +···+k` +` ) (k1 + · · · + k` + `) ↓for ` = 1, . . . , n .

iSo, fi (x) is already defined for all 0 6 x 6 k1 + · · · + kn + n.

25

Learning Recursive Functions

Stage n + 1, n > 2. Try to compute
ϕS(hi0k1 fi (k1 +1)···0kn fi (k1 +···+kn +n)i) (k1 + · · · + kn + n + 1)
ϕS(hi0k1 fi (k1 +1)···0kn fi (k1 +···+kn +n)0i) (k1 + · · · + kn + n + 2)···
ϕS(hi0k1 fi (k1 +1)···0kn fi (k1 +···+kn +n)0k i) (k1 + · · · + kn + n + k + 1)···
until the first value kn+1 is found such thatϕS(hi0k1 fi (k1 +1)···0kn fi (k1 +···+kn +n)0kn+1 i) (k1 + · · · + kn + n + kn+1 + 1) ↓ .
Let yn+1 = ϕS(hi0k1 fi (k1 +1)···0kn fi (k1 +···+kn +n)0kn+1 i) (k1 +· · ·+kn +n+kn+1 +1).
Then we set fi (x) = 0 for all k1 + · · · + kn + n + 1 6 x 6 k1 + · · · + kn + n + kn+1 ,and set fi (k1 + · · · + kn + kn+1 + n + 1) = yn+1 + 1.
As before, if Stage n + 1 is not left, we are already done. Thus, it remains to consider
the case that Stage n is left for all n > 1. Let s ∈ R be chosen such that ϕs(i) = fi
for all i ∈ N. By the fixed point theorem (cf., e.g., Smith [88]) there is a number jsuch that ϕs(j) = ϕj . Since fj = ϕs(j) = ϕj and fj (0) = j we get fj ∈ Usd . But
by construction we have ϕS(fk1 ) (k1 + 1) 6= fj (k1 + 1), ϕS(fk1 +k2 +1 ) (k1 + k2 + 2) 6=jj

fj (k1 + k2 + 2), . . . , ϕS(fk1 +···kn +n−1 ) (k1 + · · · + kn + n) 6= fj (k1 + · · · + kn + n), . . . .
jTherefore, when successively fed fn
j the strategy S outputs infinitely many wrong
hypotheses, and thus fj ∈/ BC(S), a contradiction to U0 ∪ Usd ∈ BC(S).
This proof directly yields the following corollary.
Corollary 20.
(1) R ∈/ BC.
(2) LIM is not closed under finite union.
(3) R ∈
/ LIM.
Proof. (1) is a direct consequence of Theorem 19. Clearly, Usd , U0 ∈ LIM andLIM ⊆ BC. Since Usd ∪ U0 ∈/ BC, Assertion (2) follows. Finally, (3) is directly
implied by Assertion (2).
Adleman and Blum [1] have shown that, under canonical formalization, the degreeof the algorithmic unsolvability of “R ∈ LIM” is strictly less than the degree of thealgorithmic unsolvability of the halting problem. Brand [23] studied the related problem of identifying all partial recursive functions. Of course, it is also algorithmicallyunsolvable but its degree and the degree of the halting problem are equivalent.

26

Thomas Zeugmann and Sandra Zilles

Moreover, Apsı̄tis et al. [7] investigated the problem in which cases unions of identifiable classes are also necessarily identifiable and obtained many interesting andbeautiful results.
On the other hand, many more function classes are learnable behaviorally correctly
than are learnable in the limit. In order to state this result and for pointing toanother interesting property of behaviorally correct learning, we modify Definition 8
by relaxing the learning goal. By R∗ and T∗ we denote the class of all functions f ∈ P
and f ∈ P, respectively, for which dom(f) is cofinite. For f, g ∈ T∗ and a ∈ N wewrite f =a g and f =∗ g if |{x ∈ N | f(x) 6= g(x)}| 6 a and |{x ∈ N | f(x) 6= g(x)}| < ∞,respectively. Note that there are three possibilities for a number x to belong to thesets just considered: both f(x) ↓ and g(x) ↓ , but f(x) 6= g(x), or f(x) ↓ while g(x) ↑ ,or f(x) ↑ and g(x) ↓ .
Definition 11 (Case and Smith [27]). Let U ⊆ R and let ψ ∈ P2 . Leta ∈ N ∪ {∗}. The class U is said to be learnable in the limit with a anomalies (in casea = ∗: with finitely many anomalies) with respect to ψ if there is a strategy S ∈ Psuch that for each function f ∈ U,(1) for all n ∈ N, S(fn ) is defined,(2) there is a j ∈ N such that ψj =a f and the sequence (S(fn ))n∈N converges to j.
This is denoted by U ∈ LIMaψ for short. The notions LIMaψ and LIMa are definedin the usual way.
Note that for a = 0, the inference type LIM0 coincides with LIM by definition.
The following theorem establishes an infinite hierarchy in dependence on the numberof anomalies allowed and relates this hierarchy to BC.
Theorem 21 (Barzdin [16], Case and Smith [27]).
S
LIM ⊂ LIM1 ⊂ LIM2 ⊂ · · · ⊂ a∈N LIMa ⊂ LIM∗ ⊂ BC
For a proof, we refer the reader to Case and Smith [27]. Note that the inclusion
LIM∗ ⊂ BC appeared already in Barzdin [16]. Thus the option to syntacticallychange hypotheses entails an error-correcting power.
Note that behaviorally correct learning with anomalies has also been studied intensively (cf., e.g., Case and Smith [27], Daley [29], Freivalds [35]). Further results
concerning learning with anomalies can be found e.g., in Freivalds et al. [42], Gasarch
et al. [46], Kinber and Zeugmann [62, 61], and Smith and Velauthapillai [90].
Furthermore, using the same ideas as in the proof of Theorem 16 one can easily
show the following result.
Theorem 22. Let (ϕ, Φ) be a complexity measure. There is a function s ∈ Rsuch that ϕs(i) ∈ R and BCϕ (ϕi ) ⊆ BCϕ (ϕs(i) ) for all i ∈ N.
There is another peculiarity we want to point to. If we sharpen the definition of
BC by adding the requirement that the set {S(fn ) | n ∈ N} of all produced hypotheses

Learning Recursive Functions

27

is of finite cardinality, then we again get the learning type LIM. This result appeared
first in Barzdin and Podnieks [18] and was generalized by Case and Smith [27] (seeTheorem 2.9).
A further interesting modification of behaviorally correct learning was introduced
by Podnieks [82]. Instead of requiring semantic convergence, he introduced a certain
type of uncertainty by demanding correct hypotheses to occur with a certain frequency.
Definition 12 (Podnieks [82]). Let 0 < p 6 1, let U ⊆ R and let ϕ ∈ Göd.
The class U is said to be behaviorally correctly learnable with frequency p if there isa strategy S ∈ P such that for each function f ∈ U,(1) for all n ∈ N, S(fn ) is defined,|{n | ϕM(fn ) = f, 0 6 n 6 k}|
>p
k→∞
k

(2) lim inf

If U is behaviorally correctly learnable with frequency p by a strategy S, we writeU ∈ BCfreq (p)(S). BCfreq (p) is defined analogously to the above.

1
1⊂ BCfreq n+2
for all n ∈ N. InPodnieks [82, 83] could prove that BCfreq n+1
tuitively, this theorem holds, since BC is not closed under union. For example, taking
U0 and Usd and trying half the time to learn any function in U0 ∪ Usd by simulating any learner for U0 and for Usd , respectively, and then outputting the hypotheses
obtained alternatingly shows that BC ⊂ BCfreq 12 .
Additionally, he discovered that the BCfreq hierarchy is discrete. More formally,
he showed the following. Let p with 1/n > p > 1/(n + 1) be given. Then we haveBCfreq (p) = BCfreq n1 .
Pitt [81] then defined the LIM–analogue to Podnieks’ behaviorally correct frequency identification, i.e., LIMfreq and showed an analogous theorem.
Another way to attack the non-closure under finite union has been proposed bySmith [87] who introduced the notion of team learning (or pluralistic inference). For
the sake of motivation imagine the task that a robot has to explore a planet. Theremay be different models for the dynamics of the planet and so the robot is required
to learn. While it may be possible to learn the parameters of each single model, due
to the non-closure under finite union, it may be impossible to learn the parametersof all these models at once. So, if the number of models is not too large, it may bepossible to send a finite number of robots instead of a single one. If one of them learns
successfully, the successful robot can perform the exploration.
So, in the basic model of team learning we allow m learning strategies instead ofa single one and request, for each f ∈ U, one of them to be successful. Of course, one
can consider teams of BC learners or teams of LIM learners. The resulting learning
types are denoted by BCteam (m) and LIMteam (m), respectively.
Last but not least, one can also consider probabilistic inference. In this model,
it is required that the sequence S(fn )n∈N converges with a certain probability p.

28Thomas Zeugmann and Sandra Zilles

This model has been introduced by Freivalds [43] in the setting of finite learning andwas then adapted to BC and LIM learning. Let us denote the resulting models by
BCprob (p) and LIMprob (p), respectively.
Pitt [81] obtained the following beautiful unification results. First, he showed that
BCfreq (p) = BCprob (p) and LIMfreq (p) = LIMprob (p) for every p with 0 < p 6 1.
Thus, probabilistic identification is also discrete. Additionally, he succeeded to prove
the following theorem.
Theorem 23 (Pitt [81]).
(1) BCfreq(2) LIMfreq

1n= BCprob n1 = BCteam (n) for every n ∈ N+ .


1
1
=
LIM
= LIMteam (n) for every n ∈ N+ .
prob
n
n



Furthermore, Wiehagen, Freivalds and Kinber [101] showed that, with probability
close to 1, probabilistic strategies learning in the limit with n mind changes are able
to identify function classes which cannot be identified by any deterministic strategy
learning in the limit with n mind changes. Additionally, Freivalds, Kinber and Wiehagen [40] studied finite probabilistic learning and probabilistic learning in the limit in
nonstandard numberings. In particular, for I ∈ {FIN, LIM}, they could show that
there exist numberings ψ such that, with respect to ψ, no infinite function class canbe I–learned deterministically, whereas every class in I is I-learnable with probability
1 − ε for every ε > 0.
Since there are some excellent papers treating probabilistic, pluralistic and frequency identification we are not exploring this subject here in more detail. Instead,the interested reader is referred to Ambainis [3], Apsı̄tis et al. [8], Daley [29], Pitt [81],Smith [87, 89] and the references therein.
5.2. Varying the Set of Admissible Strategies
It should be noted that in Definition 8 no requirement is made concerning theintermediate hypotheses output by strategy S. So, first, we again aim to introduce theconsistency requirement already considered in Section 4. However, there are several
possibilities to do this. Since a more detailed study of these different possibilities
will shed some light on the question of how natural are intuitive postulates, we shallprovide a rather complete discussion here. Additionally, in order to make it moreinteresting we consider the notion of δ–delay, too, which has recently been introduced
by Akama and Zeugmann [2].
Definition 13 (Akama and Zeugmann [2]). Let U ⊆ R, let ψ ∈ P2 and letδ ∈ N. The class U is called consistently learnable in the limit with δ–delay withrespect to ψ if there is a strategy S ∈ P such that
(1) U ∈ LIMψ (S),(2) ψS(fn ) (x) = f(x) for all f ∈ U, n ∈ N and all x such that x + δ 6 n.

Learning Recursive Functions

29

CONSδψ (S), CONSδψ and CONSδ are defined analogously to the above.
Note that for δ = 0 we get Barzdin’s [10] original definition of CONS. We therefore
usually omit the upper index δ if δ = 0. This is also done for all other versions ofconsistent learning defined below. We use the term δ–delay, since a consistent strategy
with δ–delay correctly reflects all but at most the last δ data seen so far. If a strategy
does not always work consistently with δ–delay we call it δ–delay inconsistent.
Next, we modify CONSδ in the same way Jantke and Beick [59] changed CONS,
i.e., we add the requirement that the strategy is defined on every input.
Definition 14 (Akama and Zeugmann [2]). Let U ⊆ R, let ψ ∈ P2 and letδ ∈ N. The class U is called R–consistently learnable in the limit with δ–delay withrespect to ψ if there is a strategy S ∈ R such that U ∈ CONSδψ (S).
R- CONSδψ (S), R- CONSδψ and R- CONSδ are defined analogously to the above.
Note that in Definition 14 consistency with δ–delay is only demanded for inputs
that correspond to some function f in the target class. Therefore, in the following
definition we incorporate Wiehagen and Liepe’s [102] requirement on a strategy towork consistently on all inputs into our scenario of consistency with δ–delay.
Definition 15 (Akama and Zeugmann [2]). Let U ⊆ R, let ψ ∈ P2 and letδ ∈ N. The class U is called T–consistently learnable in the limit with δ–delay withrespect to ψ if there is a strategy S ∈ R such that
(1) U ∈ CONSδψ (S),(2) ψS(fn ) (x) = f(x) for all f ∈ R, n ∈ N and all x such that x + δ 6 n.
T- CONSδψ (S), T- CONSδψ and T- CONSδ are defined in the same way as above.
So, for δ = 0 we again obtain the learning type T- CONS already considered at theend of Section 4.
Next, we introduce coherent learning (again with δ-delay). While our consistency
with δ-delay demand requires a strategy to correctly reflect all but at most the lastδ data seen so far, the coherence requirement only demands to correctly reflect the. δ) on input fn .
value f(n −Definition 16 (Akama and Zeugmann [2]). Let U ⊆ R, let ψ ∈ P2 and letδ ∈ N. The class U is called coherently learnable in the limit with δ–delay withrespect to ψ if there is a strategy S ∈ P such that
(1) U ∈ LIMψ (S),. δ) = f(n −. δ) for all f ∈ U and all n ∈ N such that n > δ.
(2) ψS(fn ) (n −COHδψ (S), COHδψ and COHδ are defined analogously to the above.
Now, performing the same modifications to coherent learning with δ–delay as we
did in Definitions 14 and 15 to consistent learning with δ–delay results in the learning

30

Thomas Zeugmann and Sandra Zilles

types R- COHδ and T- COHδ , respectively. We therefore omit the formal definitionsof these learning types here.
Using standard techniques one can show that for all δ ∈ N and all learning types
LT ∈ {CONSδ , R- CONSδ , T- CONSδ , COHδ , R- COHδ , T- COHδ } we have LTϕ = LTfor every Gödel numbering ϕ (cf. Lemma 2).
A natural question arising is whether or not the introduction of δ–delay to consistent and coherent learning yields an advantage with respect to the learning power ofthe defined learning types.
For answering this problem it is advantageous to recall the definition of reliable
learning introduced by Blum and Blum [19] and Minicozzi [75]. Intuitively, a learning
strategy S is reliable on a set M provided it converges, when fed the graph of a function
f in M, if and only if it learns f. Thus, reliable strategies signal their inability to learn
by performing infinitely many mind changes.
Definition 17 (Blum and Blum [19], Minicozzi [75]). Let U ⊆ R, let M ⊆ P
and let ϕ ∈ Göd; then U is said to be reliably learnable on M if there is a strategy
S ∈ R such that
(1) U ∈ LIMϕ (S), and(2) for all functions f ∈ M, if the sequence (S(fn ))n∈N converges, say to j, thenϕj = f.
M-REL denotes the family of all function classes that are reliably learnable on M.
In particular, we shall consider the cases where M = T and M = R, i.e., reliable
learnability on the set of all total functions and all recursive functions, respectively.
For the sake of completeness, we also mention here that the family of all function
classes reliably identifiable on the set of all partial functions equals the set of all function classes reliably learnable on the set of all partial recursive functions. Furthermore,reliable learning on the set of all partial functions allows the following characterizationin terms of consistency.
Theorem 24 (Blum and Blum [19]). P-REL = P-REL = T- CONSarb .
Moreover, reliable learning possesses some very nice closure properties as shownby Minicozzi [75] (cf. Theorems 3 and 4 in [75]). For the sake of completeness, werecall these results here but refer the reader to [75] for a proof.
Theorem 25 (Minicozzi [75]). Let M ⊆ P; then we have:(1) M-REL is closed under recursively enumerable union.
(2) For every class U ⊆ R, if U ∈ M-REL then also the class of all finite variantsof the functions in U is reliable learnable on M, i.e., [[U]] ∈ M-REL.

Learning Recursive Functions

31

The following theorem provides a first insight into the learning capabilities of reliable learning in dependence on the set M. The first rigorous proof of T-REL ⊂ R-REL
appeared in Grabowski [49]. A conceptually much easier proof has been provided by
Stephan and Zeugmann [94]. Therefore, we skip this proof below.
Theorem 26. P-REL ⊂ T-REL ⊂ R-REL ⊂ LIM.
Proof. P-REL ⊂ T-REL is a direct consequence of Theorems 15 and 24.
R-REL ⊆ LIM is obvious. For showing that LIM \ R-REL 6= ∅, we use the class Usd
which is clearly in LIM. Suppose Usd ∈ R-REL. Then applying Theorem 25 directly
yields [[Usd ]] ∈ R-REL, too. But [[Usd ]] = R (cf. Claim 2 in the proof of Lemma 1).
Since R-REL ⊆ LIM, we get R ∈ LIM, a contradiction to Corollary 20.
Note that one can extend the notion of reliable learning to behaviorally correct
reliable inference, too. Additionally, starting from the notion of reliability one candefine for BC– and LIM–type identification the notion of one-sided error probabilistic
learning as well as of reliable frequency identification (see Kinber and Zeugmann [61]).
The flavor of the obtained results is similar to Podnieks’ [82, 83] and Pitt’s [81]. On
the other hand, one can also look at team learning as a way of introducing a bounded
nondeterminism to learning. But even introducing an unbounded nondeterminism toreliable learning does not enlarge the learning capabilities of reliable LIM inference(see Pitt [81], Theorem 4.14). So, though we have Theorem 23, there are subtle
differences between probabilistic and frequency identification on the one hand andpluralistic learning on the other.
5.3. Varying the Information Supply
Next, we consider two variations of the information fed to the learner. Looking at
all the learning models defined so far we see that a strategy has always access to all
examples presented so far. In the following definition, we consider the variant where
the strategy is only allowed to use its last guess and the new datum coming in.
Definition 18 (Wiehagen [97]). Let U ⊆ R and let ψ ∈ P2 . The class U is said
to be iteratively learnable with respect to ψ if there is a strategy S ∈ P such that foreach function f ∈ U,(1) for every n ∈ N, Sn (f) is defined, where
S0 (f) = S(0, f(0)), andSn+1 (f) = S(Sn (f), n + 1, f(n + 1)).
(2) There is a j ∈ N such that ψj = f and the sequence (S(fn ))n∈N converges to j.
If the class U is iteratively learnable with respect to ψ by a strategy S, we write
U ∈ IT ψ (S). Furthermore, IT ψ and IT are defined analogously to the above.

32

Thomas Zeugmann and Sandra Zilles

Of course, an iterative strategy can try to memorize the pairs (n, f(n)) in its
current hypothesis. Then the strategy would have access to the whole initial segment
fn presented so far. On the other hand, the strategy has to converge. Therefore,
an iterative strategy can only memorize finitely many pairs (n, f(n)), i.e., a finite
subfunction, in its hypothesis. Consequently, it is only natural to ask whether or not
this restriction does decrease the resulting learning power. The affirmative answer isprovided by the following theorem.
Theorem 27 (Wiehagen [97]). IT ⊂ LIM
Proof. Clearly, we have IT ⊆ LIM. It remains to show that LIM \ IT 6= ∅.
The separating class U is defined as follows. We modify the class of self-describing
functions a bit by requiring all function values to be strictly positive, i.e., we set
Usdp = {f | f ∈ R, ϕf(0) = f, ∀x[f(x) > 0]} and U = U0 ∪ Usdp .
Claim 1. U ∈ LIM
Intuitively, the desired strategy S outputs f(0) as long as all function values seen
so far are greater than 0. If S sees 0 as a function value for the first time, it switches
its learning mode. From this point onwards S uses the identification by enumeration
strategy to learn the target function. We omit the details.
Claim 2. U ∈/ IT
It suffices to show that for every S with U0 ∈ IT ϕ (S) there is a function f ∈ Usdp
such that f ∈/ IT ϕ (S). Let s ∈ R be chosen such that for all j ∈ N
ϕs(j) (0) = j, and for all n ∈ N : 1, if S(Sn (ϕs(j) ), n + 1, 1) 6= Sn (ϕs(j) )2, if S(Sn (ϕs(j) ), n + 1, 1) = Sn (ϕs(j) ) andϕs(j) (n + 1) =S(Sn (ϕs(j) ), n + 1, 2) 6= Sn (ϕs(j) )Note that one of these cases must happen. For seeing this, suppose the converse. Letm be the least n such that
S(Sn−1 (ϕs(j) ), n, 1) = S(Sn−1 (ϕs(j) ), n, 2) = Sn−1 (ϕs(j) ) .
Now consider the functions g and g 0 defined as ϕs(j) (x), if x < m
1, if x = m
g(x) =
0, if x > m ,and g 0 (x) = g(x) for all x 6= m and g 0 (m) = 2. Since g, g 0 ∈ U0 the strategy S
must iteratively learn both g and g 0 . But by the choice of m we can directly conclude
that the sequences (Sn (g))n∈N and (Sn (g 0 ))n∈N converge to the same number, acontradiction.
Consequently, ϕs(j) ∈ R for every j. By the fixed point theorem (cf., e.g., [88])there is an i ∈ N such that ϕi = ϕs(i) . By construction, ϕi ∈ Usdp and S changes its
hypothesis in every learning step when successively fed ϕi . Thus, for f = ϕi we havef∈
/ IT ϕ (S).

Learning Recursive Functions

33

It should be mentioned that Wiehagen [97] proved a slightly stronger result than
our Theorem 27, since he showed the class U in the proof above to be even learnable
by a feed-back strategy. A feed-back strategy, when successively fed a function fworks like an iterative strategy but can additionally make a query by computing anargument x and asking for f(x). While feed-back learning is stronger than iterative
learning, it is still weaker than learning in the limit. It should be noted that a suitably
modified version of feed-back learning has recently attracted attention in the settingof language learning from positive data (see [24, 68]).
Finally, iterative learning is also quite sensitive to the order in which examples arepresented. Jantke and Beick [59] considered IT arb and showed the following result.
Theorem 28 (Jantke and Beick [59]). R- TOTAL # IT arb
In the next definition, we consider a variant of how to enrich the information
presented to a learner. This type of inference has been introduced by Wiehagen [99]and has been intensively studied in Freivald and Wiehagen [32]. It has been further
investigated by Freivalds, Botuscharov, and Wiehagen [38] and, in the context oflanguage identification, by Jain and Sharma [56]. We refer to it as learning withadditional information.
Definition 19 (Wiehagen [99]). Let U ⊆ R and let ϕ ∈ Göd. U ∈ LIM+ if
there is a strategy S ∈ P2 such that for every f ∈ U and for every bound s > minϕ f
the following conditions are satisfied.
(1) S(s, fn ) is defined for all n ∈ N, and(2) the sequence (S(s, fn ))n∈N converges to a number j such that ϕj = f.
Whenever appropriate, we shall also consider LT + for any of the learning types
defined in this paper.
Learning with additional information shows that consistent learning is full of surprises. Note that Assertion (1) in the following theorem has been shown by Freivald
and Wiehagen [32], while Assertion (2) goes back to Wiehagen [99].
Theorem 29 (Freivald and Wiehagen [32], Wiehagen [99]).
(1) T- CONS+ = T- CONS, and(2) R ∈ CONS+ .
Proof. Since we obviously have T- CONS ⊆ T- CONS+ , it suffices to show that
T- CONS+ ⊆ T- CONS. Let U ∈ T- CONS+ (S), where S ∈ R2 . Then for everyf ∈ U we can construct in the limit a number s such that the sequence (S(s, fn ))n∈N
converges to a number j. Since S is T-consistent, we can conclude that ϕj = f. Note
that, in general, we do not have s > minϕ f. The formal proof is done as follows. We
have to define a strategy S 0 ∈ R such that U ∈ T- CONS(S 0 ). Let α ∈ N∗ be any
tuple of length 1. The desired strategy S 0 is defined as follows.
We set i0 = 0 and S 0 (α) = S(i0 , α).

34Thomas Zeugmann and Sandra Zilles

Now assume n ∈ N such that in and S 0 (α) for all tuples of length n + 1 are alreadydefined. Let y ∈ N; we set
in+1 = in and S 0 (αy) = S(in , αy) provided S(in , αy) = S(in , α). Otherwise, we
set in+1 = in + 1 and S 0 (αy) = S(in+1 , αy).
By construction, we directly obtain S 0 ∈ R because of S ∈ R2 . Furthermore, S is Tconsistent, so is S 0 . Additionally, since for every f ∈ U there is an s ∈ N such that thesequence (S(s, fn ))n∈N converges (every s > minϕ f has this property) the sequence(S 0 (fn ))n∈N must converge, too. So, let j be the number the sequence (S 0 (fn ))n∈N
converges to. Finally, by the T-consistency of S 0 we can conclude that ϕj = f. This
proves Assertion (1).
For showing the remaining Part (2), we use the amalgamation technique (cf. Wiehagen [99], Case and Smith [27]). 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 definedby running ϕi (x) for every i ∈ I in parallel and taking the first value obtained, ifany. The desired strategy S ∈ P2 is mainly defined by using the function amal defined
above. Let f ∈ R and let s ∈ N; we set If,−1 = {0, . . . , s}. For n > 0 we proceedinductively. Assume If,n−1 to be already defined. We set
t = “the minimal number such that for all 0 6 x 6 n there is ani ∈ If,n−1 with Φi (x) 6 t and ϕi (x) = f(x) .”Furthermore, we defineI−f,n = {i | i ∈ If,n−1 , ∃x 6 n[Φi (x) 6 t, ϕi (x) 6= f(x)]} .
2
Moreover, we set If,n = If,n−1 \ I−f,n . Now we define the desired strategy S ∈ P as
follows. For all n ∈ N and all s ∈ N let

S(s, fn ) = “Compute If,n . If the computation of If,n stops then let
S(s, fn ) = amal(If,n ).
Otherwise, S(s, fn ) = ↑ .”It remains to show that R ∈ CONS+ (S). Let s ∈ N be any number such thats > minϕ f. Then, by construction, the computation of If,n stops for all n ∈ N and
we have If,n ⊆ If,n−1 for all n ∈ N. Furthermore, by construction S is consistent, too.
Since minϕ f ∈ If,n for all n ∈ N, we also have If,n 6= ∅ for all n ∈ N. Consequently,
the sequence (If,n )n∈N of sets converges to a finite and non-empty set I containing
at least one ϕ-program for f. Thus, the sequence (S(s, fn ))n∈N converges to amal(I)and since S is consistent we can conclude ϕamal(I) = f. This proves Assertion (2).
Another interesting effect is observed when studying FIN+ . In contrast to Theorem 17, the learning type FIN+ comprises classes containing an accumulation point,e.g., U = {0i 10∞ | i 6 minϕ 0i 10∞ } ∪ {0∞ }. On the other hand, it is easy to show that{0i 10∞ | i ∈ N} ∪ {0∞ } ∈/ FIN+ . Thus, we directly get:Learning Recursive Functions

35

Theorem 30. FIN ⊂ FIN+ ⊂ ℘(R).
For further information concerning inductive inference with additional information,
we refer the interested reader to Jain et al. [55].
Before exploring further relations between consistent and reliable learning we takea closer look at coherent and consistent identification.
5.4. Coherence and Consistency of Learning Strategies
In this subsection we study the question whether or not the relaxation to learncoherently with δ–delay instead of demanding consistency with δ–delay does enhance
the learning power of the corresponding learning types introduced above. The negative
answer is provided by the following theorem.
Theorem 31 (Akama and Zeugmann [2]). Let δ ∈ N be arbitrarily fixed. Then
we have(1) CONSδ = COHδ ,(2) R- CONSδ = R- COHδ ,(3) T- CONSδ = T- COHδ .
Proof. By definition, we obviously have CONSδ ⊆ COHδ , R- CONSδ ⊆ R- COHδand T- CONSδ ⊆ T- COHδ .
For showing the opposite directions we can essentially use the same idea for all
three cases. Let δ ∈ N, ϕ ∈ Göd, U ⊆ R and any strategy Ŝ be arbitrarily fixedsuch that U ∈ LTϕ (Ŝ), where LT ∈ {COHδ , R- COHδ , T- COHδ }. Next, we define astrategy S as follows. Let f ∈ R and let n ∈ N. On input fn do the following.
1. Compute Ŝ(f0 ), . . . , Ŝ(fn ) and determine the largest number n∗ such that∗∗Ŝ(fn −1 ) 6= Ŝ(fn ).
2. Output the canonical ϕ–program i computing the following function g:
g(x) = f(x) for all x 6 n∗ , andg(x) = ϕŜ(fn∗ ) (x) for all x > n∗ .
First, we show that S learns U consistently with δ–delay.
By construction, we have ϕS(fn ) (x) = f(x) for all x 6 n∗ , and thus S is consistenton f(0), . . . , f(n∗ ). If n − n∗ 6 δ, we are already done. Finally, if n − n∗ > δ, then∗∗we exploit the fact that Ŝ works coherently with δ–delay and that Ŝ(fn +k ) = Ŝ(fn )for all k = 1, . . . , n − n∗ . Thus, for all k ∈ {1, . . . , n − n∗ − δ} we getϕS(fn ) (n∗ + k) = ϕŜ(fn∗ ) (n∗ + k) = ϕŜ(fn∗ +δ+k ) (n∗ + k) = f(n∗ + k) .

(2)

36

Thomas Zeugmann and Sandra Zilles

Since in this case Ŝ(fn ) is defined for all f ∈ U and all n ∈ N, we can directly conclude
that S(fn ) is defined for all f ∈ U and all n ∈ N, too. This proves Assertion (1).
If Ŝ ∈ R, then so is S and thus Assertion (2) follows.
Finally, if Ŝ ∈ R and Ŝ works T–coherently, then we directly get S ∈ R and S is
T–consistent, since now (2) is true for all f ∈ R. This completes the proof.

6. Characterizations in Terms of Complexity
In this section we characterize T- CONSδ , CONSδ , T-REL, R-REL, and LIM interms of complexity. The importance of such characterizations has already been explained in Subsection 3.1. However, in order to achieve the aforementioned characterizations, several modifications are necessary. In particular, so far we used functions tocompute the relevant complexity bounds in the definitions of the complexity classes
Rt , where t ∈ R and in Rh , where h ∈ R2 . Now we need stronger tools, i.e., computable operators which are introduced next.
First, we recall the definitions of recursive and general recursive operator. Let(Fx )x∈N be the canonical enumeration of all finite functions.
Definition 20 (Rogers [86]). A mapping O : P 7→ P from partial functions to partial 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 iff there is an x ∈ Nsuch that (x, y, z) ∈ W and f extends the finite function Fx .
Furthermore, a partial recursive operator O is called a general recursive operator
iff T ⊆ dom(O), and f ∈ T implies O(f) ∈ T.
A mapping O : P 7→ P is called an effective operator iff there is a function g ∈ Rsuch 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
the reader is referred to [52, 77, 107]. If O is an operator which maps functions tofunctions, we write O(f, x) to denote the value of the function O(f) at the argument x.
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 tape of T (under unlimited working time).
Let O be a general recursive or total effective operator. Then, for f ∈ dom(O),m ∈ N, we set: ∆O(f, m) =“the least n such that, for all x 6 n, f(x) is defined and,for the computation of O(f, m), the Turing machine T only uses the pairs (x, f(x))
with x 6 n; if such an n does not exist, we set ∆O(f, m) = ∞.”For u ∈ R we define Ωu to be the set of all partial recursive operators O satisfying∆O(f, m) 6 u(m) for all f ∈ dom(O). For the sake of notation, below we shall use
id + δ, δ ∈ N, to denote the function u(x) = x + δ for all x ∈ N.

Learning Recursive Functions

37

Now we are ready to provide the first group of characterizations.
6.1. Characterizing T- CONSδ and CONSδ
Note that in the following we use mainly ideas and techniques from Blum andBlum [19] and Wiehagen [99].
Furthermore, in the following we always assume that learning is done with respect
to any fixed ϕ ∈ Göd.
As in Blum and Blum [19] we define operator complexity classes as follows. Let O
be any computable operator; then we set
RO = {f | ∃i[ϕi = f ∧ ∀∞ x[Φi (x) 6 O(f, x)]]} ∩ R .
First, we characterize T- CONSδ .
Theorem 32. Let U ⊆ R and let δ ∈ N; then we have: U ∈ T- CONSδ if andonly if there exists a general recursive operator O ∈ Ωid+δ such that O(R) ⊆ R andU ⊆ RO .
Proof. Necessity. Let U ∈ T- CONSδ (S), S ∈ R. Then for all f ∈ R and all n ∈ N
we define O(f, n) = ΦS(fn+δ ) (n).
Since ϕS(fn+δ ) (n) is defined for all f ∈ R and all n ∈ N by Condition (2) ofDefinition 15, we directly get from Condition (1) of the definition of a complexity
measure that ΦS(fn+δ ) (n) is defined for all f ∈ R and all n ∈ N, too. Moreover,for every t ∈ T and n ∈ N there is an f ∈ R such that tn = fn . Hence, we haveO(T) ⊆ R ⊆ T. Moreover, in order to compute O(f, n) the operator O reads only
the values f(0), . . . , f(n + δ). Thus, we have O ∈ Ωid+δ .
Now let f ∈ U. Then the sequence (S(fn ))n∈N converges to a correct ϕ–program
i for f. Consequently, O(f, n) = Φi (n) for almost all n ∈ N. Therefore, we conclude
U ⊆ RO .
Sufficiency. Let O ∈ Ωid+δ such that O(R) ⊆ R and U ⊆ RO . We have to definea strategy S ∈ R such that U ∈ T- CONSδ (S). By the definition of RO we know thatfor every f ∈ U there exist i and k such that ϕi = f and Φi (x) 6 max{k, O(f, x)} forall x. Thus, the desired strategy S searches for the first current candidate for such apair (i, k) in the canonical enumeration c2 of N × N and converges to i provided an
appropriate pair has indeed been found. Until this pair (i, k) is found, the strategy S
outputs auxiliary consistent hypotheses. For doing this, we choose g ∈ R such thatϕg(hαi) (x) = yx for every tuple α ∈ N∗ , α = (y0 , . . . , yn ) and all x 6 n.
. δ. Search for the least z 6 n such that
S(fn ) = “Compute O(f, x) for all x 6 n −for c2 (z) = (i, k) the conditions. δ, and(A) Φi (x) 6 max{k, O(f, x)} for all x 6 n −38Thomas Zeugmann and Sandra Zilles. δ(B) ϕi (x) = f(x) for all x 6 n −are fulfilled. If such a z is found, set S(fn ) = i.
Otherwise, set S(fn ) = g(fn ).”. δ and since
Since O ∈ Ωid+δ , the strategy can compute O(f, x) for all x 6 n −c2 ∈ R it also can perform the desired search effectively. By Condition (2) of thedefinition of a complexity measure, the test in (A) can be performed effectively, too.
If this test has succeeded, then Test (B) can also be effectively executed by Condition(1) of the definition of a complexity measure. Thus, we get S ∈ R. Finally, byconstruction S is always consistent with δ-delay, and if f ∈ U, then the sequence(S(fn ))n∈N converges to a correct ϕ–program for f.
Theorem 33. Let U ⊆ R and let δ ∈ N; then we have: U ∈ CONSδ if andonly if there exists a partial recursive operator O ∈ Ωid+δ such that O(U) ⊆ R andU ⊆ RO .
Proof. The necessity is proved mutatis mutandis as in the proof of Theorem 32
with the only modification that O(f, x) is now defined for all f ∈ U instead of for allf ∈ R. This directly yields O ∈ Ωid+δ , O(U) ⊆ R and U ⊆ RO .
The only modification for the sufficiency part is to leave S(fn ) undefined if O(f, x)
is not defined for f ∈/ U. We omit the details.
We continue this section by using Theorem 32 to show that T- CONSδ is closed
under enumerable unions.
Theorem 34. Let δ ∈ N and let (Si )i∈N be a recursive enumeration of strategies
working T-consistently with δ-delay. Then there exists a strategy S ∈ R such thatSδδi∈N T- CONS (Si ) ⊆ T- CONS (S).
Proof. The proof of the necessity of Theorem 32 shows that the construction of
the operator O is effective provided a program for the strategy is given. Thus, we
effectively obtain a recursive enumeration (Oi )i∈N of operators Oi ∈ Ωid+δ such that
Oi (R) ⊆ R and T- CONSδ (Si ) ⊆ ROi .
Now we define an operator O as follows. Let f ∈ R and x ∈ N. We set O(f, x) =max{Oi (f, x) | i 6 x}.
SThus, we directly get O ∈ Ωid+δ , O(R) ⊆ R and i∈N T- CONSδ (Si ) ⊆ RO . By
S
Theorem 32 we can conclude i∈N T- CONSδ (Si ) ⊆ T- CONSδ (S).
On the other hand, CONSδ and R- CONS are not even closed under finite union.
This is a direct consequence of Theorem 19. It is easy to verify that Usd , U0 ∈R- CONSδ and thus Usd , U0 ∈ CONSδ for every δ ∈ N. But Usd ∪ U0 ∈/ BC.
6.2. Characterizing T-REL, R-REL and LIM

Learning Recursive Functions

39

We continue with the characterizations of T-REL, R-REL and LIM in terms ofcomplexity. As the following theorem shows, these characterizations express the difference of these learning models by different sets of admissible operators, i.e., generalrecursive, total effective and effective operators, respectively. Assertion (1) has beenshown by Grabowski [49], Assertion (2) by Blum and Blum [19] and Assertion (3) isa variation of a corresponding characterization obtained by Wiehagen [99].
In the proofs below, it is technically convenient to use limiting recursive functionals
instead of partial recursive functions as strategies. For a formal machine independent
definition of a limiting recursive functional see Rogers [86]. Intuitively, a limiting
recursive functional is a mapping which maps functions to numbers in a computableway. Using 3-tape Turing machines with input, work and output tape and a read-only
head for the input tape, a read-write head for the work tape and a write-only headfor the output tape, a limiting recursive functional can be defined as follows.
A partial mapping S : P 7→ N is called limiting recursive functional if there is a
3-tape Turing machine T (as described above) working as follows:
If an arbitrary function f ∈ P is written down on the input tape of T (in anarbitrary enumeration of input-output examples where repetitions are allowed), then,if S(f) is defined, T writes a finite nonempty sequence of natural numbers on the
output tape such that the last number is equal to S(f); (T does not need to stop after
doing so), or T writes an infinite sequence of natural numbers which converges on its
output tape such that its limit is equal to S(f). It is allowed that the sequence written
on the output tape depends on the enumeration in which the function f is written on
the input tape, but it is prohibited that its limit depends on it.
If S(f) is not defined, then two cases are possible. First, S does not uniformly
converge on some enumeration in which the function f is written on the input tape.
Second, S never converges – independent of the enumeration in which the function f is
written on the input tape. These cases are not equivalent (cf. Freivald [33]). Therefore,
we require that for all f ∈ P we have: f ∈/ dom(S) iff S on f never converges.
Theorem 35. Let U ⊆ R, then we have:(1) U ∈ T-REL if and only if there exists a general recursive operator O such thatU ⊆ RO .
(2) U ∈ R-REL if and only if there exists a total effective operator O such thatU ⊆ RO .
(3) U ∈ LIM if and only if there exists an effective operator O such that O(U) ⊆ R
and U ⊆ RO .
Proof. Necessity. The first part of the proof is almost the same for all three assertions. Let LT ∈ {T-REL, R-REL, LIM} and let U ⊆ LT (S) for some strategy S ∈ R.
The desired operator O is defined as follows. Let f ∈ M and let x ∈ N.

40

Thomas Zeugmann and Sandra Zilles

O(f, x) = “Compute S(fx ). Use half of the time for executing (A) and (B) until (C)or (D) happens.
(A) Compute S(fx+1 ), S(fx+2 ), . . .
(B) Check if ΦS(fx ) (x) = y for y = 0, 1, 2, . . .
(C) In (A) a k ∈ N is found such that S(fx ) 6= S(fx+k ). Set
O(f, x) = 0.
(D) In (B) a y ∈ N is found such that ΦS(fx ) (x) = y. Set
O(f, x) = ΦS(fx ) (x).”First, we show the necessity part of Assertion (1). Clearly, the operator O is recursive,
since by Definition 17, for all f ∈ T and all x ∈ N we have that S(fx ) is defined. Test
(B) can be effectively executed by Property (2) of a complexity measure. It remains
to show that O is general recursive.
Claim 1. O(T) ⊆ T.
Suppose that for some f ∈ T and some x ∈ N the value O(f, x) is not defined.
Then, in particular, (C) cannot happen. But this means that S(fx ) = S(fx+n ) for alln ∈ N. Therefore, the sequence (S(fm )m∈N converges to S(fx ). Since S is reliable on
T, we know that ϕS(fx ) = f. Consequently, ϕS(fx ) (x) is defined and thus, by Property(1) of a complexity measure, ΦS(fx ) (x) is defined, too. Thus, in (D) a y must be foundsuch that ΦS(fx ) (x) = y, a contradiction to O(f, x) undefined. This proves Claim 1.
Claim 2. U ⊆ RO .
Let f ∈ U be arbitrarily fixed. Since U ∈ LIM(S), the sequence (S(fm ))m∈N
converges, say to j and ϕj = f. Thus, in the definition of O(f, x), Test (C) can succeed
only finitely often. That is, for all but finitely many x we have O(f, x) = ΦS(fx ) (x).
Consequently, f ∈ RO . Thus Claim 2 is shown and the necessity part of Assertion (1)follows.
For showing the necessity part of Assertion (2) note that the operator O is effective,
too. We have to show O(R) ⊆ R instead of Claim 1, while Claim 2 and its proof
remain unchanged. This can be done mutatis mutandis as above.
For the necessity part of Assertion (3) we again note that the operator O is effective,
since by Definition 8 we know that S(fx ) is defined for all f ∈ U and all x ∈ N. Now
we have to show that O(U) ⊆ R, while Claim 2 and its proof again remain unchanged.
Claim 3. O(U) ⊆ R.
Suppose that for some f ∈ U and some x ∈ N the value O(f, x) is not defined.
Then, in particular, (C) cannot happen. But this means that S(fx ) = S(fx+n ) for
all n ∈ N. Therefore, the sequence (S(fm ))m∈N converges to S(fx ). Since f ∈ U andU ∈ LIM(S), we know that ϕS(fx ) = f. Consequently, ϕS(fx ) (x) is defined and thus,
by Property (1) of a complexity measure, ΦS(fx ) (x) is defined, too. Thus, in (D) a ymust be found such that ΦS(fx ) (x) = y, a contradiction to O(f, x) undefined. This
proves Claim 3.

Learning Recursive Functions

41

Thus, we have shown the necessity parts of Assertions (1) through (3).
Sufficiency. Again, the first part of the proof is identical for Assertions (1) through(3). Let O be an operator satisfying the relevant conditions. We define the desired
strategy as a limiting recursive functional.
S(f) = “Execute Stage 0:
Stage n: Compute c2 (n) = (i, k). Output i.
Check for all x ∈ N whether or not Φi (x) 6 max{k, O(f, x)} and ϕi (x) =f(x). If this test fails for some x, stop executing Stage n and goto Stagen + 1.”
Now for showing Assertions (1) through (3) it suffices to distinguish the cases M ∈{T, R, U} and to show that S is reliable on M. Note that these three cases arecompletely reflected by the domain of the operator O.
Claim 1. S is reliable on M.
Let f ∈ M. Then we can conclude that O(f, x) is defined for all x ∈ N. Now
suppose that f ∈ dom(S), i.e., S(f) converges, say to i. Since S performs a mindchange every time it enters a new stage, it follows that S enters some Stage n, wherec2 (n) = (i, k) and never leaves it. Thus, it verifies that Φi (x) 6 max{k, O(f, x)} andϕi (x) = f(x) for all x ∈ N. This proves Claim 1.
The following claim is identical for Assertions (1) through (3).
Claim 2. f ∈ RO implies S learns f.
By the definition of RO we know that for every f ∈ RO there exist i and k suchthat ϕi = f and Φi (x) 6 max{k, O(f, x)} for all x. Then S can never go past Stagen, where c2 (n) = (i, k). It follows that S converges, and since S is reliable, it learns
f. Hence, Claim 2 is shown.
By Claims 1 and 2 the theorem follows.
Further characterizations in the same style as above are possible. Wiehagen [99]showed a characterization of LIM∗ , Kinber and Zeugmann [62] characterized T-RELa
for every a ∈ N ∪ {∗}.
Note that sometimes also a different and stronger characterization of learning types
in terms of complexity is possible. The first results along this line can be found inBlum and Blum [19], who also coined the term a-posteriori characterization. For
stating such a characterization, the notion of compression index is needed.
Definition 21 (Blum and Blum [19]). Let (ϕ, Φ) be a complexity measure,let f ∈ R, and let O be a general recursive operator. Then i ∈ N is said to be an
O-compression index of f if
(1) ϕi = f,42Thomas Zeugmann and Sandra Zilles(2) ∀j[ϕj = f → ∀x[Φi (x) 6 O(Φj , max{i, j, x})]] .
In this case we also say that the function f is everywhere O-compressed.
Then Blum and Blum [19] could prove the following characterization.
Theorem 36 (Blum and Blum [19]). Let U ⊆ R, then we have: U ∈ R-REL
if and only if there is a general recursive operator O such that every function in U iseverywhere O-compressed.
Consequently, function classes that are reliably identifiable on the set R have theproperty that every function of the class does possess a fastest program modulo a general recursive operator, where “fastest program modulo a general recursive operator
O” is formalized by the notion of O-compression index.
Further results along this line have been achieved. We refer the interested reader
to Grabowski [49] and Zeugmann [106, 109].

7. Learning and Consistency – Part II
The main goal of this section is a thorough study of the learning power of the different models of consistent learning with and without δ-delay. As we have seen above,certain additional information can help to learn the whole class of recursive functions
consistently without δ-delay, i.e., CONS+ = ℘(R) (cf. Theorem 29) – whereas we have
not yet studied the exact effect of omitting additional information in CONSδ -learning.
So it is only natural to analyze the learning power of CONSδ -models more thoroughly.
We start with δ = 0. The following theorem actually states that the demand to learn
consistently is a severe restriction to the learning power.
Theorem 37 (Barzdin [10], Wiehagen [97]). CONS ⊂ IT
Proof. CONS ⊆ IT follows from the fact that an iterative strategy can recompute allvalues seen so far from the hypothesis it receives as input and then take the previous
values and the new value to simulate the consistent strategy. We omit the details.
For showing the remaining part, i.e., IT \ CONS 6= ∅, we use the following class
U = {f ∈ R | f = αjp, α ∈ N∗ , j > 2, p ∈ R{0,1} , ϕj = f}, where ϕ ∈ Göd.
We set S0 (f) = S(0, f(0)) = f(0) and for n > 1 we define m, if m > 2
k , if k > 2 and m < 2
S(k, n, m) =

0 , otherwise.
By construction, Sn (f) is equal to the last value f(x) > 2 in (f(0), . . . , f(n)) and 0, if
no such value exists. Thus, the definition of the class U directly implies U ∈ IT ϕ (S).
It remains to show U ∈/ CONS. We need the observation that for every α ∈ N∗ ,there is an f ∈ U such that α v f. Indeed an implicit use of the fixed point theorem(cf., e.g., Smith [88]) yields that for every α ∈ N∗ and every p ∈ R{0,1} , there is aj > 2 such that ϕj = αjp.

Learning Recursive Functions

43

Now suppose that there is a strategy S ∈ P such that U ∈ CONSϕ (S). The
observation made directly implies S ∈ R and for every α ∈ N∗ , α v ϕS(α) . Thus, on
every α ∈ N∗ , S always computes a consistent hypothesis. Then, again by an implicit
use of the fixed point theorem, let j > 2 be any ϕ-program of the function f defined
as follows: f(0) = j, and for any n ∈ N,f(n + 1) =

0, if
1, if

S(fn 0) 6= S(fn )S(fn 0) = S(fn ) and S(fn 1) 6= S(fn ) .

In accordance with the observation made above and the assumption that S isconsistent, one immediately verifies that S(fn 0) 6= S(fn ) or S(fn 1) 6= S(fn ) for any
n ∈ N. Therefore the function f is everywhere defined and we have f ∈ U. On theother hand, the strategy S changes its mind infinitely often when successively fed f,
a contradiction to U ∈ CONSϕ (S).
As we have seen, learning in the limit is insensitive with respect to the requirement
to learn exclusively with recursive strategies (cf. Theorem 16). On the other hand,consistency is a common requirement in machine learning. Therefore, it is natural to
ask whether or not the power of consistent learning algorithms further decreases if
one restricts the notion of learning algorithms to the set of recursive strategies. The
answer to this question is provided by our next theorem.
Theorem 38 (Wiehagen and Zeugmann [104]).
T- CONS ⊂ R- CONS ⊂ CONS .
Proof. By definition we have T- CONS ⊆ R- CONS ⊆ CONS. Next we show thatUsd ∈ R- CONS \ T- CONS. Obviously, Usd ∈ R- CONSϕ (S) by the strategy S(fn ) =f(0) for all n ∈ N.
Now suppose that Usd ∈ T- CONS. Since U0 ∈ T- CONS and T- CONS is closed
under union (cf. Theorem 34), this would directly imply that U0 ∪ Usd ∈ T- CONS, acontradiction to Theorem 19. Thus T- CONS ⊂ R- CONS.
For the proof of CONS \ R- CONS 6= ∅ we use a class similar to the class above,
namely U = {f | f ∈ R, either ϕf(0) = f or ϕf(1) = f}. First we show that U ∈ CONS.
The desired strategy is defined as follows. Let f ∈ R and n ∈ N.
S(fn ) = “Compute in parallel ϕf(0) (x) and ϕf(1) (x) for all x 6 n until (A) or (B)happens.
(A) ϕf(0) (x) = f(x) for all x 6 n.
(B) ϕf(1) (x) = f(x) for all x 6 n.
If (A) happens first, then output f(0). If (B) happens first, then output f(1). If
neither (A) nor (B) happens, then S(fn ) is not defined.”

44

Thomas Zeugmann and Sandra Zilles

By the definition of U, it is obvious that S(fn ) is defined for all f ∈ U and all n ∈ N.
Moreover, S is clearly consistent. Hence, it suffices to prove that (S(fn ))n∈N converges
for all f ∈ U. But this is also an immediate consequence of the definition of U, sinceeither ϕf(0) 6= f or ϕf(1) 6= f. Hence S cannot oscillate infinitely often between f(0)and f(1). Consequently, U ∈ CONSϕ (S).
Next we show that U ∈/ R- CONS. Suppose there is a strategy S ∈ R such thatU ∈ R- CONSϕ (S). Applying Smullyan’s Recursion Theorem [91], we construct afunction f ∈ U such that either S(fn ) 6= S(fn+1 ) for all n ∈ N or ϕS(fx ) (y) 6= f(y)for some x, y ∈ N with y 6 x. Since both cases yield a contradiction to the definitionof R- CONS, we are done. The desired function f is defined as follows. Let h and s
be two recursive functions such that for all i, j ∈ N, ϕh(i,j) (0) = ϕs(i,j) (0) = i andϕh(i,j) (1) = ϕs(i,j) (1) = j. For any i, j ∈ N, x > 2 we proceed inductively.
Suspend the definition of ϕs(i,j) . Try to define ϕh(i,j) for more and more arguments
via the following procedure.
(T) Test whether or not (A) or (B) happens (this can be effectively checked, since
S ∈ R):(A) S(ϕxh(i,j) 0) 6= S(ϕxh(i,j) ),(B) S(ϕxh(i,j) 1) 6= S(ϕxh(i,j) ).
If (A) happens, then let ϕh(i,j) (x + 1) = 0, let x := x + 1, and goto (T).
In case (B) happens, set ϕh(i,j) (x + 1) = 1, let x := x + 1, and goto (T).
If neither (A) nor (B) happens, then define ϕh(i,j) (x 0 ) = 0 for all x 0 > x, andgoto (∗).
(∗) Set ϕs(i,j) (n) = ϕh(i,j) (n) for all n 6 x, and ϕs(i,j) (x 0 ) = 1 for all x 0 > x.
By Smullyan’s Recursion Theorem, there are numbers i and j such that ϕi = ϕh(i,j)
and ϕj = ϕs(i,j) . Now we distinguish the following cases.
Case 1. The loop in (T) is never left.
Then we directly obtain that ϕi ∈ U, since ϕj = ij is just a finite function while
ϕi ∈ R. Moreover, in accordance with the definition of the loop (T), on input ϕni thestrategy S changes its mind for all n > 0.
Case 2. The loop in (T) is left.
Then there exists an x such that S(ϕxh(i,j) 0) = S(ϕxh(i,j) 1). Hence S(ϕx+1
) =
i
x+1
S(ϕj ), since ϕh(i,j) = ϕi , ϕs(i,j) = ϕj , ϕi (n) = ϕj (n) for all n 6 x by (∗),
as well as ϕi (x + 1) = 0 and ϕj (x + 1) = 1. Furthermore, ϕi , ϕj ∈ R. Since
ϕi (x + 1) 6= ϕj (x + 1), we get ϕi 6= ϕj . On the other hand, ϕi (0) = i and ϕj (1) = j.
Consequently, both functions ϕi and ϕj belong to U. But S(ϕx+1) = S(ϕx+1
) and
i
j
x+1
ϕi (x + 1) 6= ϕj (x + 1), hence S does not work consistently on input ϕi or ϕx+1.
jThis contradiction completes the proof.

Learning Recursive Functions

45

Using the same classes as above one can show mutatis mutandis the following
theorem.
Theorem 39. T- CONSδ ⊂ R- CONSδ ⊂ CONSδ for all δ ∈ N.
The next result provides a more subtle insight into the difference in power between
T- CONS and R- CONS. Assertion (1) has been shown by Wiehagen and Liepe [102]and Assertion (2) has been proved in Wiehagen and Zeugmann [104].
Theorem 40.
(1) FIN # T- CONS
(2) FIN ⊂ R- CONS.
Proof. For proving Assertion (1) note that we obviously have Usd ∈ FIN. But
Usd ∈/ T- CONS (see the proof of Theorem 38), and thus FIN \ T- CONS 6= ∅. Furthermore, by Theorem 12 we have U(ϕ,Φ) ∈ T- CONS for every complexity measure(ϕ, Φ). It remains to argue that U(ϕ,Φ) ∈/ FIN. But this is obvious at least for complexity measures satisfying Property ext via Theorem 17. Thus, T- CONS \ FIN 6= ∅and Assertion (1) follows.
Next, we prove Assertion (2). Since T- CONS ⊆ R- CONS, R- CONS \ FIN 6= ∅ isan immediate consequence of (1). The proof of FIN ⊆ R- CONS mainly relies on thedecidability of the convergence of any finite learning algorithm. Let U ∈ FIN, and let
S be any strategy witnessing U ∈ FINϕ (S). Furthermore, let s ∈ R be any function
such that ϕs(α) = α0∞ for all α ∈ N∗ . The desired strategy Ŝ is defined as follows.
Let f ∈ R and n ∈ N. Then
Ŝ(fn ) = “In parallel, try to compute S(f0 ), . . . , S(fn ) for precisely n steps. Let k > 1
be the least number such that all values S(f0 ), . . . , S(fk ) turn out to be defined,
and S(fk−1 ) = S(fk ).
In case this k is found, output S(fk ). Otherwise, output s(fn ).”It remains to show that U ∈ R- CONS(Ŝ). Obviously, Ŝ ∈ R. Now let f ∈ U. We
have to show that Ŝ consistently learns f.
Claim 1. Ŝ learns f.
Since f ∈ U, the strategy S is defined for all inputs fn , n ∈ N. Moreover, since
S finitely learns f, the sequence (S(fn ))n∈N finitely converges to a ϕ–program of f.
Hence, Ŝ eventually has to find the least k such that S(fk−1 ) = S(fk ), and all values
S(f0 ), . . . , S(fk ) are defined. By the definition of FIN, ϕS(fk ) = f. Hence, Ŝ learns f.
Claim 2. For all f ∈ U and n ∈ N, Ŝ(fn ) is a consistent hypothesis.
As long as Ŝ outputs s(fn ), it is consistent. Suppose, Ŝ outputs S(fk ) for the firsttime. Then it has verified that S(fk−1 ) = S(fk ). Since f ∈ U, and U ∈ FINϕ (S), thisdirectly implies ϕS(fk ) = f. Therefore, Ŝ again outputs a consistent hypothesis. Since
this hypothesis is repeated in any subsequent learning step, the claim is shown.

46

Thomas Zeugmann and Sandra Zilles

Theorem 41. The following statements hold for all δ ∈ N:
(1) T- CONSδ ⊂ T- CONSδ+1 ⊂ T-REL,(2) NUM ∩ ℘(R{0,1} ) = T- CONSδ ∩ ℘(R{0,1} ) = T- CONSδ+1 ∩ ℘(R{0,1} ) = T-REL ∩℘(R{0,1} ),(3) T- CONSδ ∩ ℘(R{0,1} ) ⊂ R-REL ∩ ℘(R{0,1} ).
Proof. We first prove Assertion (1). Let δ ∈ N be arbitrarily fixed. Then by
Definition 15 we obviously have T- CONSδ ⊆ T- CONSδ+1 . For showing T- CONSδ+1 \T- CONSδ 6= ∅ we use the following class. Let (ϕ, Φ) be any complexity measure; we
set
(ϕ,Φ)
Uδ+1 = {f | f ∈ R, ϕf(0) = f, ∀x[Φf(0) (x) 6 f(x + δ + 1)]} .
(ϕ,Φ)

Claim 1. Uδ+1

∈ T- CONSδ+1 .

The desired strategy S is defined as follows. Let g ∈ R be the function defined in
the sufficiency proof of Theorem 32. For all f ∈ R and all n ∈ N we set

S(fn ) = f(0),


if n 6 δ or n > δ and Φf(0) (y) 6 f(y + δ + 1)
. δ−
. 1
and ϕf(0) (y) = f(y) for all y 6 n −otherwise.

g(fn ),(ϕ,Φ)

Now, by construction, one easily verifies Uδ+1
Claim 1.
(ϕ,Φ)

Claim 2. Uδ+1

∈ T- CONSδ+1 (S). This proves∈/ T- CONSδ .
(ϕ,Φ)

Suppose the converse. Then there must be a strategy S ∈ R such that Uδ+1 ∈(ϕ,Φ)
T- CONSδ (S). We continue by constructing a function ϕi∗ ∈ Uδ+1 on which S fails.
Furthermore, let r ∈ R be such that Φi = ϕr(i) for all i ∈ N and r is strongly
monotonously increasing, i.e., r(i) < r(i + 1) for all i ∈ N. Then Val(r) is recursive(cf. Rogers [86]). Choose s ∈ R such that for all j ∈ N and for all x 6 δ we haveϕs(j) (x) =i,0,if there is an i with r(i) = j
otherwise.

For the further definition of ϕs(j) we also use δ + 1 arguments in every step. For
x = 0, δ + 1, 2δ + 2, 3δ + 3, . . . we set
ϕs(j) (x + δ + 1) = ϕj (x) + 1···
ϕs(j) (x + 2δ + 1) = ϕj (x + δ) + 1

Learning Recursive Functions

47

provided ϕj (x), ϕj (x + 1), . . . , ϕj (x + δ) are all defined, ϕx+δs(j) is defined and
S ϕx+δ
= S h(ϕs(j) (0), . . . , ϕs(j) (x + δ), ϕj (x), . . . , ϕj (x + δ))is(j)and
ϕs(j) (x + δ + 1) = ϕj (x)···ϕs(j) (x + 2δ + 1) = ϕj (x + δ)provided ϕj (x), ϕj (x + 1), . . . , ϕj (x + δ) are all defined, ϕx+δs(j) is defined and
S



ϕx+δ
s(j)




6= S h(ϕs(j) (0), . . . , ϕs(j) (x + δ), ϕj (x), . . . , ϕj (x + δ))i .

Otherwise, ϕs(j) (x + δ + 1), . . . , ϕs(j) (x + 2δ + 1) remain undefined.
By the fixed point theorem (cf. Rogers [86]) there exists a number i∗ such thatϕs(r(i∗ )) = ϕi∗ .
(ϕ,Φ)

Next, we show that ϕi∗ ∈ Uδ+1 . This is done inductively. For the induction base,by construction we have ϕi∗ (0) = · · · = ϕi∗ (δ) = i∗ . Hence, Φi∗ (0), . . . , Φi∗ (δ) are all
defined, too. Therefore, we know that ϕδs(r(i∗ )) is defined and so either ϕs(r(i∗ )) (δ +1) = Φi∗ (0) + 1, . . . , ϕs(r(i∗ )) (2δ + 1) = Φi∗ (δ) + 1 provided
S ϕδs(r(i∗ )) = S h(ϕs((r(i∗ )) (0), . . . , ϕs((r(i∗ )) (δ), Φi∗ (0), . . . , Φi∗ (δ))ior ϕs(r(i∗ )) (δ + 1) = Φi∗ (0), . . . , ϕs(r(i∗ )) (2δ + 1) = Φi∗ (δ) ifS ϕδs(r(i∗ )) 6= S h(ϕs((r(i∗ )) (0), . . . , ϕs((r(i∗ )) (δ), Φi∗ (0), . . . , Φi∗ (δ))i .
Note that one of these cases must happen, since otherwise S would not be T-consistent
with δ–delay.
Hence, Φi∗ (0) 6 ϕi∗ (δ + 1), . . . , Φi∗ (δ) 6 ϕi∗ (2δ + 1), since ϕs(r(i∗ )) = ϕi∗ . So weknow that ϕi∗ (δ + 1), . . . , ϕi∗ (2δ + 1) as well as Φi∗ (δ + 1), . . . , Φi∗ (2δ + 1) are all
defined. This completes the induction base.
Consequently, we have the induction hypothesis that for some x = 0, δ + 1, 2δ +2, 3δ + 3, . . . the values ϕi∗ (z) are defined and Φi∗ (z) 6 ϕi∗ (z + δ + 1) for allz 6 x + δ. This of course implies ϕx+δs(r(i∗ )) is defined, too. The induction step is done
from x to x + δ + 1. First, we either have ϕs(r(i∗ )) (x + δ + 1) = Φi∗ (x) + 1, . . . ,ϕs(r(i∗ )) (x + 2δ + 1) = Φi∗ (x + δ) + 1 provided



x+δ
S ϕs(r(i= S h(ϕs(r(i∗ )) (0), . . . , ϕs(r(i∗ )) (x + δ), Φi∗ (x), . . . , Φi∗ (x + δ))i
∗ ))

48

Thomas Zeugmann and Sandra Zilles

or ϕs(r(i∗ )) (x + δ + 1) = Φi∗ (x), . . . , ϕs(r(i∗ )) (x + 2δ + 1) = Φi∗ (x + δ) if



x+δ
S ϕs(r(i∗ )) 6= S h(ϕs(r(i∗ )) (0), . . . , ϕs(r(i∗ )) (x + δ), Φi∗ (x), . . . , Φi∗ (x + δ))i .
Note that one of these cases must happen, since otherwise S would not be T-consistent
with δ–delay.
Therefore, ϕi∗ (x + δ + 1), . . . , ϕi∗ (x + 2δ + 1) are all defined andΦi∗ (x) 6 ϕi∗ (x + δ + 1), . . . , Φi∗ (x + δ) 6 ϕi∗ (x + 2δ + 1) .
Now we also know that Φi∗ (x + δ + 1), . . . , Φi∗ (x + 2δ + 1) are all defined. Thus,(ϕ,Φ)
we have shown that ϕi∗ ∈ Uδ+1 . Finally, by construction we directly obtain that S
performs infinitely many mind changes when successively fed ϕi∗ , a contradiction to(ϕ,Φ)
Uδ+1 ∈ T- CONSδ (S). This proves Claim 2.
Taking into account that, for any f ∈ R, a strategy working T-consistently with
δ–delay converges when successively fed f iff it learns f, we directly get T- CONSδ ⊆T-REL for every δ ∈ N. Now T- CONSδ ⊂ T- CONSδ+1 ⊆ T-REL for all δ ∈ N implies
T- CONSδ ⊂ T-REL for all δ ∈ N. This proves Assertion (1).
For Assertion (2) we only have to show T-REL ∩ ℘(R{0,1} ) ⊆ NUM ∩ ℘(R{0,1} ). For
that purpose let U ∈ T-REL ∩ ℘(R{0,1} ). By Theorem 35 there is a general recursive
operator O such that U ⊆ RO , that means
U ⊆ {ϕi | ∀∞ x[Φi (x) 6 O(ϕi , x)]} ∩ R{0,1} .
As each general recursive operator, O can be bounded by a monotone general recursive
operator Ô, i.e., O(f, x) 6 Ô(f, x) for all f ∈ R and all x ∈ N, where monotonicity ofÔ means that ∀∞ x[Ô(f, x) 6 Ô(g, x)] for all f, g ∈ R satisfying ∀∞ x[f(x) 6 g(x)].
In particular, for any ϕi ∈ U ⊆ R{0,1} we have ∀x[ϕi (x) 6 1] and therefore∀ x[O(ϕi , x) 6 Ô(1∞ , x)]. Consequently∞U ⊆ {ϕi | ∀∞ x[Φi (x) 6 Ô(1∞ , x)]} ∩ R{0,1} .
Since Ô is general recursive, the function t defined by t(x) = Ô(1∞ , x) for all x isrecursive. Applying Theorem 4 we can conclude U ∈ NUM, and Assertion (2) isshown.
Finally, Assertion (3) is an immediate consequence of Assertion (2) and Theorems
2 and 3 from Stephan and Zeugmann [94] which together show that Umahp ∈ R-REL\
NUM. Consequently, since Umahp ⊆ R{0,1} we have NUM ∩ ℘(R{0,1} ) ⊂ R-REL ∩℘(R{0,1} ). This completes the proof.
In particular, we have seen that Umahp ∈ R-REL and thus located the appropriate
learning model for inferring all functions in Umahp . Does this result also extend tothe class Uahp ? Interestingly, now the answer depends on the underlying complexity

49

Learning Recursive Functions

measure. As shown in Stephan and Zeugmann [94], there are “natural” complexity measures such that Uahp ∈/ BC. On the other hand, there are also complexity
measures such that Uahp ∈ LIM.
Together with Theorem 34 the proof of Theorem 41 allows for a nice corollary.
Corollary 42. For all δ ∈ N we have:(1) CONSδ ⊂ CONSδ+1 ,(2) R- CONSδ ⊂ R- CONSδ+1 .
(ϕ,Φ)

Proof. We use Uδ+1 from the proof of Theorem 41 and the class U0 . Clearly,
(ϕ,Φ)
(ϕ,Φ)
Uδ+1 , U0 ∈ T- CONSδ+1 and therefore, by Theorem 34 we also have Uδ+1 ∪ U0 ∈
(ϕ,Φ)
(ϕ,Φ)
T- CONSδ+1 . Consequently, Uδ+1 ∪ U0 ∈ R- CONSδ+1 and Uδ+1 ∪ U0 ∈ CONSδ+1 .
(ϕ,Φ)
It remains to argue that Uδ+1 ∪ U0 ∈/ CONSδ . This will suffice, since R- CONSδ ⊆CONSδ .
(ϕ,Φ)

Suppose the converse, i.e., there is a strategy S ∈ P such that Uδ+1 ∪ U0 ∈CONSδ (S). By the choice of U0 we can then directly conclude that S ∈ R and that S
has to work consistently with δ–delay on every fn , where f ∈ R and n ∈ N. But this
(ϕ,Φ)
(ϕ,Φ)
would imply Uδ+1 ∪ U0 ∈ T- CONSδ (S), a contradiction to Uδ+1 ∈/ T- CONSδ .
A closer look at the proof above shows that we have even proved the following
corollary shedding some light on the power of our notion of δ–delay.
Corollary 43. T- CONSδ+1 \ CONSδ 6= ∅ for all δ ∈ N.
The situation is comparable to Lange and Zeugmann’s [68] bounded example memory learnability BEM k of languages from positive data, where BEM k yields an infiniteShierarchy such that k∈N BEM k is a proper subclass of the class of all indexed familiesof recursive languages that can be conservatively learned.
On the one hand, Corollary 42 shows the strength of δ–delay. On the other hand,the δ–delay cannot compensate all the learning power that is provided by the different
consistency demands on the domain of the strategies.
Theorem 44. R- CONS \ T- CONSδ 6= ∅ for all δ ∈ N.
Proof. The proof can be done by using the class Usd of self-describing functions.
Obviously, Usd ∈ R- CONS(S) as witnessed by the strategy S(fn ) = f(0) for all f ∈ R
and all n ∈ N. Now assuming Usd ∈ T- CONSδ for some δ ∈ N would directly imply
that Usd ∪ U0 ∈ T- CONSδ for the same δ by Theorem 34. But this is a contradiction
to Usd ∪ U0 ∈/ BC (see Theorem 19).
Finally, combining Corollary 43 and Theorem 44, we get the following incomparabilities.
Corollary 45. T- CONSδ # CONSµ and T- CONSδ # R- CONSµ for all δ, µ ∈ Nprovided δ > µ.

50Thomas Zeugmann and Sandra Zilles

T- COH⊂

T- COH1

T- CONS ⊂ T- CONS1∩∩
R- COH ⊂ R- COH1

⊂ ··· ⊂

T- COHδ⊂ · · · ⊂ T- CONSδ
∩⊂ · · · ⊂ R- COHδ

T- COHδ+1⊂ · · · ⊂ T-REL⊂ T- CONSδ+1∩⊂ R- COHδ+1⊂ · · · ⊂ T-REL∩⊂ · · · # R-REL⊂

R- CONS ⊂ R- CONS1 ⊂ · · · ⊂ R- CONSδ ⊂ R- CONSδ+1 ⊂ · · · # R-REL
∩
∩
∩
∩
∩
COH
⊂
COH1
⊂ ··· ⊂COHδ⊂
COHδ+1⊂ · · · ⊂ LIM
CONS

⊂

CONS1

⊂ ··· ⊂CONSδ⊂CONSδ+1⊂ ··· ⊂

LIM

Figure 2: Hierarchies of consistent learning with δ-delay
Figure 2 below summarizes the achieved separations and equivalences of the various
coherent and consistent learning models investigated in this paper.
Another interesting relaxation of the consistency demand has been proposed by
Wiehagen [99] – he called it conformity.
Definition 22 (Wiehagen [99]). Let U ⊆ R, and let ψ ∈ P2 . The class U iscalled conformly learnable in the limit with respect to ψ if there is a strategy S ∈ Psuch that(1) U ∈ LIMψ (S),(2) [either ψS(fn ) (x) ↑ or ψS(fn ) (x) = f(x)] for all f ∈ U, all n ∈ N and all x 6 n.
CONFψ (S), CONFψ and CONF are defined analogously to the above.
Now one can prove the following theorem in which the second proper inclusion
intuitively seems to be the more surprising one.
Theorem 46 (Wiehagen [99]). CONS ⊂ CONF ⊂ LIM
Proof. Clearly, we have CONS ⊆ CONF ⊆ LIM. For showing LIM \ CONF 6= ∅only one new idea is needed. We use the class from the proof of Theorem 37, i.e.,
U = {f ∈ R | f = αjp, α ∈ N∗ , j > 2, p ∈ R{0,1} , ϕj = f}. Suppose U ∈ CONFϕ (S).
Then we directly get S ∈ R. Using the fixed point theorem we obtain a number jwhich is a ϕ-program of the following function f.
f(0) = j ,

 0,
1,
f(n + 1) =
1,

if S(fn ) 6= S(fn 0)
if S(fn ) = S(fn 0) and S(fn ) 6= S(fn 1) ,if S(fn ) = S(fn 0) = S(fn 1) .

By construction we obtain f ∈ U. Since S is supposed to be conform, if the caseS(fn ) = S(fn 0) = S(fn 1) occurs, we see that ϕS(fn 1) (n + 1) must diverge. Consequently, ϕS(fn 1) (n + 1) 6= f. Hence, the sequence (S(fn ))n∈N contains infinitely many

Learning Recursive Functions

51

mind changes or infinitely many wrong hypotheses. Since f ∈ U we get a contradiction
to U ∈ CONFϕ (S), and thus CONF ⊂ LIM must hold.
For the remaining part CONF \ CONS 6= ∅ we refer the reader to [99].
The second inclusion in the theorem above seems to be of great interest for thephilosophy of science: it says that, when learning in the limit, strategies using conjectures which convergently contradict known data may have a strictly greater inference
power than strategies whose conjectures never contradict known data convergently.

8. Characterizations in Terms of Computable Numberings
In this survey, we have already seen several characterizations of learning types interms of computable numberings. We started with the characterization of R- TOTAL(see Theorem 2), then presented a characterization for TOTAL (see Theorem 10), andprovided also a characterization of T- CONSarb in terms of measurable numberings(see Theorem 12). So far all these characterizations showed that for each learning
type LT considered and each class U ∈ LT there is a non-Gödel numbering ψ suchthat U is learnable in the sense of LT with respect to ψ by an enumerative inference
strategy.
The technical difficulty we have to overcome is provided by Lemma 3 below. For
every class U ∈/ NUM there are only hypothesis spaces ψ such that U ⊆ Pψ implies
the undecidability of the halting problem with respect to ψ.
Lemma 3 (Wiehagen and Zeugmann [103]). Let U ⊆ R and let U ∈/ NUM.
2
Then, for any numbering ψ ∈ P satisfying U ⊆ Pψ , the halting problem with respectto ψ is undecidable.
Proof. Let U ⊆ R and U ∈/ NUM. Furthermore, let ψ ∈ P2 be any numbering suchthat U ⊆ Pψ . Suppose the halting problem with respect to ψ is decidable. So there
exists a function h ∈ R2 such that for all i, x ∈ N, h(i, x) = 1 iff ψi (x) is defined.
Then define a numbering ψ̃ by effectively filling out the “gaps” in ψ as follows:ψ̃i (x) =ψi (x) , if h(i, x) = 1
0 , otherwise

Obviously, for any i ∈ N, if ψi ∈ R then ψ̃i = ψi . Hence U ⊆ Pψ̃ . However, ψ̃ ∈ R2
and consequently, U ⊆ Pψ̃ implies U ∈ NUM, a contradiction.
So, it is only natural to ask whether or not we can show an analogous result for every
learning type. What we would like to present in this chapter is substantial evidence for
an affirmative answer. Besides its epistemological importance, these characterizations
will also provide a deeper insight into the problem what kind of properties “inferencefriendly” non-Gödel numberings ψ should have in order to make Rψ learnable.
One idea may be derived from the proof of R ∈ CONS+ (cf. Theorem 29, Assertion (2)). Here the additional information allowed for restricting the hypothesis

52

Thomas Zeugmann and Sandra Zilles

search to a finite subspace of ϕ. If we can limiting recursively compute such additional
information, then we can use essentially the same proof technique. Note that this idea
goes back to Barzdin and Podnieks [18].
Theorem 47 (Wiehagen [99]). Let U ⊆ R, then we have:(1) U ∈ LIM if and only if there exists a limiting recursive functional B such thatU ⊆ dom(B) and B(f) > minϕ f for all f ∈ U.
(2) U ∈ CONS if and only if there exists a function B ∈ P such that for every f ∈ U
the following conditions are satisfied:(A) There is a j > minϕ f with B(fn ) = j for all but finitely many n ∈ N.
(B) B(fn ) is defined for every n ∈ N and there is an i 6 B(fn ) such that
ϕi =n f.
In the second version we cannot restrict the hypothesis search to a finite subspaceof ϕ. Instead, the classes to learn can be embedded into a computable numbering ψsuch that for computing the actual hypothesis quite often only finitely many elementsof the computable numbering ψ have to be considered. Note that we have alreadyprovided a theorem that uses precisely this idea, i.e., the characterization of TOTAL(cf. Theorem 10). Using similar ideas Wiehagen [99] could show the following theorem.
Theorem 48 (Wiehagen [99]). Let U ⊆ R, then we have:(1) U ∈ LIM if and only if there exists a numbering ψ ∈ P2 such that the following
conditions are satisfied:(A) U ⊆ Pψ(B) There is a function g ∈ R such that for every function f ∈ U the set of allnumbers i with ψi =g(i) f is finite.
(2) U ∈ BC if and only if there exists a numbering ψ ∈ P2 such that the following
conditions are satisfied:(A) U ⊆ Pψ(B) There is a function r ∈ R such that for every function f ∈ U and almost
all i, ψi =r(i) f implies ψi = f.
Proof. We only prove Assertion (2) here, since Assertion (1) can be shown mutatis
mutandis as Theorem 10.
In order to show the necessity part of (2) let U ∈ BCϕ (S), where, without loss ofgenerality, S ∈ R (cf. Theorem 22). We define M to be the set of all pairs (z, n) suchthat
• for all x 6 n, ϕz (x) is defined, andLearning Recursive Functions

53• S(ϕnz ) = z.
Let M be enumerated without repetitions by d ∈ R. For i, x ∈ N, d(i) = (z, n), we
define ψ(i, x) = ϕz (x) and r(i) = n.
U ⊆ Pψ is obvious. Let f ∈ U and let n̂ be such that ϕS(fn ) = f for all n > n̂.
Then ψi =r(i) f and r(i) > n̂ implies ψi = f. Since there are only finitely many
numbers i such that ψi =r(i) f and r(i) < n̂, Condition (B) follows.
For showing the sufficiency part of (2) we have to define a strategy S such that U ∈BCϕ (S). Let amal be the amalgamation function defined in the proof of Theorem 29.
Furthermore, let c ∈ R be a compiler function such that ψi = ϕc(i) for all i ∈ N. For
any input fn we define the set
M(fn ) = {i | i ∈ N, i 6 n, r(i) 6 n∧ ∀x[x 6 r(i) → Φc(i) (x) 6 n ∧ ψi =r(i) f]∧ ∀x[n > x > r(i) ∧ Φc(i) (x) 6 n → ψi (x) = f(x)]} ,where r ∈ R is the function from Condition (B). Clearly, M(fn ) is finite and computable for every fn . Again, we choose g ∈ R such that ϕg(hαi) (x) = yx for every
tuple α ∈ N∗ , α = (y0 , . . . , yn ) and all x 6 n.
We define the strategy S as follows. If M(fn ) = ∅ then we set S(fn ) = g(fn ). If
M(fn ) 6= ∅, we set S(fn ) = amal({c(i) | i ∈ M(fn )}).
It remains to show that S learns every function f ∈ U behaviorally correctly.
By construction and Condition (B) we know that for almost all n the set M(fn )contains only ψ-programs i such that ψi ⊆ f. For sufficiently large n, we also know
by Condition (A) that M(fn ) contains at least one ψ-program i such that ψi = f.
Consequently, for all sufficiently large n, S(fn ) is a ϕ-program for f, and thus U ∈BCϕ (S). Note that S outputs infinitely many different ϕ-programs for f if there areinfinitely many ψ-programs for f.
The third version of characterizations in terms of computable numberings showsthat learnable functions classes are embeddable into numberings ψ possessing someeffective distinguishability property. Informally, ψ has an effective distinguishability
property if there is an effective method to distinguish ψi and ψj for every i, j provided
ψi 6= ψj .
The following characterization is due to Wiehagen [100].
Theorem 49 (Wiehagen [99, 100]). Let U ⊆ R, then we have: U ∈ LIM if
and only if there exists a numbering ψ ∈ P2 such that
(1) U ⊆ Pψ , and(2) there is a function d ∈ R2 such that ψi 6=d(i,j) ψj for all i, j ∈ N with i 6= j.

54Thomas Zeugmann and Sandra Zilles

Proof. Necessity. Let U ∈ LIM; then there exists a numbering ϕ ∈ P2 and astrategy S ∈ P such that U ∈ LIMϕ (S).
Let M denote the set of all pairs (z, n) such that• for all x 6 n, ϕz (x) is defined, and• S(ϕn−1) 6= S(ϕnzz ) = z.
Intuitively, M corresponds to the set of all initial segments ϕnz on which after an−1n(perhaps last) mind change (namely S(ϕz ) 6= S(ϕz )) the strategy S outputs areasonable hypothesis.
Clearly, M is recursively enumerable. Let M be enumerated by e ∈ R without
repetition. Now we are ready to define the desired numbering ψ. For any i such thate(i) = (z, n), we set:ϕz (x),
if x 6 n
ϕz (x),
if x > n and for every y with n < y 6 x,
ψi (x) =ϕz (y) is defined and S(ϕyz ) = z
undefined,
otherwise.
Next, let g ∈ R be chosen such that g(i) = n for every i with e(i) = (z, n). We defined(i, j) = max{g(i), g(j)}.
It remains to show that Conditions (1) and (2) are satisfied.
Claim 1. U ⊆ Pψ .
Let f ∈ U; we have to show that there is an i such that ψi = f. Since f ∈ U, there
exists a least n such that S(fn ) = S(fn+m ) = z for all m ∈ N. Then (z, n) ∈ M andsince S has converged and since U ∈ LIMϕ (S), we also have ψi = f. Thus, Claim 1
is shown.
Claim 2. ψi 6=d(i,j) ψj for all i, j ∈ N with i 6= j.
Let i 6= j and suppose that ψi =d(i,j) ψj . Without loss of generality we can assumeg(i) < g(j). By the definition of M it follows that ψj (x) is defined for all x 6 g(j)and thus ψi (x) is defined for all x 6 g(j), too. By the definition of ψ we obtaing(j)−1g(j)that S(ψi) = S(ψi ). On the other hand, by the definition of M we get thatg(j)−1g(j)S(ψj) 6= S(ψj ). But this is a contradiction to ψi =d(i,j) ψj . Thus, Claim 2 isproved and the necessity part of the theorem follows.
Sufficiency. We define the desired strategy as follows.
S(f0 ) = 0
S(fn ) = “Compute i = S(fn−1 ). Check within at most n steps of computation
whether or not there is a j > i such that d(i, j) 6 n and ψi =d(i,j) f. Ifsuch a j is found, output i + 1.
Otherwise output i.”Learning Recursive Functions

55

We have to show that U ∈ LIMψ (S). Let f ∈ U, let n ∈ N+ and let i = S(fn−1 ).
Suppose there is a j > i such that d(i, j) 6 n and ψi =d(i,j) f. Then, by Condition(2), we know that ψj 6=d(i,j) ψi . Consequently, ψi 6= f. Thus, choosing a new
hypothesis is justified. Moreover, this observation also shows that the strategy S will
never abandon a correct hypothesis i.
So, it remains to show that i is abandoned if ψi 6= f. Fix any i with ψi 6= f. Then,by Condition (1), there is a j > i (namely ψj = f) such that d(i, j) 6 n, for n large
enough, and ψj =d(i,j) f. Thus, j will be eventually found and the strategy is forced
to change the provably wrong hypothesis i to i + 1.
Putting it all together, we get that for every f ∈ U the strategy S converges to theminimal (and only!) ψ–number of f. This shows U ∈ LIMψ (S).
This theorem nicely shows that requiring a learning strategy to exclusively output
programs for recursive functions is by no means the only way to realize Popper’s [84]refutability principle. Instead, Theorem 49 leads to the crucial notion of semantic
finiteness. Intuitively, a semantically finite strategy is never allowed to reject a hypothesis that is correct for the target function. Hence, when learning semanticallyfinitely, a strategy should have a serious reason to reject its current hypothesis. As theproof of Theorem 49 shows, this reason might be quite different from just detecting
an inconsistency.
Next, we turn our attention to finite learning. As we have already seen, no class
U ∈ FIN can contain an accumulation point (cf. Theorem 17). A closer look at thisobservation leads to the following characterization of FIN.
Theorem 50 (Wiehagen [98, 100]). Let U ⊆ R, then we have: U ∈ FIN if andonly if there exists a numbering ψ ∈ P2 such that
(1) U ⊆ Pψ , and(2) there is a function d ∈ R such that ψi 6=d(i) ψj for all i, j ∈ N with i 6= j.
Proof. Necessity. Let U ∈ FIN; then there exists a numbering ϕ ∈ P2 and astrategy S ∈ P such that U ∈ FINϕ (S).
Let M denote the set of all pairs (z, n) such that• for all x 6 n, ϕz (x) is defined,• for all 0 < x < n, S(ϕx−1) 6= S(ϕxz ), andz• S(ϕn−1) = S(ϕnzz ) = z.
Let M be enumerated by e ∈ R without repetition. For any i such that e(i) = (z, n)
we define:ψi = ϕz and d(i) = n .

56Thomas Zeugmann and Sandra Zilles

Clearly, ψ ∈ P2 and d ∈ R. It remains to show that Conditions (1) and (2) aresatisfied.
Claim 1. U ⊆ Pψ .
Let f ∈ U; we know that {f} ∈ FINϕ (S). Thus, there exists an n ∈ N such that
S(fx−1 ) 6= S(fx ) for all 0 < x < n and S(fn−1 ) = S(fn ) = z. By the definition of finite
convergence, we can conclude that (S(fn ))n∈N has converged and since {f} ∈ FINϕ (S),we know that ϕz = f. Thus, (z, n) ∈ M and by construction there is an i such thate(i) = (z, n). Hence, ψi = ϕz = f. This proves Claim 1.
Claim 2. ψi 6=d(i) ψj for all i, j ∈ N with i 6= j.
Let i 6= j and suppose ψi =d(i) ψj . Let e(i) = (z, n); by the definition of d we canconclude ψi (x) ↓ for all x = 0, . . . , n. Additionally, by the definition of the relation=m we also have that ψj (x) ↓ for all x = 0, . . . , n. Now let e(j) = (ẑ, n̂). Since i 6= j
and since e enumerates M without repetition, it must hold z 6= ẑ or n 6= n̂.
n
By construction, S(ψni ) = z and since ψi =d(i) ψj , we also have S(ψj ) = z. Thus,z 6= ẑ cannot happen. But n 6= n̂ cannot happen either, since n is the least number
such that S(ψn−1) = S(ψni ). Thus i = j, a contradiction.
iClaim 1 and 2 together yield the necessity part.
Sufficiency. The desired strategy S is defined as follows. Let f ∈ U and let n ∈ N.
We set:S(fn ) = “Check whether there is an i ∈ N such that• i 6 n,• d(i) 6 n,
• ψi =d(i) f can be verified within n steps of computation.
If such an i is found, let S(fn ) = i.
Otherwise, let S(fn ) = n.”
Let f ∈ U; then Condition (1) ensures that there is at least one ψ-program i such that
ψi =d(i) f. Furthermore, Condition (2) guarantees that there is at most one such ψprogram. Since n increases, this ψ-program i will be found eventually. Consequently,
U ∈ FINψ (S) and thus U ∈ FIN.
Next, we characterize the different versions of consistent learning in terms of computable numberings. As we shall see, the difference between the different versions ofconsistent learning can be completely expressed by different versions of consistencyrelated decision problems. Therefore, following Wiehagen and Zeugmann [104], next
we define these consistency-related decision problems.
Definition 23. Let ψ ∈ P2 be any numbering and let U ⊆ R. We say that
(1) consistency with respect to ψ is decidable if there is a predicate cons ∈ R2 suchthat for each α ∈ N∗ and all i ∈ N, cons(hαi, i) = 1 if and only if α v ψi .

Learning Recursive Functions

57(2) U–consistency with respect to ψ is decidable if there is a predicate cons ∈P2 such that for each α ∈ [U] and all i ∈ N, cons(hαi, i) is defined, andcons(hαi, i) = 1 if and only if α v ψi .
(3) U–consistency with respect to ψ is R–decidable if there is a predicate cons ∈ R2
such that for each α ∈ [U] and all i ∈ N, cons(hαi, i) = 1 if and only if α v ψi .
Note that the following proof uses ideas from Wiehagen [98] as well as from [104].
Theorem 51. U ∈ T- CONS iff there is a numbering ψ ∈ P2 such that
(1) U ⊆ Pψ ,(2) consistency with respect to ψ is decidable.
Proof. Necessity. Let U ∈ T- CONSϕ (S) where ϕ ∈ P2 is any Gödel numberingand S is a T–consistent strategy. Let
M = {(z, n) | z, n ∈ N, ϕz (x) is defined for every x 6 n, S(ϕnz ) = z}be recursively enumerated by a function e. Then define a numbering ψ as follows.
Let i, x ∈ N, e(i) = (z, n).
ϕz (x),
ϕz (x),
ψi (x) =
↑,

if x 6 n
if x > n and, for any y ∈ N such that n < y 6 x,
ϕz (y) is defined and S(ϕyz ) = z
otherwise.

For showing (1) let f ∈ U and n, z ∈ N be such that S(fm ) = z for any m > n.
Clearly, ϕz = f. Furthermore, (z, n) ∈ M. Let i ∈ N be such that e(i) = (z, n).
Then, by definition of ψ, ψi = ϕz = f. Hence U ⊆ Pψ .
In order to prove (2) we define cons ∈ R2 such that for any α ∈ N∗ , i ∈ N,
cons(hαi, i) = 1 iff α v ψi . Let α = (α0 , . . . , αx ) ∈ N∗ and i ∈ N. Let e(i) = (z, n).
Then define
1, if x 6 n and, for every y 6 x, αy = ψi (y)1, if x > n and S(hα0 , . . . , αy i) = z for every y ∈ Ncons(hαi, i) =such that n < y 6 x
0, otherwise.
Since e(i) = (z, n) ∈ M, by construction we know that ϕz (m) ↓ for all m 6 n
and S(ϕnz ) = z. Thus, we have ψi (m) = ϕz (m) for all m 6 n. Consequently, if
x 6 n, then for all y 6 x it can be effectively tested whether or not αy = ψi (y).
Furthermore, S ∈ R implies that S(hα0 , . . . , αy i) can be computed for every y ∈ Nsuch that n < y 6 x. Thus, if x > n, the condition S(hα0 , . . . , αy i) = z can beeffectively checked for every y ∈ N such that n < y 6 x. Consequently, cons ∈ R2 .

58

Thomas Zeugmann and Sandra Zilles

Furthermore, it is not hard to see that for every α ∈ N∗ , i ∈ N, we havecons(hαi, i) = 1 iff α v ψi . This proves the necessity part.
Sufficiency. Let ψ ∈ P2 be any numbering. Let cons ∈ R2 be such that for allα ∈ N∗ and i ∈ N we have cons(α, i) = 1 iff α v ψi . Let U ⊆ Pψ . In order toconsistently learn any function f ∈ U it suffices to define S(fn ) = min{i | cons(fn , i)}.
However, S is undefined if, for f ∈/ U, n ∈ N, there is no i ∈ N such that fn v ψi . The
following more careful definition of S will circumvent this difficulty. Let ϕ ∈ Göd.
Let aux ∈ R be such that for any α ∈ N∗ , ϕaux (ff ) = α0∞ . Finally, let c ∈ R be suchthat for all i ∈ N, ψi = ϕc(i) . Then, for any f ∈ R, n ∈ N, define a strategy S as
follows.

S(fn ) =c(j),if I = {i | i 6 n, cons(fn , i) = 1} 6= ∅ and j = min Inaux (f ), if I = ∅.

Clearly, S ∈ R and S outputs only consistent hypotheses. Now let f ∈ U. Then,obviously, (S(fn ))n∈N converges to c(min{i | ψi = f}). Hence, the strategy S witnesses
U ∈ T- CONSϕ .
Next, we present our characterization for CONS.
Theorem 52. U ∈ CONS iff there is a numbering ψ ∈ P2 such that
(1) U ⊆ Pψ ,(2) U–consistency with respect to ψ is decidable.
Finally, we characterize R- CONS.
Theorem 53. U ∈ R- CONS iff there is a numbering ψ ∈ P2 such that
(1) U ⊆ Pψ ,(2) U–consistency with respect to ψ is R–decidable.
The proofs of Theorems 52 and 53 are similar to that of Theorem 51.
The above characterizations of T- CONS, CONS and R- CONS as well as the characterization of T- CONSarb provided in Theorem 12 point out a relation between the
problem of deciding consistency and the halting problem. On the one hand, for anyof the learning types LT ∈ {T- CONS, CONS, R- CONS,
T- CONSarb } we have NUM ⊆ LT (via Theorem 2 and Corollary 13). On the other
hand, as shown in Lemma 3, for any class U ⊆ R outside NUM and any numberingψ ∈ P2 , if U ⊆ Pψ , then the halting problem with respect to ψ is undecidable.
In contrast, for any U ∈ LT \ NUM the corresponding version of consistency withrespect to ψ is decidable. Hence this version of consistency cannot be decided by first
deciding the halting problem and second, if possible, computing the desired values ofLearning Recursive Functions

59

the function under consideration in order to compare these values with the given ones.
So, though consistency is decidable in the “characteristic” numberings of Theorems 51,
52, 53 and 12 it is not decidable in a “straightforward way.”

9. Further Topics
In this section we briefly summarize further research pursued by Rolf Wiehagenand his co-workers. We start with robust inference.
9.1. Robust Learning
For the sake of motivation, let us look at any class U in R- TOTAL. Recalling that
R- TOTAL = NUM we can think of U as (a subset of) a family (ϕs(i) )i∈N for somes ∈ R (cf. Theorem 2). Furthermore, let O be any effective operator realized by afunction g ∈ R such that O(U) ⊆ R (cf. Definition 20). Then we have O(ϕs(i) ) =ϕg(s(i)) for every i ∈ N and thus the family (ϕg(s(i)) )i∈N also belongs to NUM andis consequently in R- TOTAL, again by Theorem 2.
Thus, every class U in R- TOTAL has the remarkable property that not only theclass U itself is learnable but all classes obtained from U by effective transformations
are R- TOTAL-learnable, too. This property may serve as a first informal definitionof what is meant by saying that a class is robustly learnable.
For discussing the importance of robust learnability, it is helpful to recall that wehave separated several learning types by using some class of self-describing functions,for example Usd . On the one hand, this is an elegant proof method and, as pointed
out by Jain, Smith and Wiehagen [57], self-description is quite a natural phenomenon
in that every cell of every organism contains a description of itself. On the other
hand, such separating classes may seem a bit artificial, since they use coding tricks.
So for the positive part of the separation, a learner only needs to fetch some codefrom the input. For the non-learnability result one usually shows that at least one
function in the separating class is too complex to gain the information necessary tolearn it in the more restricted model. If such self-describing function classes were theonly separating examples, then we would have to draw major consequences for our
overall understanding of learning and for the value of the theory developed so far.
Around thirty years ago, Bārzdiņš suggested to prove or to disprove the following
conjecture.
Let U ⊆ R; then O(U) ∈ LIM for all effective operators O with O(U) ⊆ R implies
that there is a ψ ∈ R2 such that U ⊆ Rψ .
An affirmative answer to Bārzdiņš’ conjecture could be interpreted as follows. Every function class U in LIM \ NUM contains only functions having encoded a certain
information in their graphs which is helpful in the learning process. Intuitively, thisinformation is then erased by some operator O and thus O(U) ∈/ LIM.

60

Thomas Zeugmann and Sandra Zilles

However, it took many years before any progress concerning Bārzdiņš’ conjecture
has been made. Zeugmann [108] proposed to generalize Bārzdiņš’ conjecture by replacing LIM by any learning type LT and showed it to be true for FIN and T-REL.
Then Kurtz and Smith [64, 65] disproved Bārzdiņš’ conjecture for classes U ∈ NUM.
The major breakthrough has been made by Fulk [44] who also coined the term ofrobust learnability. Let LT be any learning type. Then we call a class U robustly
LT -learnable, iff, for every operator O, the class O(U) is LT -learnable.
There were many discussions about which operators O are admissible in this context. Fulk [44] considered the class of all general recursive operators and for thisversion he disproved Bārzdiņš’ conjecture for LIM. Subsequently, many interesting
results have been obtained in this context (cf., e.g., [4, 25, 53, 57, 80, 94]).
We would like to mention here only some of the results obtained. For this purpose
we use LT -robust to denote the family of all classes U ⊆ R such that O(U) ∈ LT for
every general recursive operator O.
As we have seen in Theorem 21, there is an infinite anomaly hierarchy for LIMtype learning and also for BC-type identification (cf. Case and Smith [27]). Thesehierarchies do not stand robustly.
Theorem 54 (Fulk [44]).
(1) LIMa -robust = LIM-robust for all a ∈ N ∪ {∗}.
(2) BCa -robust = BC-robust for all a ∈ N ∪ {∗}.
Let us denote by LIMn the family of all classes U ⊆ R which can be learned in
the limit with at most n mind changes. Then it is not hard to prove that LIMn ⊂LIMn+1 for every n ∈ N (cf. [27]).
Interestingly, this mind change hierarchy does stand robustly as the following theorem shows. Note that the proof uses a complicated priority argument.
Theorem 55 (Jain, Smith and Wiehagen [57]).
LIMn -robust ⊂ LIMn+1 -robust for all n ∈ N.
In [57] it was also shown that the LIMteam (n) and BCteam (n) hierarchies standrobustly.
A more detailed study on which learning types contain rich robustly learnableclasses has been carried out by Case et al. [26] and the reader is encouraged to consult
this paper for many deep and interesting results. As a final example, we mention thefollowing. Adding a uniformity condition (see also Subsection 9.4) in [26] it could be
proved that LIM-uniform-robust ⊆ CONS. This for sure sheds additional light on
the importance of consistent learning.
Before closing this subsection, let us again take a look at our five classes from
Section 3. Since U0 ∈ NUM, it is robustly learnable. Usd is not robustly learnable,
since for O(f) = g, where g(x) = f(x + 1) we have O(Usd ) = R. Likewise, in general

Learning Recursive Functions

61

the class U(ϕ,Φ) is not in LIM-robust. This can be seen by using Theorem 2.4 andCorollary 2.6 in [80]. As far as Umahp and Uahp are concerned, now the answer
depends for both classes on the underlying complexity measure. There are complexity
measures such that Umahp , Uahp ∈ LIM-robust (cf. Theorem 16 and Corollary 17
in [94]). Furthermore, there are “natural” complexity measures such that Umahp ∈/LIM-robust (cf. Theorem 19 in [94]).
Next, we turn our attention to learning from good examples, motivated partly by
the intuitive thought that humans can learn more efficiently from well-chosen (good)
examples than they can from arbitrary input.
9.2. Assisting the Learner
The most natural way to help a learner – at least when thinking of the way humans
learn – would be to emphasize particularly representative or helpful examples during
the learning process and maybe not to present unhelpful examples at all. In particular,thus one could think of learning from only finitely many examples instead of learningfrom a whole infinite sequence of examples representing a target function. On a formal
level, this requires a notion of what helpful examples, called good examples, are, andhow they should be utilized in learning.
In this context, Freivalds, Kinber, and Wiehagen [41] have introduced two modelsof learning from good examples, one in the context of finite learning, one in the context
of learning in the limit.
Definition 24 (Freivalds et. al. [41]). Let U ⊆ R and let ψ ∈ P2 . The class U
is said to be• finitely learnable from good examples with respect to ψ if there is a numberingex ∈ P2 , a strategy S ∈ P, and a function z ∈ P such that U ⊆ Pψ and, for anyi ∈ N with ψi ∈ U,(1) exi is a finite subfunction of ψi and z(i) = |{x | ψi (x) ↓ }|,(2) ψS(ex ∪ε) = ψi for any finite subfunction ε of ψi .
• learnable in the limit from good examples with respect to ψ if there is a numbering ex ∈ P2 , a strategy S ∈ P2 , and a function z ∈ P such that U ⊆ Pψ and,for any i ∈ N with ψi ∈ U,(1) exi is a finite subfunction of ψi and z(i) = |{x | ψi (x) ↓ }|,(2) for any finite subfunction ε of ψi , there is some j with ψj = ψi andS(ex ∪ ε, n) = j for all but finitely many n ∈ N.
The resulting learning types are defined in the usual way and denoted by GEX-FIN
and GEX-LIM, respectively.

62

Thomas Zeugmann and Sandra Zilles

Interestingly, GEX-FIN coincides with the standard inference type of behaviorally
correct learning, i.e., the classes learnable finitely from good examples can be characterized as exactly those which are learnable behaviorally correctly.
Theorem 56 (Freivalds et. al. [41]). GEX-FIN = BC
So, accessing good examples, learning strategies can, even within finite learning
processes, achieve more than ordinary strategies can in the limit. This theorem naturally raises the question whether or not GEX-LIM is richer than GEX-FIN. The
affirmative answer is provided by the following theorem. When learning from good
examples in the limit, the whole class of all recursive functions can be identified.
Theorem 57 (Freivalds et. al. [41]). R ∈ GEX-LIM
For the proofs of Theorems 56 and 57 as well as for further results, we refer thereader to [41].
The paradigm of learning from good examples has received further interest in
research meanwhile; the reader is referred to Nessel [76] for further results on learning
recursive functions. Additionally, this framework has been discussed for learning
recursive languages as well; here the reader is directed to the survey by Lange etal. [69]. It has also attracted interest in other branches of learning theory, see e.g.,
Ling [72].
9.3. Complexity of Learning Problems
So far we have discussed many different learning models derived from Gold’s [48]
initial one, compared these to one another, and illustrated their strengths and limitations with several examples of learnable or non-learnable classes, respectively. However, we still do not have a deeper insight into what makes some classes harder tolearn than others. Characterization theorems provide necessary and sufficient conditions for learnability, but in case two classes are learnable, can we say anything about
which of the two is the more challenging learning problem?
To deal with this question, Freivalds et al. [39] have introduced a notion of intrinsic
complexity of learning. The idea was to define an appropriate notion of reducibility,
inspired by results from recursion theory and complexity theory where similar approaches have been successfully applied.
The notion of reducibility defined is based on the usage of recursive operators, i.e.,
partial recursive operators that are defined on every partial function.
Definition 25 (Rogers [86]). A partial recursive operator O : P 7→ P is called arecursive operator if dom(O) = P.
We continue with the reduction principle. Given two classes U1 and U2 of recursivefunctions a reduction from U1 to U2 involves two recursive operators. The first one
translates any function in U1 into a function in U2 . The second operator converts
any successful hypothesis sequence for the obtained function in U2 into a successful

Learning Recursive Functions

63

hypothesis sequence for the original function in U1 . Here the term successful hypothesis
sequence is used to refer to the notion of admissible sequences defined as follows.
Definition 26 (Freivalds et al. [39]). Let f ∈ R. An infinite sequence σ iscalled LIM-admissible for f if σ converges to a ϕ-program for f.
This finally allows us to define the desired reducibility relation.
Definition 27 (Freivalds et al. [39], Kinber et al. [60], Jain et al. [54]).
Let U1 , U2 ∈ LIM. U1 is called LIM-reducible to U2 if there exist recursive operators
Θ and Ξ such that each function f ∈ U1 satisfies the following two conditions:(1) Θ(f) ∈ U2 ,(2) if σ is a LIM-admissible sequence for Θ(f), then Ξ(σ) is a LIM-admissible
sequence for f.
In the sequel we omit the prefix LIM, since we consider the notion of reducibility
here only in the context of learning in the limit; however, this definition has also been
adapted and analyzed for other inference types.
Now the idea for reductions is as follows: if U1 is reducible to U2 , then a strategy
identifying all functions in U1 can be computed from any strategy which is successful
for U2 . For instance, each class in LIM is reducible to the class U0 of functions offinite support (cf. Theorem 58). Thus U0 is a class in LIM of highest complexity
respecting the notion of reducibility. Such classes are said to be LIM-complete.
Definition 28 (Freivalds et al. [39], Kinber et al. [60], Jain et al. [54]). Let
U ⊆ R. U is LIM-complete if U ∈ LIM and every class U0 ∈ LIM is LIM-reducible
to U.
Theorem 58 (Freivalds et. al. [39]). U0 is LIM-complete.
Note that U0 is an r.e. class and every initial segment of any function f ∈ U0 is an
initial segment of infinitely many other functions f0 ∈ U0 . This property has turned
out to be crucial when trying to characterize the hardest problem sets in learning in
the limit (with respect to the proposed complexity notion). This is reflected in thefollowing characterization theorem for complete classes.
Theorem 59 (Kinber et al. [60], Jain et al. [54]). Let U ∈ LIM. U is
LIM-complete, iff there is some ψ ∈ R2 such that
(1) Pψ ⊆ U,(2) for all i, n ∈ N there are infinitely many j ∈ N satisfying ψi =n ψj and ψi 6= ψj .
That means that complete classes are characterized by being topologically complicated (in terms of the second condition demanding density with respect to theso-called Baire metric, see Rogers [86] for details) and containing an algorithmicallyrather “simple” – since uniformly r.e. – set (in terms of the first condition).

64

Thomas Zeugmann and Sandra Zilles

9.4. Uniformity of Learning Problems
Throughout this survey, we have very often – sometimes implicitly – encounteredcases in which different classes of recursive functions can be learned with very similar
strategies, or – more specifically – in which different learning problems are solved witha uniform method.
For instance, all classes in NUM can be learned with Gold’s identification by
enumeration strategy [48] (cf. the proof of Theorem 2). This strategy is uniform inthe sense that it only needs access to the numbering ψ ∈ R2 comprising the classof target functions to be learned. Numerous other impressive examples of strategies
working uniformly for a huge collection of learning problems have been obtained in
the characterization theorems discussed above. Note that in each of these theorems,
the sufficiency part of the proof deploys a uniform strategy specific for the inference
type that is being characterized.
In contrast to that, most of the learning types studied so far have the property
that their corresponding collections of learnable function classes are not closed underunion. For instance, the proof of Theorem 19 shows that, although both Usd and U0
are learnable in the limit, their union is not even BC-learnable. In particular, bothclasses can be learned in the limit with two different instances of the same uniform
method (different special strategies derived from a kind of meta-strategy), but there
is no way of designing an instance of that uniform method, which can cope with allfunctions contained in any of the two classes.
Intuitively, each special strategy for a special class of functions is designed using
some prior knowledge about the target class (e.g., the identification by enumeration
strategy for a class in NUM knows a numbering ψ ∈ R2 comprising the target class)which can be seen as a restriction of the space of possible hypotheses and thus arestriction of the search space. Now, if the union of two such learnable classes is nolonger learnable, this means that there is no means of successfully exploiting the priorknowledge that a function is contained in one of these classes.
Hence there may be ways of describing prior knowledge about certain learnableclasses such that this prior knowledge can be exploited by a meta-strategy in order toinstantiate strategies tailored for the corresponding target classes. The circumstances
under which such meta-strategies exist have been the focus of a branch of researchconcerning so-called uniform learning.
Any formalization of this approach requires a notion of how to describe target
classes of recursive functions (i.e., means of describing prior knowledge about a target
class) as well as a notion of the desired learning behavior of meta-strategies.
A straightforward scheme for describing classes of recursive functions is the following: Consider a fixed three-place Gödel numbering τ. For any d ∈ N, the numbering
τd is just the two-place function resulting from τ, if the first input is fixed by d1 . Thus
1

Note that throughout this subsection, for any d, i ∈ N, we actually denote the function

Learning Recursive Functions

65

d corresponds to the set Pτd = {τdi | i ∈ N} of partial recursive functions enumeratedby τd and may simply serve as a description of the class Rτd = {τdi | i ∈ N} ∩ R
of recursive functions, which is also called the recursive core of the numbering τd .
In particular, each set D = {d0 , d1 , d2 , . . .} ⊆ N can be regarded as a set of descriptions and thus as a collection of the “learning problems” Rτd0 , Rτd1 , Rτd2 , . . . In thiscontext, such a set D is simply called a description set.
Now a meta-strategy is a strategy expecting two inputs: first, a parameter d ∈ Ninterpreted as a description of some recursive core, and second, a coding fn of an initial
segment of some recursive function f. If S is a meta-strategy and d any description,then Sd denotes the strategy resulting from S, when the first input is fixed by d.
Given a learning type LT as studied above, a meta-strategy S is a successful uniform
strategy for D, in case Sd learns Rτd for all d ∈ D according to the constraints of LT .
More formally:
Definition 29 (Zilles [110], Jantke [58]). Let LT be a learning type and D ⊆ N
a description set. Let ϕ be a Gödel numbering. D is uniformly LT -learnable (withrespect to ϕ) if there is a meta-strategy S, such that, for any d ∈ D, the strategy Sd
is an LT -learner for the class Rτd with respect to ϕ. UNI-LT denotes the class of all
uniformly LT -learnable description sets.2
Lemma 2 justifies the choice of a fixed Gödel numbering ϕ as a hypothesis space
beforehand; the reader may easily verify that this definition of learnability is independent of the choice of ϕ. However, this is not the only suggestive notion of hypothesis
spaces in uniform learning. Note that each numbering τd enumerates at least all functions in Rτd , so a meta-strategy might also be designed for using τd as a hypothesis
space when learning Rτd . This results in a special case of Definition 29, because τd programs can be uniformly translated into programs in a fixed Gödel numbering ϕ.
We refer to this model as description-uniform learning.
Definition 30 (Zilles [110], Jantke [58]). Let LT be a learning type and D ⊆ N
a description set. D is description-uniformly LT -learnable, iff there is a meta-strategy
S, such that, for any d ∈ D, the strategy Sd is an LT -learner for the class Rτd withrespect to τd . UNIdes -LT denotes the class of all description sets which are descriptionuniformly LT -learnable.
Uniform learning has been studied for numerous learning types, especially in comparison of different learning types to one another, cf. Zilles [112, 111]; however, forthe sake of brevity, we restrict the following survey to the inference types LIM and
BC. Note that most of the results hold analogously for many other learning types.
The following theorem states that description-uniform learning is a proper restrictionof uniform learning.
λx.τ(d, i, x) by τdi . Here the superscript d does not mean we consider a coding of an initial segmentof any function. However, the intended meaning will always be clear from context.
2
Note that, by intuition, it seems adequate to refer to uniformly learnable collections of recursive
cores represented by description sets, rather than to uniformly learnable description sets themselves.
Yet, for convenience, the latter notion is preferred.

66

Thomas Zeugmann and Sandra Zilles

Theorem 60 (Zilles [112]).
UNIdes -LIM ⊂ UNI-LIM and UNIdes -BC ⊂ UNI-BC.
But what are the general limitations of uniform learning? It turns out that there
are “maximally powerful” meta-strategies: with a suitable choice of descriptions all
non-uniformly learnable classes of functions can be learned uniformly.
Theorem 61 (Zilles [112], Jantke [58]). Let LT ∈ {LIM, BC}. Then there
exists a description set D ⊆ N, such that(1) for all U ∈ LT there is some d ∈ D satisfying U ⊆ Rτd ;(2) D ∈ UNI-LT .
In contrast to this, depending on the choice of the descriptions, even sets describing
the most simple recursive cores can be non-learnable. This concerns descriptions ofrecursive cores each consisting of just one function or even, in the description-uniform
model, descriptions for just a single recursive core consisting of just one function. Thisis a significant difference compared to non-uniform learning, because there arbitrary
finite classes are trivially learnable.
Theorem 62 (Zilles [112]).
(1) Let D = {d ∈ N | |Rτd | = 1} be the set of all descriptions representing singleton
recursive cores. Then D ∈/ UNI-BC.
(2) Fix any recursive function r and let D = {d ∈ N | Rτd = {r}} be the set of all
descriptions representing the recursive core {r}. Then D ∈/ UNIdes -BC.
Theorems 61 and 62 show how much the choice of descriptions affects uniform
learnability. In a slightly more subtle way this is expressed in the following twotheorems, which moreover show that the hierarchy of learning types in non-uniform
learning is reflected in the uniform framework.
Theorem 63 (Zilles [112]). UNI-LIM ⊂ UNI-BC. In particular, there is a
D ⊆ N satisfying(1) |Rτd | = 1 for all d ∈ D,
(2) D ∈ UNI-BC \ UNI-LIM.
Theorem 64 (Zilles [112]). UNIdes -LIM ⊂ UNIdes -BC. In particular, for any
r ∈ R, there is a D ⊆ N satisfying(1) Rτd = {r} for all d ∈ D,
(2) D ∈ UNIdes -BC \ UNIdes -LIM.

Learning Recursive Functions

67

Now many of the results obtained in the non-uniform framework of learning canbe lifted to the meta-level of uniform and description-uniform learning. We will pick
two aspects for illustration: (i) characterizations of learning types as in Section 8 and(ii) intrinsic complexity as in Subsection 9.3. From now on, however, we shall focus
exclusively on the learning type LIM.
Most of the characterizations shown above have their immediate counterpart inthe context of uniform learning, such as the following characterizations derived from
Theorem 49. However, it should be noted that characterizations for descriptionuniform learning always require some additional “embedding” property (like Property(3) in Theorem 66 below). The proofs can be easily lifted from the non-uniform case.
Theorem 65 (Zilles [111]). Let D ⊆ N. D ∈ UNI-LIM, if and only if there isa three-place partial recursive numbering χ and a recursive function h, such that for
all d ∈ D the following conditions are fulfilled.
(1) Rτd ⊆ Pχd ,(2) χdi 6=h(d,i,j) χdj for all i, j ∈ N with i 6= j.
Theorem 66 (Zilles [111]). Let D ⊆ N. D ∈ UNIdes -LIM, if and only ifthere is a three-place partial recursive numbering χ, a recursive function h, as well
as a recursive function e ∈ R2 , such that for all d ∈ D the following conditions are
fulfilled.
(1) Rτd ⊆ Pχd ,(2) χdi 6=h(d,i,j) χdj for all i, j ∈ N with i 6= j,(3) τde(d,i) = χdi for all i such that χdi ∈ R.
In order to lift the intrinsic complexity approach to uniform learning, first appropriate notions of admissible sequences and of reducibility need to be defined – again distinguishing between uniform learning (the UNI-LIM-model) and description-uniform
learning (the UNIdes -LIM-model). For that purpose, from now on, let ϕ denote a
fixed Gödel numbering.
Definition 31 (Zilles [113]). Let d ∈ N be any description and let f ∈ Rτd . An
infinite sequence σ of natural numbers is called• UNI-LIM-admissible for d and f if σ converges to a ϕ-program for f;• UNIdes -LIM-admissible for d and f if σ converges to a τd -program for f.
Since the recursive operators needed now have to take the descriptions d ∈ N of thetarget classes into account, actually a new notion of recursive operators is required.
Definition 32 (Zilles [113]). Let Θ be a total function mapping pairs of functions
to pairs of functions. Θ is called a recursive meta-operator if the following properties
are satisfied for all functions δ, δ 0 and f, f 0 and all numbers n, y ∈ N:

68

Thomas Zeugmann and Sandra Zilles(1) if δ ⊆ δ 0 , f ⊆ f 0 , as well as Θ(δ, f) = (γ, g) and Θ(δ 0 , f 0 ) = (γ 0 , g 0 ), then γ ⊆ γ 0
and g ⊆ g 0 ;(2) if Θ(δ, f) = (γ, g) and γ(n) = y (or g(n) = y, respectively), then there exist
initial subfunctions δ0 ⊆ δ and f0 ⊆ f such that (γ0 , g0 ) = Θ(δ0 , f0 ) fulfills
γ0 (n) = y (g0 (n) = y, respectively);(3) if δ and f are finite and Θ(δ, f) = (γ, g), then one can effectively (in (δ, f))enumerate γ and g.
This finally enables us to define the following formalization of reducibility in uniform and description-uniform learning.
Definition 33 (Zilles [113]). Let D1 , D2 ∈ UNI-LIM. We say that D1 is
UNI-LIM-reducible to D2 if there is a recursive meta-operator Θ and a recursive
operator Ξ, such that the following holds. For any description d1 ∈ D1 , any function
f1 ∈ Rd1 , and any δ1 ∈ N∗ there is a δ2 ∈ N∗ and a function f2 satisfying:(1) Θ(δ1 d∞
1 , f1 ) = (δ2 , f2 ),(2) δ2 converges to a description d2 ∈ D2 such that f2 ∈ Rd2 ,(3) if σ is a UNI-LIM-admissible sequence for d2 and f2 , then Ξ(σ) is UNI-LIMadmissible for d1 and f1 .
Moreover, if D1 , D2 ∈ UNIdes -LIM, then the definition of UNIdes -LIM-reducibility
is obtained by replacing UNI-LIM by UNIdes -LIM above as well as replacing Condition (3) by Condition (30 ): if σ is a UNIdes -LIM-admissible sequence for d2 and f2 ,then Ξ(d2 σ) is UNIdes -LIM-admissible for d1 and f1 .
As in the non-uniform framework, these reducibility notions immediately yieldcompleteness notions, obtained in the straightforward way.
Definition 34 (Zilles [113]). Let D ⊆ N.
(1) D is UNI-LIM-complete if D ∈ UNI-LIM and every set D0 ∈ UNI-LIM is
UNI-LIM-reducible to D.
(2) D is UNIdes -LIM-complete if D ∈ UNIdes -LIM and every set D0 ∈ UNIdes -LIM
is UNIdes -LIM-reducible to D.
For illustration consider the following two examples taken from [113]:
g(i)

g(i)

Assume a recursive function g, given any i, x ∈ N, fulfills τ0 = ϕi and τx
x > 0. Then the description set {g(i) | i ∈ N} is UNI-LIM-complete.
h(i)

h(i)

↑ , if

Let r, h ∈ R. Assume τi= r for all i, as well as ϕx ↑ for any i, x ∈ N withx 6= i. Then the description set {h(i) | i ∈ N} is UNIdes -LIM-complete, but not
UNI-LIM-complete.

Learning Recursive Functions

69

Finally, as in the non-uniform case, we obtain characterizations of UNI-LIMcomplete description sets as well as of UNIdes -LIM-complete description sets.
Theorem 67 (Zilles [113]). Let D ∈ UNI-LIM. D is UNI-LIM-complete, if
and only if there is a ψ ∈ R2 and a limiting r.e. family (di )i∈N of descriptions in D,such that the following conditions are fulfilled:(1) ψi ∈ Rdi for all i ∈ N;(2) every function in Pψ is an accumulation point of Pψ .
Theorem 68 (Zilles [113]). Let D ∈ UNIdes -LIM. D is UNIdes -LIM-complete,
if and only if there is a ψ ∈ R2 and a limiting r.e. family (di )i∈N of descriptions in D,such that the following conditions are fulfilled:(1) ψi ∈ Rdi for all i ∈ N;(2) for each i, n ∈ N there are infinitely many j ∈ N satisfying ψi =n ψj and(di , ψi ) 6= (dj , ψj ).
How closely the results on intrinsic complexity of uniform learning are related to theresults in the non-uniform framework, as presented in the previous section, is shownin an alternative formulation of Theorem 67, which holds analogously if Property (2)is replaced by the following property: (20 ) Pψ is LIM-complete.

10. Summary and Conclusions
Inductive inference of recursive functions has attracted much attention during thepast four decades. As we have seen, the theory has been developed to a large extent
and many interesting results have been obtained. These results in turn deepen our
principal understanding of inference processes and have many implications for thephilosophy of science, for cognition, and of course for learning in general (cf. [79, 55]).
For example, the prediction model (see Definition 4) originating in inductive inference of recursive functions has been adapted in several branches of learning theory. A
prominent example is Littlestone’s [73] on-line prediction model which is also known as
the mistake-bound learning model and which in turn has nice relations to PAC learning (cf. Haussler et al. [51]). In this context we mention here again the Algorithm FP
from the proof of Theorem 6.
Furthermore, we have investigated consistent learning versus inconsistent learning,observing a general inconsistency phenomenon: In spite of the remarkable power ofconsistent learning it turns out that this power is not universal. There are learning
problems which can exclusively be solved by inconsistent strategies, i.e., by strategies
that do temporarily incorrectly reflect the behavior of the unknown object on data forwhich the correct behavior of the object is already known. Moreover, the necessity of70Thomas Zeugmann and Sandra Zilles

inconsistent strategies, working in a somewhat unintuitive way, has been traced backto the undecidability of consistency.
If consistent learning is possible, then the corresponding consistency problem must
be decidable with respect to some suitably chosen numbering. Further results showthat the inconsistency phenomenon is also valid in more realistic situations. Wiehagen
and Zeugmann [104] considered a domain where consistency is decidable and thelearning strategies have to work in polynomial time, observing that certain learning
problems can be solved efficiently, but not efficiently by any consistent strategy (unless
P = NP). The reason is quite analogous to that in the setting of learning recursivefunctions. Now the NP-hardness of problems can prevent learning strategies fromproducing consistent hypotheses in polynomial time.
The characterizations of learning types in terms of computable numberings also
provide deeper insight concerning the way in which learning strategies can actually
perform the inference process in a uniform manner. The first and very powerful
method in this regard is Gold’s [48] “identification by enumeration.” Though themethods provided in the sufficiency proofs of the characterizations theorems in termsof computable numberings have their peculiarities, they all have a rather strong resemblance to “identification by enumeration.” This has been further investigated by
Kurtz et al. [66], where the authors concluded with the thesis that enumeration techniques are even universal in that each solvable learning problem in inductive inference
can be solved by an adequate enumeration technique. This insight is of fundamental
epistemological importance.
On the other hand, these methods do not yield efficient practical algorithms. In
general the size of the space that must be searched is typically exponential in thelength of the description of the first correct hypothesis.
Looking at the characterizations in terms of complexity, we see that the results obtained also have nice implications for the theory of computational complexity. For illustration, let us recall that there is no function h ∈ R2 such that Φi (x) 6 h(x, ϕi (x))
for all i ∈ N with ϕi ∈ R and almost all x ∈ N (cf., e.g., [88]). Using Theorem 35
we can directly generalize this to the statement that there is no effective Operator O
such that Φi (x) 6 O(ϕi , x) for all i ∈ N with ϕi ∈ R and almost all x ∈ N.
Furthermore, Theorems 35 and 36 together solve the problem of characterizing
the operator honest functions. Similar results can be obtained by combining further
characterizations (cf. [106]).
Additionally, the characterizations in terms of complexity also show that every
function to be learned possesses a recursively computable upper bound for its complexity. In turn, the additional knowledge of such an upper bound does not only
guarantee the learnability of the considered functions but also the synthesis of a program with a complexity not greater than the given upper bound almost everywhere.
Let us finish this survey with the remark that the field of learning recursive functions is large but the discourse here is brief. Although several topics could not beLearning Recursive Functions

71

touched at all, the material selected for this survey hopefully provides a good overview
and guides the reader to other, more specialized sources of information.

References[1] L. M. Adleman and M. Blum. Inductive inference and unsolvability. The Journalof Symbolic Logic, 56(3):891–900, 1991.
[2] Y. Akama and T. Zeugmann. Consistency conditions for inductive inferenceof recursive functions. In New Frontiers in Artificial Intelligence, JSAI 2006
Conference and Workshops, Tokyo, Japan, June 2006, Revised Selected Papers,
volume 4384 of Lecture Notes in Artificial Intelligence, pages 251–264, Berlin,
2007. Springer.
[3] A. Ambainis. Probabilistic inductive inference: a survey. Theoret. Comput. Sci.,
264(1):155–167, 2001.
[4] A. Ambainis and R. Freivalds. Transformations that preserve learnability. In
Algorithmic Learning Theory, 7th International Workshop, ALT ’96, Sydney,
Australia, October 1996, Proceedings, volume 1160 of Lecture Notes in Artificial
Intelligence, pages 299–311. Springer, 1996.
[5] D. Angluin and C. H. Smith. A survey of inductive inference: Theory andmethods. ACM Comput. Surv., 15(3):237–269, 1983.
[6] D. Angluin and C. H. Smith. Inductive inference. In Encyclopedia of Artificial
Intelligence, pages 409–418. J. Wiley and Sons, New York, 1987.
[7] K. Apsı̄tis, R. Freivalds, R. Simanovskis, and J. Smotrovs. Closedness properties
in ex-identification. Theoret. Comput. Sci., 268(2):367–393, 2001.
[8] K. Apsı̄tis, R. Freivalds, and C. Smith. Choosing a learning team: a topologicalapproach. In Proc. of Twenty-sixth ACM Symposium on Theory of Computing,
1994.
[9] J. M. Barzdin. Prognostication of automata and functions. In C. V. Freiman,
J. E. Griffith, and J. L. Rosenfeld, editors, Information Processing 71, Proceedings of IFIP Congress 71, Volume 1 - Foundations and Systems, Ljubljana,
Yugoslavia, August 23-28, 1971, pages 81–84. North-Holland, 1972.
[10] J. M. Barzdin. Inductive inference of automata, functions and programs.
In Proc. of the 20-th International Congress of Mathematicians, Vancouver,
Canada, pages 455–460, 1974. (republished in Amer. Math. Soc. Transl. (2)109, 1977, pages 107- 112).

72

Thomas Zeugmann and Sandra Zilles[11] J. M. Barzdin, editor. Teori Algoritmov i Programm, volume I. Latvian
State University, 1974.
[12] J. M. Barzdin, editor. Teori Algoritmov i Programm, volume II. Latvian
State University, 1975.
[13] J. M. Barzdin, editor. Teori Algoritmov i Programm, volume III. Latvian
State University, 1977.
[14] J. M. Barzdin and R. V. Freivald. On the prediction of general recursive functions. Soviet Math. Dokl., 13:1224–1228, 1972.
[15] . M. Barzdin~. Slonost~ i qastotnoe rexenie nekotoryh algoritmiqeski nerazreximyh massovyh problem. Dokt. dissertaci,Novosibirsk, 1971.
[16] . M. Barzdin~. Dve teoremy o predel~nom sinteze funkci$
i. In J. M.
Barzdin, editor, Teori Algoritmov i Programm, volume I, pages 82–88.
Latvian State University, 1974.
[17] . M. Barzdin~ and R. V. Fre$
ivald. Prognozirovanie i predel~ny$isintez effektivno pereqislimyh klassov funkci$
i. In J. M. Barzdin,
editor, Teori Algoritmov i Programm, volume I, pages 101–111. Latvian
State University, 1974.
[18] . M. Barzdin~ and K. M. Podnieks. 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., pages 9–15. Mathematical Institute of the Slovak Academy of Sciences,
1973.
[19] L. Blum and M. Blum. Toward a mathematical theory of inductive inference.
Inform. Control, 28(2):125–155, June 1975.
[20] M. Blum. A machine independent theory of the complexity of recursive functions. Journal of the ACM, 14(2):322–336, 1967.
[21] R. Board and L. Pitt. On the necessity of Occam algorithms. Theoret. Comput.
Sci., 100(1):157–184, 1992.
[22] A. Borodin. Computational complexity and the existence of complexity gaps.
Journal of the ACM, 19(1):158–174, 1972.
[23] U. Brandt. The position of index sets of identifiable sets in the arithmeticalhierarchy. Inform. Control, 68(1-3):185–195, 1986.
[24] J. Case, S. Jain, S. Lange, and T. Zeugmann. Incremental concept learning forbounded data mining. Inform. Comput., 152(1):74–110, 1999.

Learning Recursive Functions

73[25] J. Case, S. Jain, M. Ott, A. Sharma, and F. Stephan. Robust learning aided bycontext. J. Comput. Syst. Sci., 60(2):234–257, 2000.
[26] J. Case, S. Jain, F. Stephan, and R. Wiehagen. Robust learning – rich andpoor. J. Comput. Syst. Sci., 69(2):123–165, 2004.
[27] J. Case and C. Smith. Comparison of identification criteria for machine inductive
inference. Theoret. Comput. Sci., 25(2):193–220, 1983.
[28] R. L. Constable. The operator gap. Journal of the ACM, 19(1):175–183, 1972.
[29] R. P. Daley. On the error correcting power of pluralism in BC-type inductive
inference. Theoret. Comput. Sci., 24(1):95–104, 1983.
[30] R. P. Daley. Towards the development of an analysis of learning algorithms. In
Analogical and Inductive Inference, International Workshop AII ’86. WendischRietz, GDR, October 1986, Proceedings, volume 265 of Lecture Notes in Computer Science, pages 1–18. Springer-Verlag, 1986.
[31] J. Feldman. Some decidability results on grammatical inference and complexity.
Inform. Control, 20(3):244–262, 1972.
[32] R. V. Freivald and R. Wiehagen. Inductive inference with additional information. Elektronische Informationsverarbeitung und Kybernetik, 15(4):179–185,
1979.
[33] R. V. Fre$
ivald. Predel~no vyqislimye funkcii i funkcionaly. In
J. M. Barzdin, editor, Teori Algoritmov i Programm, volume I, pages
6–19. Latvian State University, 1974.
[34] R. V. Fre$
ivald and . M. Barzdin~. Sootnoxeni medu prognoziruemost~ i predel~no$i sinteziruemost~. In J. M. Barzdin, editor, Teori Algoritmov i Programm, volume II, pages 26 – 34. Latvian State University, 1975.
[35] R. Freivalds. An answer to an open problem. Bulletin of the EATCS, 23:31–32,
1984.
[36] R. Freivalds. Inductive inference of minimal programs. In Proceedings of theThird Annual Workshop on Computational Learning Theory, pages 3–20, San
Mateo, CA, 1990. Morgan Kaufmann.
[37] R. Freivalds, J. Bārzdiņš, and K. Podnieks. Inductive inference of recursivefunctions: Complexity bounds. In Baltic Computer Science, volume 502 of
Lecture Notes in Computer Science, pages 111–155. Springer-Verlag, Berlin,
1991.

74

Thomas Zeugmann and Sandra Zilles[38] R. Freivalds, O. Botuscharov, and R. Wiehagen. Identifying nearly minimalGödel numbers from additional information. Annals of Mathematics and Artificial Intelligence, 23(1/2):199–209, 1998.
[39] R. Freivalds, E. Kinber, and C. H. Smith. On the intrinsic complexity of learning. Inform. Comput., 123(1):64–71, 1995.
[40] R. Freivalds, E. B. Kinber, and R. Wiehagen. Probabilistic versus deterministic
inductive inference in nonstandard numberings. Zeitschr. f. math. Logik undGrundlagen d. Math., 34:531–539, 1988.
[41] R. Freivalds, E. B. Kinber, and R. Wiehagen. On the power of inductive inference from good examples. Theoret. Comput. Sci., 110(1):131–144, 1993.
[42] R. Freivalds, C. H. Smith, and M. Velauthapillai. Trade-off among parameters
affecting inductive inference. Inform. Comput., 82:323–349, 1989.
[43] R. V. Freivalds. Finite identification of general recursive functions by probabilistic strategies. In Fundamentals of Computations Theory, FCT’ 79, Proc. of theConference on Algebraic, Arithmetic, and Categorial Methods in Computation
Theory, pages 138–145, Berlin, 1979. Akademie-Verlag.
[44] M. A. Fulk. Robust separations in inductive inference. In Proc. of the 31st
Annual Symposium on Foundations of Computer Science, pages 405–410. IEEE
Computer Society Press, Los Alamitos, CA, 1990.
[45] W. Gasarch and C. H. Smith. A survey of inductive inference with an emphasis
on queries. In Complexity, Logic, and Recursion Theory. Marcel Dekker, Inc.,
1997.
[46] W. I. Gasarch, R. K. Sitaraman, C. H. Smith, and M. Velauthapillai. Learning
programs with an easy to calculate set of errors. Fundamenta Informaticae,
pages 355–370, 1992.
[47] E. M. Gold. Limiting recursion. Journal of Symbolic Logic, 30:28–48, 1965.
[48] E. M. Gold. Language identification in the limit. Inform. Control, 10(5):447–
474, 1967.
[49] J. Grabowski. Starke Erkennung. In R. Linder and H. Thiele, editors, Strukturerkennung diskreter kybernetischer Systeme, volume 82, pages 168–184. Seminarberichte der Sektion Mathematik der Humboldt-Universität zu Berlin, 1986.
[50] G. Grieser. Reflective inductive inference of recursive functions. Theoret. Comput. Sci., xxx(xxx):xx–xx, 2007.
[51] D. Haussler, M. Kearns, N. Littlestone, and M. K. Warmuth. Equivalence ofmodels for polynomial learnability. Inform. Comput., 95(2):129–161, 1991.

Learning Recursive Functions

75[52] J. Helm. On effectively computable operators. Zeitschrift für Mathematische
Logik und Grundlagen der Mathematik (ZML), 17:231–244, 1971.
[53] S. Jain. Robust behaviorally correct learning. Inform. Comput., 153(2):238–248,
1999.
[54] S. Jain, E. Kinber, C. Papazian, C. Smith, and R. Wiehagen. On the intrinsic
complexity of learning recursive functions. Inform. Comput., 184(1):45–70, 2003.
[55] S. Jain, D. Osherson, J. S. Royer, and A. Sharma. Systems that Learn: An
Introduction to Learning Theory, second edition. MIT Press, Cambridge, Massachusetts, 1999.
[56] S. Jain and A. Sharma. Learning with the knowledge of an upper bound on
program size. Inform. Comput., 102(1):118–166, 1993.
[57] S. Jain, C. Smith, and R. Wiehagen. Robust learning is rich. J. Comput. Syst.
Sci., 62(1):178–212, 2001.
[58] K. P. Jantke. Natural properties of strategies identifying recursive functions.
Elektronische Informationsverarbeitung und Kybernetik, 15(10):487–496, 1979.
[59] K. P. Jantke and H.-R. Beick. Combining postulates of naturalness in inductive
inference. Elektronische Informationsverarbeitung und Kybernetik, 17(8/9):465–
484, 1981.
[60] E. Kinber, C. Papazian, C. Smith, and R. Wiehagen. On the intrinsic complexityof learning recursive functions. In Proceedings of the Twelfth Annual Conference
on Computational Learning Theory, July 6th-9th, 1999, Santa Cruz, California,
pages 257–266, New York, NY, 1999. ACM Press.
[61] E. Kinber and T. Zeugmann. One-sided error probabilistic inductive inference
and reliable frequency identification. Inform. Comput., 92(2):253–284, 1991.
[62] E. B. Kinber and T. Zeugmann. Inductive inference of almost everywhere correct
programs by reliably working strategies. Elektronische Informationsverarbeitung
und Kybernetik, 21(3):91–100, 1985.
[63] R. Klette and R. Wiehagen. Research in the theory of inductive inference by
GDR mathematicians – A survey. Inform. Sci., 22:149–169, 1980.
[64] S. A. Kurtz and C. H. Smith. On the role of search for learning. In Proceedingsof the Second Annual Workshop on Computational Learning Theory, pages 303–
311, San Mateo, CA, 1989. Morgan Kaufmann.
[65] S. A. Kurtz and C. H. Smith. A refutation of Barzdins’ conjecture. In Analogicaland Inductive Inference, International Workshop AII ’89, Reinhardsbrunn Castle, GDR, October 1989, Proceedings, volume 397 of Lecture Notes in Artificial
Intelligence, pages 171–176. Springer-Verlag, 1989.

76

Thomas Zeugmann and Sandra Zilles[66] S. A. Kurtz, C. H. Smith, and R. Wiehagen. On the role of search for learningfrom examples. J. of Experimental and Theoret. Artif. Intell., 13(1):25–43, 2001.
[67] L. H. Landweber and E. L. Robertson. Recursive properties of abstract complexity classes. Journal of the ACM, 19(2):296–308, 1972.
[68] S. Lange and T. Zeugmann. Incremental learning from positive data. J. of
Comput. Syst. Sci., 53(1):88–103, 1996.
[69] S. Lange, T. Zeugmann, and S. Zilles. Learning indexed families of recursive
languages from positive data: a survey. Theoret. Comput. Sci., xxx(x):xx–xx,
2007.
[70] R. Linder and H. Thiele, editors. Strukturerkennung diskreter kybernetischer
Systeme, volume 82. Seminarberichte der Sektion Mathematik der HumboldtUniversität zu Berlin, 1986.
[71] R. Lindner. Algorithmische Erkennung.
Universität, Jena, 1972.

Dissertation B, Friedrich-Schiller-[72] X. C. Ling. Inductive learning from good examples. In Proceedings of the 12th
International Joint Conference on Artificial Intelligence, Sydney, Australia, August 24-30, 1991, pages 751–756. Morgan Kaufmann, 1991.
[73] N. Littlestone. Learning quickly when irrelevant attributes abound: A newlinear-threshold algorithm. Machine Learning, 2(4):285–318, 1988.
[74] E. M. McCreight and A. R. Meyer. Classes of computable functions defined bybounds on computation: Preliminary report. In Proceedings of the first annual
ACM symposium on Theory of computing, Marina del Rey, California, UnitedStates, pages 79–88. ACM Press, 1969.
[75] E. Minicozzi. Some natural properties of strong identification in inductive inference. Theoret. Comput. Sci., 2(3):345–360, 1976.
[76] J. Nessel. Learnability of enumerable classes of recursive functions from “typical” examples. In Algorithmic Learning Theory, 10th International Conference,
ALT ’99, Tokyo, Japan, December 1999, Proceedings, volume 1720 of Lecture
Notes in Artificial Intelligence, pages 264–275. Springer, 1999.
[77] P. Odifreddi. Classical Recursion Theory. North Holland, Amsterdam, 1989.
[78] W. of Ockham. Quodlibeta Septem (in translation). Circa 1320.
[79] D. N. Osherson, M. Stob, and S. Weinstein. Systems that Learn: An Introduction to Learning Theory for Cognitive and Computer Scientists. MIT Press,
Cambridge, Massachusetts, 1986.

Learning Recursive Functions

77[80] M. Ott and F. Stephan. Avoiding coding tricks by hyperrobust learning. In Computational Learning Theory, 4th European Conference, EuroCOLT ’99, Nordkirchen, Germany, March 29-31, 1999, Proceedings, volume 1572 of Lecture
Notes in Artificial Intelligence, pages 183–197. Springer, 1999.
[81] L. Pitt. Probabilistic inductive inference. J. ACM, 36(2):383–433, 1989.
[82] K. M. Podnieks. Sravnenie razliqnyh tipov sinteza i prognozirovani funkci$
i I. In J. M. Barzdin, editor, Teori Algoritmov
i Programm, volume I, pages 68–81. Latvian State University, 1974.
[83] K. M. Podnieks. Sravnenie razliqnyh tipov sinteza i prognozirovani funkci$
i II. In J. M. Barzdin, editor, Teori Algoritmov i
Programm, volume II, pages 35–44. Latvian State University, 1975.
[84] K. Popper. The Logic of Scientific Discovery. (2nd ed.). Harper Torch Books,
New York, 1968.
[85] H. Putnam. Probability and confirmation. In Mathematics, Matter and Method.
Cambridge University Press, 1975.
[86] H. J. Rogers. Theory of Recursive Functions and Effective Computability.
McGraw-Hill, 1967. Reprinted, MIT Press 1987.
[87] C. H. Smith. The power of pluralism for automatic program synthesis. J. ACM,
29(4):1144–1165, 1982.
[88] C. H. Smith. A Recursive Introduction to the Theory of Computation. SpringerVerlag, New York, Berlin, Heidelberg, 1994.
[89] C. H. Smith. Three decades of team learning. In Algorithmic Learning Theory,
4th International Workshop on Analogical and Inductive Inference, AII ’94, 5thInternational Workshop on Algorithmic Learning Theory, ALT ’94, Reinhardsbrunn Castle, Germany, October 1994, Proceedings, volume 872 of Lecture Notes
in Artificial Intelligence, pages 211–228. Springer-Verlag, 1994.
[90] C. H. Smith and M. Velauthapillai. On the inference of programs approximately
computing the desired function. In Analogical and Inductive Inference, International Workshop AII ’86. Wendisch-Rietz, GDR, October 1986, Proceedings,
volume 265 of Lecture Notes in Computer Science, pages 164–176. SpringerVerlag, 1986.
[91] R. M. Smullyan. Theory of formal systems, volume 47 of Annals of Mathathematical Studies. Princeton University Press, Princeton, New Jersey, USA, 1961.
[92] R. J. Solomonoff. A formal theory of inductive inference. part i. Inform. Control,
7(1):1–22, 1964.

78

Thomas Zeugmann and Sandra Zilles[93] R. J. Solomonoff. A formal theory of inductive inference. part ii. Inform.
Control, 7(2):224–254, 1964.
[94] F. Stephan and T. Zeugmann. Learning classes of approximations to nonrecursive functions. Theoret. Comput. Sci., 288(2):309–341, 2002.
[95] H. Thiele. Lernverfahren zur Erkennung formaler Sprachen. In Lernende Systeme, volume 3 of Kybernetik-Forschung, pages 11–93. Deutscher Verlag derWissenschaften, Berlin, 1973.
[96] B. A. Trakhtenbrot and Y. M. Barzdin. Finite Automata, Behavior and Synthesis. North Holland, Amsterdam, 1973.
[97] R. Wiehagen. Limes-Erkennung rekursiver Funktionen durch spezielle Strategien. Elektronische Informationsverarbeitung und Kybernetik, 12(1/2):93–99,
1976.
[98] R. Wiehagen. Characterization problems in the theory of inductive inference.
In Automata, Languages and Programming Fifth Colloquium, Udine, Italy, July
17-21, 1978, volume 62 of Lecture Notes in Computer Science, pages 494 – 508,
Berlin, 1978. Springer-Verlag.
[99] R. Wiehagen. Zur Theorie der Algorithmischen Erkennung. Dissertation B,
Humboldt-Universität zu Berlin, 1978.
[100] R. Wiehagen. A thesis in inductive inference. In Nonmonotonic and Inductive
Logic, 1st International Workshop, Karlsruhe, Germany, December 1990, Proceedings, volume 543 of Lecture Notes in Artificial Intelligence, pages 184–207,
Berlin, 1990. Springer-Verlag.
[101] R. Wiehagen, R. Freivalds, and E. Kinber. On the power of probabilistic strategies in inductive inference. Theoret. Comput. Sci., 28(1-2):111–133, 1984.
[102] R. Wiehagen and W. Liepe. Charakteristische Eigenschaften von erkennbaren
Klassen rekursiver Funktionen. Elektronische Informationsverarbeitung und Kybernetik, 12(8/9):421–438, 1976.
[103] R. Wiehagen and T. Zeugmann. Ignoring data may be the only way to learn
efficiently. J. of Experimental and Theoret. Artif. Intell., 6(1):131–144, 1994.
[104] R. Wiehagen and T. Zeugmann. Learning and consistency. In Algorithmic
Learning for Knowledge-Based Systems, GOSLER Final Report, volume 961 of
Lecture Notes in Artificial Intelligence, pages 1–24. Springer, 1995.
[105] P. Young. Easy constructions in complexity theory: Gap and speed-up theorems.
Proceedings of the American Mathematical Society, 37(2):555–563, 1973.

Learning Recursive Functions

79[106] T. Zeugmann. A-posteriori characterizations in inductive inference of recursive functions. Elektronische Informationsverarbeitung und Kybernetik,
19(10/11):559–594, 1983.
[107] T. Zeugmann. On the nonboundability of total effective operators. Zeitschriftfür Mathematische Logik und Grundlagen der Mathematik (ZML), 30:169–172,
1984.
[108] T. Zeugmann. On Barzdin’s conjecture. In Analogical and Inductive Inference, International Workshop AII ’86. Wendisch-Rietz, GDR, October 1986,
Proceedings, volume 265 of Lecture Notes in Computer Science, pages 220–227.
Springer-Verlag, 1986.
[109] T. Zeugmann. Inductive inference of optimal programs: A survey and open
problems. In Nonmonotonic and Inductive Logic, 1st International Workshop,
Karlsruhe, Germany, December 1990, Proceedings, volume 543 of Lecture Notes
in Artificial Intelligence, pages 208–222. Springer-Verlag, 1990.
[110] S. Zilles. On the synthesis of strategies identifying recursive functions. In
Computational Learning Theory: 14th Annual Conference on Computational
Learning Theory, COLT 2001 and 5th European Conference on Computational
Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 16-19,
2001, Proceedings, volume 2111 of Lecture Notes in Artificial Intelligence, pages
160–176. Springer-Verlag, 2001.
[111] S. Zilles. Uniform Learning of Recursive Functions. DISKI 278, Akademische
Verlagsgesellschaft Aka GmbH, 2003.
[112] S. Zilles. Separation of uniform learning classes. Theoret. Comput. Sci., 313:229–
265, 2004.
[113] S. Zilles. An approach to intrinsic complexity of uniform learning. Theoret.
Comput. Sci., 364(1):42–61, 2006.