On the Uniform Learnability of Approximations
to Non-Recursive Functions
Frank Stephan 1 , ? and Thomas Zeugmann 2 , ??
1

Mathematisches Institut, Universität Heidelberg, Im Neuenheimer Feld 294,
69120 Heidelberg, Germany
fstephan@math.uni-heidelberg.de
2
Department of Informatics, Kyushu University, Kasuga 816-8580, Japanthomas@i.kyushu-u.ac.jp

Abstract. Blum and Blum (1975) showed that a class B of suitable recursive approximations to the halting problem is reliably EX-learnable.
These investigations are carried on by showing that B is neither in NUM
nor robustly EX-learnable. Since the definition of the class B is quite
natural and does not contain any self-referential coding, B serves as an
example that the notion of robustness for learning is quite more restrictive than intended.
Moreover, variants of this problem obtained by approximating any given
recursively enumerable set A instead of the halting problem K are studied. All corresponding function classes U (A) are still EX-inferable but
may fail to be reliably EX-learnable, for example if A is non-high andhypersimple. Additionally, it is proved that U (A) is neither in NUM nor
robustly EX-learnable provided A is part of a recursively inseparable
pair, A is simple but not hypersimple or A is neither recursive nor high.
These results provide more evidence that there is still some need to findan adequate notion for “naturally learnable function classes.”

1. Introduction
Though algorithmic learning of recursive functions has been intensively studied
within the last three decades there is still some need to elaborate this theory
further. For the purpose of motivation, let us shortly recall the basic scenario.
An algorithmic learner is fed growing initial segments of the graph of thetarget function f . Based on the information received, the learner computes a?

Supported by the Deutsche Forschungsgemeinschaft (DFG) under Research Grant
no. Am 60/9-2.
??
Supported by the Grant-in-Aid for Scientific Research in Fundamental Areas
from the Japanese Ministry of Education, Science, Sports, and Culture under
grant no. 10558047. Part of this work was done while visiting the Laboratoired’Informatique Algorithmique: Fondements et Applications, Université Paris 7. Thisauthor is gratefully indebted to Maurice Nivat for providing financial support andinspiring working conditions.

hypothesis on each input. The sequence of all computed hypotheses has to converge to a correct, finite and global description of the target f . We shall referto this scenario by saying that f is EX-learnable (cf. Definition 1).
Clearly, what one is really interested in are powerful learning algorithms thatcannot only learn one function but all functions from a given class of functions.
Gold [11] provided the first such powerful learner, i.e., the identification by enumeration algorithm and showed that it can learn every class contained in NUM .
Here NUM denotes the family of all function classes that are subsets of somerecursively enumerable class of recursive functions.
There are, however, learnable classes of recursive functions which are notcontained in NUM . The perhaps most prominent example is the class SD of
self-describing recursive functions, i.e., of all those functions that compute a program for themselves on input 0 . Clearly, SD is EX-learnable.
Since Gold’s [11] pioneering paper a huge variety of learning criteria havebeen proposed within the framework of inductive inference of recursive functions (cf., e.g., [3, 6, 8, 9, 15, 19, 21]). By comparing these inference criteria to one
another, it became popular to show separation results by using function classes
with self-referential properties. On the one hand, the proof techniques developed
are mathematically quite elegant. On the other hand, these separating examples
may be considered to be a bit artificial, because of the use of self-describing
properties. Hence, Bārzdiņš suggested to look at versions of learning that areclosed under computable transformations (cf. [20, 28]). For example, a class U isrobustly EX-learnable, iff, for every computable operator Θ such that Θ(U) is aclass of recursive functions, the class Θ(U) is EX-learnable, too (cf. Definition 4).
There have been many discussions which operators are admissible in this context(cf., e.g., [10, 14, 16, 20, 23, 28]). At the end, it turned out to be most suitable toconsider only general recursive operators, that is, operators which map every
total function to a total one. The resulting notion of robust EX-learning is themost general one among all notions of robust EX-inference.
Next, we state the two main questions that are studied in the present paper.
(1) What is the overall theory developed so far telling us about the learnabilityof “naturally defined function classes?”(2) What is known about the robust EX -learnability of such “naturally defined
function classes?”
Clearly an answer to the first question should tell us something about the usefulness of the theory, and an answer to the second problem should, in particular,
provide some insight into the “naturalness” of robust EX-learning. However,
our knowledge concerning both questions has been severely limited. For function classes in NUM everything is clear, i.e., their learnability has been proved
with respect to many learning criteria including robust EX-learning. Next, let us
consider one of the few “natural” function classes outside NUM that have been
considered in the literature, i.e., the class C of all recursive complexity functions.
Then, using Theorem 2.4 and Corollary 2.6. in [23], one can conclude that C is
not robustly EX-learnable for many complexity measures including space, since2there is no recursive function that bounds every function in C for all but finitely
many arguments. On the other hand, C itself is still learnable with respect tomany inference criteria by using the identification by enumeration learner.
The latter result already provides some evidence that the notion of robust
EX-learning may be too restrictive. Nevertheless, the situation may be completely different if one looks at classes of {0, 1} -valued recursive functions, since
their learnability differs sometimes considerably from the inferability of arbitrary
function classes (cf., e.g., [17, 26]). As far as these authors are aware of, one ofthe very few “natural classes” of {0, 1}-valued recursive functions that may be a
candidate to be not included in NUM has been proposed by Blum and Blum [6].
They considered a class B of approximations to the halting problem K andshowed that B is reliably EX-learnable. This class B is quite natural and not
self-describing. It remained, however, open whether or not B is in NUM .
Within the present work, it is shown that B is neither in NUM nor robustly EX-learnable. Moreover, we study generalizations of Blum and Blum’s [6]original class by considering classes U(A) of approximations for any recursively
enumerable set A. In particular, it is shown that all these classes remain EXlearnable but not necessarily reliably EX-inferable (cf. Theorems 14 and 16).
Furthermore, we show U(A) to be neither in NUM nor robustly EX-learnable
provided A is part of a recursively inseparable pair, A is simple but not hypersimple or A is neither recursive nor high (cf. Theorems 13 and 17).
Thus the results obtained enlarge our knowledge concerning the learnability of “naturally defined” function classes. Additionally, all those classes U(A)which are not in NUM as well as B are natural examples for a class which is on
the one side not self-describing and on the other side not robustly learnable. So
all these U(A) provide some incidence that the presently discussed notions ofrobust and hyperrobust learning [1, 7, 10, 14, 16, 23, 28] destroy not only coding
tricks but also the learnability of quite natural classes.
Due to the lack of space, many proofs are only sketched or omitted. We refer
the reader to [25] for a full version of this paper.

2. Preliminaries
Unspecified notations follow Rogers [24]. IN = {0, 1, 2, . . .} and IN∗ denote theset of all natural numbers and the set of all finite sequences of natural numbers,
respectively. {0, 1}∗ stands for the set of all finite {0, 1} -valued sequences and forall x ∈ IN we use {0, 1}x for the set of all {0, 1}-valued sequences of length x.
The classes of all partial recursive and recursive functions of one, and twoarguments over IN are denoted by P, P 2 , R, and R2 , respectively. f ∈ P issaid to be monotone provided for all x, y ∈ IN we have, if both f (x) and f (y)are defined then f (x) ≤ f (y) . R0,1 and Rmon denotes the set of all {0, 1} valued recursive functions and of all monotone recursive functions, respectively.
Furthermore, we write f n instead of the string (f (0), . . . , f (n)) , for any n ∈IN and f ∈ R . Sometimes it will be suitable to identify a recursive function with3

the sequence of its values, e.g., let α = (a0 , . . . , ak ) ∈ IN∗ , j ∈ IN, and p ∈ R0,1 ;then we write αjp to denote the function f for which f (x) = ax , if x ≤ k ,f (k + 1) = j , and f (x) = p(x − k − 2) , if x ≥ k + 2 . Furthermore, let g ∈ P and
α ∈ IN∗ ; we write α  g iff α is a prefix of the sequence of values associatedwith g , i.e., for all x ≤ k , g(x) is defined and g(x) = ax .
Any function ψ ∈ P 2 is called a numbering. Moreover, let ψ ∈ P 2 , thenwe write ψi for the function x → ψ(i, x) and set Pψ = {ψi i ∈ IN} as well asRψ = Pψ ∩ R . Consequently, if f ∈ Pψ , then there is a number i such thatf = ψi . If f ∈ P and i ∈ IN are such that ψi = f , then i is called a ψ –programfor f . Let ψ be any numbering, and i, x ∈ IN ; if ψi (x) is defined (abbr. ψi (x) ↓ )then we also say that ψi (x) converges. Otherwise, ψi (x) is said to diverge (abbr.
ψi (x) ↑ ).
A numbering ϕ ∈ P 2 is called a Gödel numbering or acceptable numbering(cf. [24]) iff Pϕ = P , and for any numbering ψ ∈ P 2 , there is a c ∈ R such that
ψi = ϕc(i) for all i ∈ IN. In the following, let ϕ be any fixed Gödel numbering. As
usual, we define the halting problem to be the set K = {i i ∈ IN, ϕi (i) ↓ }. Anyfunction Φ ∈ P 2 satisfying dom(ϕi ) = dom(Φi ) for all i ∈ IN and {(i, x, y)i, x, y ∈ IN, Φi (x) ≤ y} is recursive is called a complexity measure (cf. [5]).
Furthermore, let NUM = {U (∃ψ ∈ R2 )[U ⊆ Pψ ]} denote the family of all
subsets of all recursively enumerable classes of recursive functions.
Next, we define the concepts of learning mentioned in the introduction.
Definition 1. Let U ⊆ R and M : IN∗ → IN be a recursive machine.
(a) (Gold [11]) M is an EX-learner for U iff, for each function f ∈ U , M
converges syntactically to f in the sense that there is a j ∈ IN with ϕj = f and
j = M (f n ) for all but finitely many n ∈ IN .
(b) (Angluin [2]) M is a conservative EX-learner for U iff M EX -learns U
and M makes in addition only necessary hypothesis changes in the sense that,whenever M (ση) 6= M (σ) then the program M (σ) is inconsistent with the dataση by either ϕM (σ) (x) ↑ or ϕM (ση) (x) ↓ =6 ση(x) for some x ∈ dom(ση) .
(c) (Bārzdins [4], Case and Smith [8]) M is a BC-learner for U iff, for eachfunction f ∈ U , M converges semantically to f in the sense that ϕM (f n ) = f
for all but finitely many n ∈ IN .
A class U is EX -learnable iff it has a recursive EX -learner and EX denotes
the family of all EX -learnable function classes. Similar we define when a classis conservatively EX -learnable or BC -learnable. We write BC for the family of
all BC -learnable function classes.
Note that EX ⊂ BC (cf. [8]). As far as we are aware of, it has been open
whether or not conservative learning constitutes a restriction for EX -learning ofrecursive functions. The negative answer is provided by the next proposition.
Proposition 2. EX = conservative-EX .
Nevertheless, whenever suitable, we shall design a conservative learner insteadof just an EX -learner, thus avoiding the additional general transformation givenby the proof of Proposition 2.
4

Next, we define reliable inference. Intuitively, a learner M is reliable provided it
converges if and only if it learns. There are several variants of reliable learning,
so we will give a justification of our choice below.
Definition 3 (Blum and Blum [6], Minicozzi [21]). Let U ⊆ R ; then U is
said to be reliably EX-learnable if there is a machine M ∈ R such that
(1) M EX -learns U and(2) for all f ∈ R , if the sequence (M (f n ))n∈IN converges, say to j , then ϕj = f .
By REX we denote the family of all reliably EX -learnable function classes.
Note that one can replace the condition “ f ∈ R ” in (2) of Definition 3 by“f ∈ P ” or “all total f .” This results in a different model of reliable learning,
say PEX and T EX , respectively. Then for every U ⊆ R0,1 such that U ∈ PEX
or U ∈ T EX one has U ∈ NUM (cf. [6, 12, 26]). On the other hand, there areclasses U ⊆ R0,1 such that U ∈ REX \ NUM (cf. [12]). As a matter of fact, ourTheorem 6 below together with Blum and Blum’s [6] result B ∈ REX provides
a much easier proof of the same result than Grabowski [12].
Finally, we define robust EX -learning. This involves the notion of generalrecursive operators. A general recursive operator is a computable mapping thatmaps functions over IN to functions over IN and every total function has to bemapped to a total function. For a formal definition and more information about
general recursive operators the reader is referred to [13, 22, 27].
Definition 4 (Jain, Smith and Wiehagen [16]). Let U ⊆ R ; then U is said
to be robustly EX-learnable if Θ(U) is EX -learnable for every general recursive
operator Θ . By robust-EX we denote the family of all robustly EX -learnable
function classes.

3. Approximating the Halting Problem
Within this section, we deal with Blum and Blum’s [6] class B . First, we define
the class of approximations to the halting problem considered in [6].
Definition 5. Let τ ∈ R be such that for all i ∈ IN
 1, if Φi (x) ↓ and Φx (x) ≤ Φi (x)ϕτ (i) (x) = 0, if Φi (x) ↓ and ¬[Φx (x) ≤ Φi (x)]↑ , otherwise.
Now, we set B = {ϕτ (i) i ∈ IN and Φi ∈ Rmon } .
Blum and Blum [6] have shown B ∈ REX but left it open whether or not
B ∈ NUM . It is not, as our next theorem shows.
Theorem 6. B ∈/ NUM .
Proof. First, recall that K is part of a recursively inseparable pair (cf. [22,Exercise III.6.23.(a)]). That is, there is an r.e. set H such that K ∩H = ∅ and for5every recursive set A ⊇ H we have |A ∩ K| = ∞. Now, we fix any enumeration
k0 , k1 , k2 , . . . and h0 , h1 , h2 , . . . of K and H , respectively. Suppose to thecontrary, that there exists a numbering ψ ∈ R2 such that B ⊆ Rψ . Next, we
define for each ψe a function ge ∈ P as follows. For all e, x ∈ IN letge (x) = “Search for the least n such that for n = s + y either (A), (B) or (C)happens:(A) y = hs ∧ ψe (y) = 1(B) y = ks ∧ ψe (y) = 0 ∧ y > x(C) ψe (y) > 1
If (A) happens first, then set ge (x) = s + y .
If (B) happens first, then let ge (x) = Φy (y) + y .
If (C) happens first, then let ge (x) = 0 .”Claim 1. ge ∈ R for all e ∈ IN .
If there is at least one y such that ψe (y) > 1 , then ge ∈ R . Now let
ψe ∈ R0,1 and suppose that there is an x ∈ IN with ge (x) ↑ . Then there are nos, y such that y = hs and ψe (y) = 1 . Hence, M = {y y ∈ IN ∧ ψe (y) = 0} ⊇ H
and M is recursive. Thus, |M ∩ K| = ∞. So there must be a y > x such thatψe (y) = 0 and an s ∈ IN with y = ks . Thus (B) must happen, and since y = ks ,we conclude Φy (y) ↓ . Hence, ge (x) ↓ , too, a contradiction. This proves Claim 1.
Claim 2. Let e be any number such that ψe = ϕτ (i) for some ϕτ (i) ∈ B . Thenge (x) > Φi (x) for all x ∈ IN .
Assume any i, e as above, and consider the definition of ge (x) . Supposege (x) = s + y for some s, y such that y = hs and ψe (y) = 1 . Since ψe (y) =ϕτ (i) (y) = 1 implies Φy (y) ≤ Φi (y) , and hence y ∈ K , we get a contradiction
to K ∩ H = ∅ . Thus, this case cannot happen.
Consequently, in the definition of ge (x) condition (B) must have happened.
Thus, some s, y such that y > x, y = ks and ψe (y) = 0 have been found.
Since y = ks , we conclude Φy (y) ↓ and thus g(x) > Φy (y) . Because of ψe (y) =ϕτ (i) (y) = 0, we obtain Φi (y) < Φy (y) by the definition of ϕτ (i) . Now, putting it
all together, we get g(x) > Φy (y) > Φi (y) ≥ Φi (x) , since y > x and Φi ∈ Rmon .
This proves Claim 2.
Claim 3. For every b ∈ R there exists an i ∈ IN such that Φi ∈ Rmon andb(x) < Φi (x) for all x ∈ IN.
Let r ∈ R be such that for all j, x ∈ IN we have0,
if ¬[Φj (0) ≤ b(0)]ϕr(j) (0) =ϕj (0) + 1, otherwise
and for x > 00,
if Φj (n) is defined for all n < x ∧¬[Φj (x) ≤ Φj (x − 1) ∨ Φj (x) ≤ b(x)]
ϕr(j) (x) = ϕj (x) + 1, if Φj (n) is defined for all n < x ∧[Φj (x) ≤ Φj (x − 1) ∨ Φj (x) ≤ b(x)]↑,otherwise.
6

By the fixed point theorem [24] there is an i ∈ IN such that ϕr(i) = ϕi . Now, one
inductively shows that ϕi = 0∞ , Φi ∈ Rmon and b(x) < Φi (x) for all x ∈ IN
and Claim 3 follows.
Finally, by Claim 1, all ge ∈ R , and thus there is a function b ∈ R such thatb(x) ≥ ge (x) for all e ∈ IN and all but finitely many x ∈ IN (cf. [6]). Together
with Claim 2, this function b contradicts Claim 3, and hence B ∈/ NUM .
The next result can be obtained by looking at U(K) in Theorems 15 and 17.
Theorem 7. B is REX -inferable but not robustly EX -learnable.
Theorems 6 and 7 immediately allow the following separation, thus reproving
Grabowski’s [12] Theorem 5.
Corollary 8. NUM ∩ ℘(R0,1 ) ⊂ REX ∩ ℘(R0,1 ) .
Finally, we ask whether or not the condition Φi ∈ Rmon in the definition of theclass B is necessary. The affirmative answer is given by our next theorem. Thatis, instead of B , we now consider the class B̃ = {ϕτ (i) i ∈ IN and Φi ∈ R}.
Theorem 9. B̃ is not BC -learnable.
Next, we generalize the approach undertaken so far by considering classes U(A)of approximations to any recursively enumerable (abbr. r.e.) set A.

4. Approximating Arbitrary r.e. Sets
The definition of Blum and Blum’s [6] class uses implicitly the measure ΦK
defined as ΦK (x) = Φx (x) for measuring the speed by which K is enumerated.
Using this notion ΦK , the class B of approximations of K is defined as
B = {f ∈ R0,1 (∃Φe ∈ Rmon ) (∀x) [f (x) = 1 ⇔ ΦK (x) ≤ Φe (x)] } .
Our main idea is to replace K by an arbitrary r.e. set A and to replace ΦK by
a measure ΦA of (the enumeration speed of) A. Such a measure satisfies thefollowing two conditions:– The set {(x, y) ΦA (x) ↓ ≤ y} is recursive.
– x ∈ A ⇔ (∃y) [ΦA (x) ≤ y] .
Here, ΦA is intended to be taken as the function Φi of some index i of A, butsometimes we might also take the freedom to look at some other functions ΦAsatisfying the two requirements above. The natural definition for a class U(A)corresponding to the class B in the case A = K based on an underlying function
ΦA is the following.
Definition 10. Given an r.e. set A, an enumeration ΦA and a total function
Φe , let
1, if ΦA (x) ≤ Φe (x)fe (x) =0, if ¬[ΦA (x) ≤ Φe (x)].
7Now U(A) consists of all those fe where Φe ∈ Rmon .
Next, comparing U(K) to the original class B of Blum and Blum [6] one caneasily prove the following. For every f ∈ B there is a function g ∈ U(K) suchthat for all x ∈ IN we have f (x) = 1 implies g(x) = 1 . Hence, the approximation
g is at least as good as f . The converse is also true, i.e., for each g ∈ U(K) there
is an f ∈ B such that g(x) = 1 implies f (x) = 1 for all x ∈ IN . Therefore, we
consider our new classes of approximations as natural generalizations of Blumand Blum’s [6] original definition.
Moreover, note that there is a function genA which computes for every e ofa monotone Φe a program genA (e) for the function f associated with Φe : 1, if ΦA (x) ≤ Φe (x) ↓ ∧ (∀y < x)[Φe (y) ≤ Φe (y + 1)]
ϕgenA (e) (x) = 0, if ¬[ΦA (x) ≤ Φe (x) ↓ ] ∧ (∀y < x)[Φe (y) ≤ Φe (y + 1)]
↑ , otherwise.
Now, if A is recursive, everything is clear, since we have the following.
Theorem 11. If A is recursive then U(A) ∈ NUM .
The direct generalization of Theorem 6 would be that U(A) is not in NUM forevery non-recursive r.e. set A and every measure ΦA . Unfortunately, there aresome special cases where this is still unknown to us.
We obtained many intermediate results which give incidence that U(A) is
not in NUM for any non-recursive r.e. set A . First, every non-recursive set A has
a sufficiently “slow” enumeration such that U(A) ∈/ NUM for this underlying
enumeration and the corresponding ΦA . Second, for many classes of sets we candirectly show that U(A) ∈/ NUM , whatever measure ΦA we choose. Besides thecases where A is part of a recursively inseparable pair or A is simple but not
hypersimple, the case of the non-recursive and non-high sets A is interesting, inparticular, since the proof differs from that for the two previous cases.
Recall that a set A is simple iff A is both r.e. and infinite, A is infinite but
there is no infinite recursive set R disjoint to A. A set A is hypersimple iff A
is both r.e. and infinite, and there is no function f ∈ R such that f (n) ≥ anfor all n ∈ IN, where a0 , a1 , . . . is the enumeration of A in strictly increasingorder (cf. Rogers [24]). Using this definition of hypersimple sets, one can easily
show the following lemma.
Lemma 12. A set A ⊆ IN is hypersimple iff(a) A is r.e. and both A and A are infinite(b) for all functions g ∈ R with g(x) ≥ x for all x ∈ IN there exist infinitely
many x ∈ IN such that {x, x + 1, . . . , g(x)} ⊆ A.
Now, we are ready to state the announced theorem.
Theorem 13. U(A) is not in NUM for the following r.e. sets A .
(a) A is part of a recursively inseparable pair.
(b) A is simple but not hypersimple.
(c) A is neither recursive nor high.
8

Proof. We sketch only the proof of Assertion (c) here. Assume by way ofcontradiction U(A) ∈ NUM . Thus, there is a ψ ∈ R2 such that U(A) ⊆ Rψ .
Assume without loss of generality that 0 ∈ A. The A-recursive function dA (x) =max{ΦA (y) y ≤ x and y ∈ A} is total and recursive relative to A. If now
m(x) ≥ dA (x), then the function generated by m in accordance to Definition 10
is equal to the characteristic function of A.

1, if ΦA (x) ≤ m(x)A(x) = fm (x) =0, if ¬[ΦA (x) ≤ m(x)].
So one can define the following A-recursive function h :h(x) = min{y ≥ x (∀j ≤ x) (∃z)[(x ≤ z ≤ y) ∧ ψj (z) 6= A(z)]} .
Since A is not recursive, no function ψj can be a finite variant of A(x) , andthus h is total. Using h we next the following total A-recursive function g byPh(x)g(x) = y=x dA (y). Since A is not high, there is a function b ∈ R such thatb(x) ≥ g(x) for infinitely many x. By Claim 3 in the demonstration of Theorem 6, there exists an e ∈ IN such Φe ∈ Rmon and Φe (x) > b(x) for all x ∈ IN .
Thus, Φe (x) ≥ g(x) for infinitely many x.
Next, for every ψk ∈ Rψ there exists an x > k such that Φe (x) > g(x) .
Consider all y = x, x + 1, . . . , h(x) . By the definition of g and by Φe ∈ Rmon ,we have Φe (y) ≥ dA (y) for all these y . Thus, by the choice of dA and the definition of ϕgenA (e) we arrive at ϕgenA (e) (y) = A(y) for all y = x, x + 1, . . . , h(x) .
But now the definition of the function h guarantees that ψk (z) 6= ϕgenA (e) (z)for some z with x ≤ z ≤ h(x) . Consequently, ϕgenA (e) differs from all fk incontradiction to the assumption U(A) ∈ NUM .

5. Reliable and EX -Learnability of U (A)Blum and Blum [6] showed B ∈ REX . The EX -learnability of U(A) alone canbe generalized to every r.e. set A, but this is not possible for reliability. But
before dealing with REX -inference, we show that every U(A) is EX -learnable.
Theorem 14. U(A) is EX -learnable for all r.e. sets A.
Proof. If A is recursive, then U(A) ∈ NUM (cf. Theorem 11) and thus EX learnable. So let A be non-recursive and let ΦA be a recursive enumeration of A.
An EX -learner for the class U(A) is given as follows.
– On input σ , disqualify all e such that there are x ∈ dom(σ) and y ≤ |σ|satisfying one of the following three conditions:(a) ΦgenA (e) (x) ≤ |σ| and ϕgenA (e) (x) 6= σ(x)(b) σ(x) = 0, ΦA (x) ≤ y and ¬[Φe (x) ≤ y](c) Φe (x + 1) ≤ y and ¬[Φe (x) ≤ y] .
– Output genA (e) for the smallest e not yet disqualified.
9

The algorithm disqualifies only such indices e where ϕgenA (e) is either definedand false or undefined for some x ∈ dom(σ) . Thus the learner is conservative.
Since the correct indices are never disqualified, it remains to show that theincorrect ones are. This clearly happens if ϕgenA (e) (y) ↓ =6 σ(y) for some y .
Otherwise let z be the first undefined place of ϕgenA (e) . This undefined place iseither due to the fact that Φe (x) > Φe (x + 1) for some x < z or that Φe (z) ↑ .
In the first case, e is eventually disqualified by condition (c), in the second case,either Φe (x + 1) ↓ for some first x ≥ z , then e is again eventually disqualified
by condition (c) or Φe (x) ↑ for some x ∈ A above z and so e is disqualified bycondition (b). Hence, the learning algorithm is correct.
The result that B is reliably EX -learnable can be generalized to halves of recursively inseparable pairs and to simple but not hypersimple sets.
Theorem 15. U(A) is reliably EX-learnable if(a) A is part of a recursively inseparable pair or(b) A is simple but not hypersimple.
Proof. The central idea of the proof is that conditions (a) and (b) allow to
identify a class of functions which contains all recursive functions which are too
difficult to learn and on which the learner then signals infinitely often divergence. The recursive functions outside this class turn out to be EX -learnable
and contain the class U(A).
The learner M does not need to succeed on functions f ∈/ R0,1 or if f (x) = 1
for almost all x ∈ A. Now, the second condition can be checked indirectly forf ∈ R0,1 and the A in the precondition of the theorem.
In case (a), let A and B = {b0 , b1 , . . .} form a recursively inseparable pair.
If f (x) = 1 for almost all x ∈ A then f (bs ) = 1 for some bs . So one definesthat σ disqualifies if σ(x) ≥ 2 for some x or if σ(bs ) ↓ = 1 for some s ≤ |σ|.
In case (b), the set A is simple but not hypersimple. By Lemma 12 there
is a function g ∈ R with g(x) ≥ x for all x ∈ IN such that A intersects every
interval {x, x + 1, . . . , g(x)}. But if f (x) = 1 for almost all x ∈ A, then, by thesimplicity of A, f (x) = 1 for almost all x and there is an x with f (y) = 1 for
all y ∈ {x, x + 1, . . . , g(x)} . So one defines that σ disqualifies if σ(x) ≥ 2 forsome x or if there is an x and σ(y) = 1 for all y ∈ {x, x + 1, . . . , g(x)}.
The reliable EX -learner N is a modification of the learner M from Theorem 14 which copies M on all σ except those which disqualify — on them,N always outputs a guess for σ0∞ and thus either converges to some σ0∞ or
diverges by infinitely many changes of the hypothesis. Let e(σ) be a programfor σ0∞ and let
e(σ),
if σ is disqualified
N (σ) =M (σ), otherwise.
For the verification, note that for every f ∈ U(A) we have f (x) = 0 for allx ∈ A. Thus, if f ∈ U(A) then no σ  f is disqualified and therefore N is an
EX -learner for U(A).
Assume now that N converges to an e0 on some recursive function f . If
10

this happens for a function f such that some σ 0  f has been disqualified thenf = σ0∞ and so also ϕe0 = σ0∞ for some σ  f . Thus, N converges to acorrect program for f in this case.
Otherwise, no σ 0  f is disqualified. Since N copies the indices of M andthose are all of the form genA (e) , there is a least e with e0 = genA (e) . If
f (x) = 0 for infinitely many x ∈ A, then M converges only to genA (e) if
ϕgenA (e) = f and the algorithm is correct in that case.
Finally, consider the subcase that f (x) = 0 for only finitely many x ∈ A.
Consequently, in case (a) f (x) = 1 for some x ∈ B and in case (b) there must
be an x such that f (y) = 1 for all y = x, x + 1, . . . , g(x) . In both cases, someσ 0  f is disqualified, thus this case cannot occur. Hence, N is reliable.
Theorem 16. If A is hypersimple and not high then U(A) ∈/ REX .
Proof. Let A be a hypersimple non-high set, let ΦA be a corresponding measure, and assume to the contrary that U(A) ∈ REX . Then also the union
U(A) ∪ {α1∞ α ∈ {0, 1}∗ }is EX -learnable, since every class in NUM is also in REX and REX is closed
under union (cf. [6, 21]). Given an EX -learner M for the above union, one candefine the following function h1 by taking
h1 (x) = min{s ≥ x (∀σ ∈ {0, 1}x ) (∀y ≤ x) [M (σ1s ) 6= M (σ) ∨ΦM (σ) (y) ≤ s ∧ ϕM (σ) (y) = σ(y)]}.
The function h1 is total since any guess M (σ) either computes the function
σ1∞ or is eventually replaced by a new guess on σ1∞ . Note that h1 ∈ Rmonand h1 (x) ≥ x for all x.
Since A is not recursive, there is no total function dominating ΦA . Thus
one can define a recursive function h2 (x) by taking
h2 (x) = the smallest s such that there is a y with x ≤ y ≤ s ∧h1 (y + h1 (y)) < s ∧ ΦA (y) + ΦA (y + 1) + . . . + ΦA (y + h1 (y)) < s .
Since A is hypersimple, we directly get from Lemma 12 that h2 ∈ R . Consider
for every f ∈ U(A) the index i to which M converges and an index j with
f = ϕgenA (j) .
Assume now that M has converged to i at z ≤ x. Consider the y, s fromthe definition of h2 and let σ = f (0), . . . , f (y) . If M (σ1h1 (y) ) 6= M (σ) thenthere is some y 0 ∈ {y, y + 1, . . . , y + h1 (y)} with f (y 0 ) = 0 . As a consequence,Φj (y 0 ) < ΦA (y 0 ) < h2 (y). Since Φj ∈ Rmon , we know Φj (y) < s. Otherwise,
Φi (x) ≤ h1 (y) and ϕi (x) has converged. Since y ≤ h2 (x) , we conclude Φi (x) ≤h1 (h2 (x)). So one can give the following definition for f by case-distinction
where the first case is taken which is applicable and where σ = f (0), . . . , f (z) .

σ(x), if x ∈ dom(σ)
ϕi (x), if Φi (x) ≤ h1 (h2 (x))ϕe(i,j,σ) (x) =if ΦA (x) ≤ Φj (x) ≤ h2 (x)

 1,
0,
otherwise.
11

Since the search-conditions in the second and third case are bounded by a recursive function in x, the family of all ϕe(i,j,σ) contains only total functions
and its universal i, j, σ, x → ϕe(i,j,σ) (x) is computable in all parameters. Furthermore, for the correct i, j, σ as chosen above, ϕe(i,j,σ) equals the given fsince, for all x > z , either ϕi (x) converges within h1 (h2 (x)) steps to f (x) orΦA (x) ≤ Φj (x) ≤ h2 (x). It follows that this family covers U(A) and that U(A)is in NUM which, a contradiction to Theorem 13, since A is neither recursive
nor high.

6. Robust Learning
A mathematical elegant proof method to separate learning criteria is the use ofclasses of self-describing functions. On the one hand, these examples are a bit
artificial, since they use coding tricks. On the other hand, natural objects likecells contain a description of themselves. Nevertheless, from a learning theoreticalpoint some criticism remains in order, since a learner needs only to fetch somecode from the input.
Therefore, Bārzdiņš suggested to look at restricted versions of learning: For
example, a class S is robustly EX -learnable, iff, for every operator Θ , the classΘ(S) is EX -learnable. There were many discussions, which operators Θ areadmissible in this context and how to deal with those cases where Θ maps
some functions in S to partial functions. At the end, it turned out that it ismost suitable to consider only general recursive operators Θ which map every
total function to a total one [16]. This notion is among all notions of robust
EX -learning the most general one in the sense that every class S which isrobustly EX -learnable with respect to any criterion considered in the literatureis also robustly EX -learnable with respect to the model of Jain, Smith andWiehagen [16].
Although the class B is quite natural and does not have any obvious selfreferential coding, the class B is not robustly EX -learnable — so while on the one
hand the notion of robust EX -learning still permits topological coding tricks [16,23], it does on the other hand already rule out the natural class B . The provided
example gives some incidence, that there is still some need to find a adequate
notion for a “natural EX -learnable class.”
Every class in NUM is robustly EX -learnable, in particular the class U(A)for a recursive set A (cf. Theorem 11). The next theorem shows that U(A)is not robustly EX -learnable for any nonrecursive sets A which are part of arecursively inseparable pair, which are simple but not hypersimple or which areneither recursive nor high. Thus, here the situation is parallel to the one at
Theorem 13.
Theorem 17. U(A) is not robustly EX-learnable for the following r.e. sets A.
(a) A is part of a recursively inseparable pair.
(b) A is simple but not hypersimple.
(c) A is neither recursive nor high.
127. Conclusions
The main topic of the present investigations have been the class B of Blum andBlum [6] and the natural generalizations U(A) of it obtained by using r.e. sets A
as a parameter. It is has been shown that for large families of r.e. sets A, theseclasses U(A) are not in NUM . Furthermore, they can be always EX -learned.
Moreover, for some but not all sets A there is also a REX -learner. Robust EX learning is impossible for all non-recursive sets A that are part of recursively
inseparable pair, for simple but not hypersimple sets A and for all sets A thatare non-high and non-recursive. Since the classes U(A) are quite natural, thisresult adds some incidence that “natural learnability” does not coincide withrobust learnability as defined in the current research.
Future work might address the remaining unsolved question whether U(A)is outside NUM for all non-recursive sets A. Additionally, one might investigate
whether U(A) is robustly BC -learnable for some sets A such that U(A) is
not robustly EX -inferable. It would be also interesting to know whether or not
U(A) can be reliably BC -learned for sets A with U(A) ∈/ REX (cf. [18] formore information concerning reliable BC -learning). Finally, there are some ways
to generalize the notion of U(A) to every K -recursive set A and one mightinvestigate the learning theoretic properties of the so obtained classes.

References
1. A. Ambainis and R. Freivalds. Transformations that preserve learnability. In
Proccedings of the 7th International Workshop on Algorithmic Learning Theory(ALT’96) (S. Arikawa and A. Sharma, Eds.) Lecture Notes in Artificial IntelligenceVol. 1160, pages 299–311, Springer-Verlag, Berlin, 1996.
2. D. Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117–135, 1980.
3. D. Angluin and C.H. Smith. A survey of inductive inference: Theory and methods.
Computing Surveys, 15:237–289, 1983.
4. J. Bārzdins. Prognostication of automata and functions. Information Processing’71, (1) 81–84. Edited by C. P. Freiman, North-Holland, Amsterdam, 1971.
5. M. Blum. A machine-independent theory of the complexity of recursive functions.
Journal of the Association for Computing Machinery, 14:322–336.
6. L. Blum and M. Blum. Towards a mathematical theory of inductive inference.
Information and Control, 28:125–155, 1975.
7. J. Case, S. Jain, M. Ott, A. Sharma and F. Stephan. Robust learning aided bycontext. In Proceedings of 11th Annual Conference on Computational Learning
Theory (COLT’98), pages 44–55, ACM Press, New York, 1998.
8. J. Case and C.H. Smith. Comparison of identification criteria for machine inductive
inference. Theoretical Computer Science 25:193–220, 1983.
9. R. Freivalds. Inductive inference of recursive functions: Qualitative theory. In
Baltic Computer Science (J. Bārzdiņš and D. Bjørner, Eds.), Lecture Notes in
Computer Science Vol. 502, pages 77–110. Springer-Verlag, Berlin, 1991.

13

10. M. Fulk. Robust separations in inductive inference. In Proceedings of the 31st
Annual Symposium on Foundations of Computer Science (FOCS), pages 405–410,
St. Louis, Missouri, 1990.
11. M.E. Gold. Language identification in the limit. Information and Control, 10:447–
474, 1967.
12. J. Grabowski. Starke Erkennung. In Strukturerkennung diskreter kybernetischer
Systeme, (R. Linder, H. Thiele, Eds.), Seminarberichte der Sektion Mathematik
der Humboldt-Universität Berlin Vol. 82, pages 168–184, 1986.
13. J.P. Helm. On effectively computable operators. Zeitschrift für mathematische
Logik und Grundlagen der Mathematik (ZML), 17:231–244, 1971.
14. S. Jain. Robust Behaviourally Correct Learning. Technical Report TRA6/98 at
the DISCS, National University of Singapore, 1998.
15. S. Jain, D. Osherson, J.S. Royer and A. Sharma. Systems That Learn: An Introduction to Learning Theory. MIT-Press, Boston, MA., 1999.
16. S. Jain, C. Smith and R. Wiehagen. On the power of learning robustly. In Proceedings of Eleventh Annual Conference on Computational Learning Theory (COLT),
pages 187–197, ACM Press, New York, 1998.
17. E.B. Kinber and T. Zeugmann. Inductive inference of almost everywhere correct
programs by reliably working strategies. Journal of Information Processing andCybernetics, 21:91–100, 1985.
18. E.B. Kinber and T. Zeugmann. One-sided error probabilistic inductive inference
and reliable frequency identification. Information and Computation, 92:253–284,
1991.
19. R. Klette and R. Wiehagen. Research in the theory of inductive inference by GDR
mathematicians – A survey. Information Sciences, 22:149–169, 1980.
20. S. Kurtz and C.H. Smith. On the role of search for learning. In Proceedings of the
2nd Annual Workshop on Computational Learning Theory (R. Rivest, D. Haussler
and M. Warmuth, Eds.) pages 303–311, Morgan Kaufman, 1989.
21. E. Minicozzi. Some natural properties of strong-identification in inductive inference. Theoretical Computer Science, 2:345–360, 1976.
22. P. Odifreddi. Classical Recursion Theory. North-Holland, Amsterdam, 1989.
23. M. Ott and F. Stephan. Avoiding coding tricks by hyperrobust learning. Proceedings of the Fourth European Conference on Computational Learning Theory(EuroCOLT) (P. Fischer and H.U. Simon, Eds.) Lecture Notes in Artificial Intelligence Vol. 1572, pages 183–197, Springer-Verlag, Berlin, 1999.
24. H.Jr. Rogers. Theory of Recursive Functions and Effective Computability.
McGraw–Hill, New York, 1967.
25. F. Stephan and T. Zeugmann. On the Uniform Learnability of Approximations
to Non-Recursive Functions. DOI Technical Report DOI-TR-166, Department ofInformatics, Kyushu University, July 1999.
26. T. Zeugmann. A-posteriori characterizations in inductive inference of recursivefunctions. Journal of Information Processing and Cybernetics (EIK), 19:559–594,
1983.
27. T. Zeugmann. On the nonboundability of total effective operators. Zeitschrift fürmathematische Logik und Grundlagen der Mathematik (ZML), 30:169–172, 1984.
28. T. Zeugmann. On Bārzdiņš’ conjecture. In Proceedings of the International Workshop on Analogical and Inductive Inference (AII’86) (K.P. Jantke, Ed.), Lecture
Notes in Computer Science Vol. 265, pages 220–227. Springer-Verlag, Berlin, 1986.

14