Learning Recursive Functions Refutably ?
Sanjay Jain1,?? , Efim Kinber2 , Rolf Wiehagen3 , and Thomas Zeugmann4
1

School of Computing, National University of Singapore, Singapore 119260
sanjay@comp.nus.edu.sg
2
Department of Computer Science, Sacred Heart University, Fairfield, CT
06432-1000, U.S.A.
kinbere@sacredheart.edu
3
Department of Computer Science, University of Kaiserslautern, PO Box 3049,
67653 Kaiserslautern, Germany
wiehagen@informatik.uni-kl.de
4
Institut für Theoretische Informatik, Med. Universität zu Lübeck, Wallstraße 40,
23560 Lübeck, Germany
thomas@tcs.mu-luebeck.de

Abstract. Learning of recursive functions refutably means that for every recursive function, the learning machine has either to learn this function or to refute it, i.e., to signal that it is not able to learn it. Threemodi of making precise the notion of refuting are considered. We showthat the corresponding types of learning refutably are of strictly increasing power, where already the most stringent of them turns out to beof remarkable topological and algorithmical richness. All these types areclosed under union, though in different strengths. Also, these types areshown to be different with respect to their intrinsic complexity; two ofthem do not contain function classes that are “most difficult” to learn,
while the third one does. Moreover, we present characterizations for thesetypes of learning refutably. Some of these characterizations make clear
where the refuting ability of the corresponding learning machines comesfrom and how it can be realized, in general.
For learning with anomalies refutably, we show that several results fromstandard learning without refutation stand refutably. Then we derive hierarchies for refutable learning. Finally, we show that stricter refutability
constraints cannot be traded for more liberal learning criteria.

1. Introduction
The basic scenario in learning theory informally consists in that a learning
machine has to learn some unknown object based on certain information, thatis the machine creates one or more hypotheses which eventually converge to amore or less correct and complete description of the object. In learning refutably
the main goal is more involved. Here, for every object from a given universe, the?
??

A full version of this paper is available as technical report (cf. [17]).
Supported in part by NUS grant number RP3992710.

284

Sanjay Jain, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmann

learning machine has either to learn the object or to refute it, that is to “signal”
if it is incapable to learn this object. This approach is philosophically motivatedby Popper’s logic of scientific discovery, (testability, falsifyability, refutability ofscientific hypotheses), see [31, 24]. Moreover, this approach has also some rather
practical implications. If the learning machine signals its inability to learn acertain object, then one can react upon this inability, by modifying the machine,by changing the hypothesis space, or by weakening the learning requirements.
A crucial point of learning refutably is to formally define how the machine isallowed or required to refute a non-learnable object. Mukouchi and Arikawa [29],required refuting to be done in a “one shot” manner, i.e., if after some finite
amount of time, the machine concludes that it cannot learn the target object,then it outputs a special “refuting symbol” and stops the learning process forever. Two weaker possibilities of refuting are based on the following observation.
Suppose that at some time, the machine feels unable to learn the target object
and outputs the refuting symbol. Nevertheless, this time the machine keeps trying to learn the target. It may happen that the information it further receives
contains new evidence causing it to change its mind about its inability to learn
the object. This process of “alternations” can repeat. It may end in learning theobject. Or it may end in refuting it by never revising the machine’s belief thatit cannot learn the object, i.e., by forever outputting the refuting symbol fromsome point on. Finally, there may be infinitely many such alternations between
trying to learn and believing that this is impossible. In our paper, we will allow
and study all three of these modes of learning refutably.
Our universe is the class R of all recursive functions. The basic learning criterion used is Ex, learning in the limit (cf. Definition 1). We study the following
types of learning refutably:
RefEx, where refuting a non-learnable function takes place in the one shotmanner described above (cf. Definition 5).
WRefEx, where both learning and refuting are limiting processes, that is on
every function from the universe, the learning machine converges either to acorrect hypothesis for this function or to the refuting symbol, see Definition 6,(W stands for “weak”).
RelEx, where a function is considered to be refuted if the learner outputs therefuting symbol infinitely often on this function (cf. Definition 7). Rel stands
for “reliable”, since RelEx coincides with reliable learning (cf. Proposition 1).
Note that for all types of learning refutably, every function from R is either
learned or refuted by every machine learning refutably. So, it can not happen thatsuch a machine converges to an incorrect hypothesis (cf. Correctness Lemma).
We show that the types of learning refutably are of strictly increasing power(cf. Theorem 3). Already the most stringent of them, RefEx, is of remarkable
topological and algorithmical richness (cf. Proposition 3 and Corollary 9). All ofthese learning types are closed under union, Proposition 5, where RefEx and
WRefEx, on the one hand, and RelEx, on the other hand, do not behave
completely analogous. Such a difference can also be exhibited with respect toLearning Recursive Functions Refutably

285

the intrinsic complexity; actually, both RefEx and WRefEx do not containfunction classes that are “most difficult” to learn, while RelEx does containsuch classes (cf. Theorems 6 and 7). We also present characterizations for ourtypes of learning refutably. Some of these characterizations make it clear where
the refuting ability of the corresponding learning machines comes from and how
it can be realized, in general (cf. Theorems 12 and 13).
Besides pure Ex-learning refutably we also consider Ex-learning and Bclearning with anomalies refutably (cf. Definitions 18 and 19). We show thatmany results from learning without refutation stand refutably, see Theorems 15
and 21. Then we derive several hierarchies for refutable learning, thereby solving
an open problem from [22], see Corollaries 16 and 22. Finally, we show that, ingeneral, one cannot trade a stricter refutability constraint for a more liberallearning criterion (cf. Corollary 25 and Theorem 26).
Since the pioneering paper [29] learning with refutation has attracted muchattention (cf. [30, 24, 16, 28, 19, 15]).

2. Notation and Preliminaries
Unspecified notations follow [33]. N denotes the set of natural numbers. We
write ∅ for the empty set and card(S) for the cardinality of the set S. The minimum and maximum of a set S are denoted by min(S) and max(S), respectively.
η, with or without decorations ranges over partial functions. If η1 and η2 areboth undefined on input x, then, we take η1 (x) = η2 (x). We say that η1 ⊆ η2
iff for all x in the domain of η1 , η1 (x) = η2 (x). We let dom(η) and rng(η),
respectively, denote the domain and range of the partial function η. η(x)↓ andη(x) =↓ both denote that η(x) is defined and η(x)↑ as well as η(x) =↑ stand forη(x) is undefined. For any partial functions η, η 0 and a ∈ N, we write η =a η 0
and η =∗ η 0 iff card({x | η(x) 6= η 0 (x)}) ≤ a and card({x | η(x) 6= η 0 (x)}) < ∞,respectively. We identify a partial function η with its graph {(x, η(x)) | x ∈dom(η)}.
For r ∈ N, the r-extension of η denotes the function f defined as f (x) = η(x),if x ∈ dom(η) and f (x) = r, otherwise.
R denotes the class of all recursive functions over N. Furthermore, we set
R0,1 = {f | f ∈ R & rng(f ) ⊆ {0, 1}}. C and S, with or without decorations
range over subsets of R. For C ⊆ R, we let C denote R \ C. By P we denotethe class of all partial recursive functions over N. f, g, h and F , with or without
decorations range over recursive functions unless otherwise specified.
A computable numbering (or just numbering) is a partial recursive functionof two arguments. For a numbering ψ(·, ·), we use ψi to denote the function
λx.ψ(i, x), i.e., ψi is the function computed by the program i in the numbering ψ.
ψ and % range over numberings. Pψ denotes the set of partial recursive functionsin the numbering ψ, i.e., Pψ = {ψi | i ∈ N} and Rψ = {ψi | i ∈ N & ψi ∈ R}.
That is, Rψ stands for the set of all recursive functions in the numbering ψ. A
numbering ψ is called one-to-one iff ψi 6= ψj for any distinct i, j. By ϕ we denote

286

Sanjay Jain, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmanna fixed acceptable programming system (cf. [33]). We write ϕi for the partial
recursive function computed by program i in the ϕ-system. By Φ we denote
any Blum [6] complexity measure associated with ϕ. We assume without loss ofgenerality that Φi (x) ≥ x, for all i, x.
C ⊆ R is said to be recursively enumerable (abbr. r.e.) iff there is an r.e. set
X such that C = {ϕi | i ∈ X}. For any r.e. class C =6 ∅, there is an f ∈ R suchthat C = {ϕf (i) | i ∈ N}.
A function g is called accumulation point of a class C ⊆ R iff g ∈ R and(∀n ∈ N)(∃f ∈ C)[(∀x ≤ n)[g(x) = f (x)] & f 6= g]. Note that g may or may notbelong to C. For C ⊆ R, we let Acc(C) = {g | g is an accumulation point of C}.
The quantifier ∀∞ stands for all but finitely many. The following function andclass are considered below. Zero is the everywhere 0 function, and FINSUP ={f | f ∈ R & (∀∞ x)[f (x) = 0]} is the class of all functions of finite support.
2.1. Function Learning
We assume that the graph of a function is fed to a machine in canonicalorder. For a partial function η with η(x)↓ for all x < n, we write η[n] for the set{(x, η(x)) | x < n}, the finite initial segment of η of length n. We set SEG ={f [n] | f ∈ R & n ∈ N} and SEG0,1 = {f [n] | f ∈ R0,1 & n ∈ N}. We let σ, τand γ, with or without decorations range over SEG. Λ is the empty segment.
We assume a computable ordering of the elements of SEG.
Let |σ| denote the length of σ. Thus, |f [n]| = n, for every total function
f and all n ∈ N. If |σ| ≥ n, then we let σ[n] denote {(x, σ(x)) | x < n}. An
inductive inference machine (IIM) M is an algorithmic device that computes
a total mapping from SEG into N (cf. [13]). We say that M(f ) converges to i
(written: M(f )↓ = i) iff (∀∞ n)[M(f [n]) = i]; M(f ) is undefined if no such iexists. Now, we define several criteria of function learning.
Definition 1 ([13, 5, 10]). Let a ∈ N ∪ {∗}, let f ∈ R and let M be an IIM.
(a) M Exa -learns f (abbr. f ∈ Exa (M)) iff there is an i with M(f )↓ = i and
ϕi =a f .
(b) M Exa -learns C iff M Exa -learns each f ∈ C.
(c) Exa = {C ⊆ R | (∃M)[C ⊆ Exa (M)]}.
Note that for a = 0 we omit the upper index, i.e., we set Ex = Ex0 .
By the definition of convergence, only finitely many data of f were seen by
an IIM up to the (unknown) point of convergence. Hence, some learning musthave taken place. Thus, we use identify, learn and infer interchangeably.
Definition 2 ([2, 10]). Let a ∈ N ∪ {∗}, let f ∈ R and let M be an IIM.
(a) M Bca -learns f (written: f ∈ Bca (M)) iff (∀∞ n)[ϕM(f [n]) =a f ].
(b) M Bca -learns C iff M Bca -learns each f ∈ C.
(c) Bca = {C ⊆ R | (∃M)[C ⊆ Bca (M)]}.
We set Bc = Bc0 . Harrington [10] showed that R ∈ Bc∗ . Thus, we shallconsider mainly Bca for a ∈ N in the following.

Learning Recursive Functions Refutably

287

Definition 3 (Minicozzi [27], Blum and Blum [5]). Let M be an IIM.
(a) M is reliable iff for all f ∈ R, M(f )↓ ⇒ M Ex-identifies f .
(b) M RelEx-infers C (written: C ⊆ RelEx(M)) iff M is reliable and M Exinfers C.
(c) RelEx = {C ⊆ R | (∃M)[M RelEx-infers C]}.
Thus, a machine is reliable if it does not converge on functions it fails to
identify. For references on reliable learning besides [27, 5], see [21, 14, 22, 8].
Definition 4. NUM = {C | (∃C 0 | C ⊆ C 0 ⊆ R)[C 0 is recursively enumerable]}.
Inductive inference within NUM has been studied, e.g. in [13, 3]. For thegeneral theory of learning recursive functions, see [1, 5, 10, 11, 23, 18].
2.2. Learning Refutably
Next, we introduce learning with refutation. We consider three versions ofrefutation based on how the machine is required to refute a function. First we
extend the definition of IIM by allowing it to output a special symbol ⊥. Thus,
now an IIM maps SEG to N ∪ {⊥}. Convergence of an IIM on a function isdefined as before (but now a machine may converge to a number i ∈ N or to ⊥).
Definition 5. Let M be an IIM. M RefEx-identifies a class C (written: C ⊆RefEx(M)) iff the following conditions are satisfied.
(a) C ⊆ Ex(M).
(b) For all f ∈ Ex(M), for all n, M(f [n]) 6= ⊥.
(c) For all f ∈ R such that f 6∈ Ex(M), there exists an n ∈ N such that(∀m < n)[M(f [m]) 6= ⊥] and (∀m ≥ n)[M(f [m]) = ⊥].
The following generalization of RefEx places less restrictive constraint on
how the machine refutes a function. WRef below stands for weak refutation.
Definition 6. Let M be an IIM. M WRefEx-learns a class C (written: C ⊆WRefEx(M)) iff the following conditions are satisfied.
(a) C ⊆ Ex(M).
(b) For all f ∈ R such that f 6∈ Ex(M), M(f )↓ = ⊥.
For weakly refuting a function f , an IIM just needs to converge to ⊥. Before
convergence, it may change its mind finitely often whether or not to refute f .
Another way an IIM may refute a function f is to output ⊥ on f infinitely often.
Definition 7. Let M be an IIM. M RelEx0 -identifies a class C (written: C ⊆RelEx0 (M)) iff the following conditions are satisfied.
(a) C ⊆ Ex(M).
(b) For all f ∈ R such that f 6∈ Ex(M), there exists infinitely many n ∈ N suchthat M(f [n]) = ⊥.
Proposition 1. RelEx = RelEx0 .
As it follows from their definitions, for any of the learning types RefEx,
WRefEx and RelEx, we get that any f ∈ R has either to be learned or to be
refuted. This is made formally precise by the following Correctness Lemma.

288

Sanjay Jain, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmann

Lemma 1 (Correctness Lemma). Let I ∈ {RefEx, WRefEx, RelEx}. For
any C ⊆ R, any IIM M with C ⊆ I(M), and any f ∈ R, if M(f )↓ ∈ N, thenϕM(f ) = f .

3. Ex-Learning Refutably
We first derive several properties of the defined types of learning refutably.
We then relate these types by their so-called intrinsic complexity. Finally, we
present several characterizations for refutable learnability.
3.1. Properties and RelationsFirst, we exhibit some properties of refutably learnable classes. These properties imply that the corresponding learning types are of strictly increasing power.
Already the most stringent of these types, RefEx, is of surprising richness. In
particular, every class from RefEx can be enriched by including all of its accumulation points. This is not possible for the classes from WRefEx and RelEx,
as it follows from the proof of Theorem 3.
Proposition 2. For all C ∈ RefEx, C ∪ Acc(C) ∈ RefEx.
Proof. Suppose C ∈ RefEx as witnessed by some total IIM M. Let g ∈ R be an
accumulation point of C. We claim that M must Ex-identify g. Assume to thecontrary that for some n, M(g[n]) = ⊥. Then, by the definition of accumulation
point, there is a function f ∈ C such that g[n] ⊆ f . Hence M(f [n]) = ⊥, too, acontradiction to M RefEx-identifying C.
The next proposition shows that RefEx contains “topologically rich”, namely
non-discrete classes, i.e. classes which contain accumulation points. Thus, RefEx
is “richer” than Ex-learning without any mind change, since any class being
learnable in that latter sense may not contain any of its accumulation points(cf. [25]). More precisely, RefEx and Ex-learning without mind changes are settheoretically incomparable; the missing direction follows from Theorem 14 below.
Proposition 3. RefEx contains non-discrete classes.
The following proposition establishes some bound on the topological richnessof the classes from WRefEx.
Definition 8. A class C ⊆ R is called initially complete iff for every σ ∈ SEG,
there is a function f ∈ C such that σ ⊆ f .
Proposition 4. WRefEx does not contain any initially complete class.
The following result is needed for proving Theorem 3 below.
Lemma 2. C = {f ∈ R | (∀x ∈ N)[f (x) 6= 0]} 6∈ Ex.
We are now ready to prove that RefEx, WRefEx and RelEx, respectively,
are of strictly increasing power.

Learning Recursive Functions Refutably

289

Theorem 3. RefEx ⊂ WRefEx ⊂ RelEx.
Proof. RefEx ⊆ WRefEx ⊆ RelEx by their definitions and Proposition 1.
We first show that WRefEx \ RefEx 6= ∅. For that purpose, we define
SEG+ = {f [n] | f ∈ R & n ∈ N & (∀x ∈ N)[f (x) 6= 0]}. Let C = {0-ext(σ) | σ ∈SEG+ }. Then Acc(C) = {f ∈ R | (∀x ∈ N)[f (x) 6= 0]}, which is not in Ex, byLemma 2. Thus, C ∪ Acc(C) 6∈ Ex, and hence, C ∈/ RefEx, by Proposition 2.
In order to show that C ∈ WRefEx, let prog ∈ R be a recursive function
such that for any σ ∈ SEG+ , prog(σ) is a ϕ-program for 0-ext(σ). Let M be
defined as follows.
 ⊥,if f [n] ∈ SEG+ ;M(f [n]) = prog(σ), if 0-ext(f [n]) = 0-ext(σ), for some σ ∈ SEG+ ;⊥,otherwise.
It is easy to verify that M WRefEx-identifies C.
We now show that RelEx \ WRefEx 6= ∅. FINSUP is initially complete and
FINSUP ∈ NUM. Since NUM ⊆ RelEx, see [27], we have that FINSUP ∈RelEx. On the other hand, FINSUP ∈/ WRefEx by Proposition 4.
As a consequence from the proof of Theorem 3, we can derive that the types
RefEx, WRefEx and RelEx already differ on recursively enumerable classes.
Corollary 4. RefEx ∩ NUM ⊂ WRefEx ∩ NUM ⊂ RelEx ∩ NUM.
We next point out that all the types of learning refutably share a pretty rare,
but desirable property, namely to be closed under union.
Proposition 5. RefEx, WRefEx and RelEx are closed under finite union.
RelEx is even closed under the union of any effectively given infinite sequence of classes (cf. [27]). The latter is not true for both RefEx and WRefEx,
as it can be seen by shattering the class FINSUP into its subclasses of one
element each.
3.2. Intrinsic Complexity
There is another field where RefEx and WRefEx, on the one hand, andRelEx, on the other hand, behave differently, namely that of intrinsic complexity. The intrinsic complexity compares the difficulty of learning by using some
reducibility notion, see [12]. With every reducibility notion comes a notion ofcompleteness. A function class is complete for some learning type I, if this classis “most difficult” to learn among all the classes from I. As we show, RefEx
and WRefEx do not contain such complete classes, while RelEx does.
Definition 9. A sequence P = p0 , p1 , . . . of natural numbers is called Exadmissible for f ∈ R iff P converges to a program p for f .
Definition 10 (Rogers [33]). A recursive operator is an effective total mapping,Θ, from (possibly partial) functions to (possibly partial) functions such that:

290

Sanjay Jain, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmann(a) For all functions η, η 0 , if η ⊆ η 0 then Θ(η) ⊆ Θ(η 0 ).
(b) For all η, if (x, y) ∈ Θ(η), then there is a finite function α ⊆ η such that(x, y) ∈ Θ(α).
(c) For all finite functions α, one can effectively enumerate (in α) all (x, y) ∈Θ(α).
For each recursive operator Θ, we can effectively find a recursive operator Θ0such that(d) for each finite function α, Θ0 (α) is finite, and its canonical index can beeffectively determined from α, and(e) for all total functions f , Θ0 (f ) = Θ(f ).
This allows us to get a nice effective sequence of recursive operators.
Proposition 6. There exists an effective enumeration, Θ0 , Θ1 , · · · of recursive
operators satisfying condition (d) above such that, for all recursive operators Θ,
there exists an i ∈ N satisfying Θ(f ) = Θi (f ) for all total functions f .
Definition 11 (Freivalds et al. [12]). Let S, C ∈ Ex. Then S is called Exreducible to C (written: S ≤Ex C ) iff there exist two recursive operators Θ andΞ such that for all f ∈ S,(a) Θ(f ) ∈ C,(b) for any Ex-admissible sequence P for Θ(f ), Ξ(P ) is Ex-admissible for f .
If S is Ex-reducible to C, then C is at least as difficult to Ex-learn as S
is. Indeed, if M Ex-learns C, then S is Ex-learnable by an IIM that, on any
function f ∈ S, outputs Ξ(M(Θ(f ))).
Definition 12. Let I be a learning type and C ⊆ R. C is called Ex-complete in
I iff C ∈ I, and for all S ∈ I, S ≤Ex C .
Theorem 5. Let C ∈ WRefEx. Then there exists a class S ∈ RefEx such that
S 6≤Ex C.
Theorem 5 immediately yields the following result.
Theorem 6. (1) There is no Ex-complete class in RefEx.
(2) There is no Ex-complete class in WRefEx.
In contrast to Theorem 6, RelEx contains an Ex-complete class.
Theorem 7. There is an Ex-complete class in RelEx.
3.3. Characterizations
We present several characterizations for RefEx, WRefEx and RelEx. The
first group of characterizations relates refutable learning to the established concept of classification. The main goal in recursion theoretic classification can be
described as follows. Let be given some finite (or even infinite) family of function
classes. Then, for an arbitrary function from the union of all these classes, one

Learning Recursive Functions Refutably

291

has to find out which of these classes the corresponding function belongs to,see [4, 37, 35, 34, 9]. What we need in our characterization theorems below will
be classification where only two classes are involved in the classification process, more exactly, a class together with its complement; and semi-classification
which is some weakening of classification. Note that the corresponding characterizations using these kinds of classification are in a sense close to the definitions oflearning refutably. Nevertheless, these characterizations are useful in that theircharacteristic conditions are easily testable, i.e. they allow to check, whether or
not a given class is learnable with refutation.
Let R0,? be the class of all total computable functions mapping N into {0, ?}.
Definition 13. S ⊆ R is finitely semi-classifiable iff there is c ∈ R0,? such that(a) for every f ∈ S, there is an n ∈ N such that c(f [n]) = 0,(b) for every f ∈ S and for all n ∈ N, c(f [n]) = ?.
Intuitively, a class S ⊆ R is finitely semi-classifiable if for every f ∈ S aftersome finite amount of time one finds out that f ∈ S, whereas for every f ∈ S,
one finds out “nothing”.
Theorem 8. For any C ⊆ R, C ∈ RefEx iff C is contained in some classS ∈ Ex such that S is finitely semi-classifiable.
Proof. Necessity. Suppose C ∈ RefEx as witnessed by some total IIM M. Let
S = Ex(M). Clearly, C ⊆ S. Furthermore, (i) for any f ∈ S and any n ∈ N,
M(f [n]) 6= ⊥, and (ii) for any f ∈ S, there is n ∈ N such that M(f [n]) = ⊥.
Now define c as follows.
c(f [n]) =0, if M(f [n]) = ⊥;?, if M(f [n]) 6= ⊥.

Clearly, c ∈ R0,? and S is finitely semi-classifiable by c.
Sufficiency. Suppose C ⊆ S ⊆ Ex(M), and S is finitely semi-classifiable bysome c ∈ R0,? . Now define M0 as follows.
0

M (f [n]) =M(f [n]), if c(f [n]) =?;⊥,if c(f [x]) = 0, for some x ≤ n.

It is easy to verify that M0 RefEx-identifies C.
We can apply the characterization of RefEx above in order to show that
RefEx contains “non-trivial” classes. Therefore, let
C = {f | f ∈ R & ϕf (0) = f & (∀x ∈ N)[Φf (0) (x) ≤ f (x + 1)]}.
Clearly, C ∈ Ex and C is finitely semi-classifiable. Hence, by Theorem 8, C is
RefEx-learnable. C 6∈ NUM was shown in [38], Theorem 4.2. Hence, we get
the following corollary illustrating that RefEx contains “algorithmically rich”
classes, that is classes being not contained in any recursively enumerable class.

292

Sanjay Jain, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmann

Corollary 9. RefEx \ NUM 6= ∅.
We now characterize WRefEx. Therefore, we need the special case of classification where the classes under consideration form a partition of R.
Definition 14 ([37]). (1) Let C, S ⊆ R, where C ∩ S = ∅. (C, S) is calledclassifiable iff there is c ∈ R0,1 such that for any f ∈ C and for almost alln ∈ N, c(f [n]) = 0; and for any f ∈ S and for almost all n ∈ N, c(f [n]) = 1.
(2) A class C ⊆ R is called classifiable iff (C, C) is classifiable.
Theorem 10. For any C ⊆ R, C ∈ WRefEx iff C ⊆ S for a classifiable classS ∈ Ex.
Proof. Necessity. Suppose C ∈ WRefEx as witnessed by some total IIM M. Let
S = Ex(M). Clearly, C ⊆ S and S ∈ Ex. Now define c as follows.
0, if M(f [n]) 6= ⊥;c(f [n]) =1, if M(f [n]) = ⊥.
Then, clearly, S is classifiable by c.
Sufficiency. Suppose C ⊆ S ⊆ Ex(M), and let S be classifiable by somec ∈ R0,1 . Then, define M0 as follows.
M(f [n]), if c(f [n]) = 0
M0 (f [n]) =⊥,if c(f [n]) = 1.
Clearly, M0 witnesses that C ∈ WRefEx.
Finally, we give a characterization of RelEx in terms of semi-classifiability.
Definition 15 ([35]). S ⊆ R is semi-classifiable iff there is c ∈ R0,? such that(a) for any f ∈ S and almost all n ∈ N, c(f [n]) = 0,(b) for any f ∈ S and infinitely many n ∈ N, c(f [n]) = ?.
Thus, a class S of recursive functions is semi-classifiable if for every functionf ∈ S, one can find out in the limit that f belongs to S, while for any g ∈ R \ S
one is not required to know in the limit where this function g comes from.
Theorem 11. For all C ⊆ R, C ∈ RelEx iff C ⊆ S for a semi-classifiable classS ∈ Ex.
Proof. Necessity. Suppose C ∈ RelEx by some total IIM M. Let S = Ex(M).
Clearly, C ⊆ S. In order to show that S is semi-classifiable, define c as follows.
0, if n = 0 or M(f [n − 1]) = M(f [n]);c(f [n]) =?, if n > 0 and M(f [n − 1]) 6= M(f [n]).
Now, for any f ∈ S, M(f )↓, and thus c(f [n]) = 0 for almost all n ∈ N. On
the other hand, if f ∈ S then f ∈/ Ex(M). Consequently, since M is reliable
and total, we have M(f [n − 1]) 6= M(f [n]) for infinitely many n ∈ N. Hencec(f [n]) = ? for infinitely many n. Thus, S is semi-classifiable by c.

Learning Recursive Functions Refutably

293

Sufficiency. Suppose C ⊆ S ⊆ Ex(M). Suppose S be semi-classifiable bysome c ∈ R0,? . Define M0 as follows.
M(f [n]), if c(f [n]) = 0;0
M (f [n]) =n,if c(f [n]) = ?.
Now, for any f ∈ S, for almost all n, c(f [n]) = 0. Hence M0 will Ex-learn f , since
M does so. If f ∈ S, then c(f [n]) = ? for infinitely many n. Consequently, M0
diverges on f caused by arbitrarily large outputs. Thus, M0 RelEx-learns C.
There is a kind of “dualism” in the characterizations of RefEx and RelEx.
A class is RefEx-learnable if it is contained in some Ex-learnable class having
a complement that is finitely semi-classifiable. In contrast, a class is RelExlearnable if it is subset of an Ex-learnable class that itself is semi-classifiable.
The characterizations of the second group, this time for RefEx and RelEx,
significantly differ from the characterizations presented above in two points.
First, the characteristic conditions are stated here in terms that formally havenothing to do with learning. Second, the sufficiency proofs are again constructive
and they make clear where the “refuting ability” of the corresponding learning
machines in general comes from. For stating the corresponding characterizationof RefEx, we need the following notions.
Definition 16. A numbering ψ is strongly one-to-one iff there is a recursivefunction d: N × N → N such that for all i, j ∈ N, i 6= j, there is an x < d(i, j)with ψi (x) 6= ψj (x).
Any strongly one-to-one numbering is one-to-one. Moreover, given any distinct ψ-indices i and j, the functions ψi and ψj do not only differ, but one cancompute a bound on the least argument on which these functions differ.
Definition 17 ([32]). A class Π ⊆ P is called completely r.e. iff {i | ϕi ∈ Π }is recursively enumerable.
Now, we can present our next characterization.
Theorem 12. For any C ⊆ R, C ∈ RefEx iff there are numberings ψ and %such that(1) ψ is strongly one-to-one and C ⊆ Pψ ,(2) P% is completely r.e. and R% = Rψ .
By the proof of Theorem 12, in RefEx-learning the processes of learning andrefuting, respectively, can be nicely separated. An IIM can be provided with two
spaces, one for learning, ψ, and one for refuting, %. If and when the “search forrefutation” in the refutation space has been successful, the learning process canbe stopped forever. This search for refutation is based on the fact that the refutation space forms a completely r.e. class P% of partial recursive functions. The
spaces for learning and refuting are interconnected by the essential property
that their recursive kernels, Rψ and R% , disjointly exhaust R. This property
guarantees that each recursive function either will be learned or refuted. The

294

Sanjay Jain, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmannabove characterization of RefEx is “more granular” than the one of RefEx by
Theorem 8. The characterization of Theorem 8 requires that one should find out
anyhow if the given function does not belong to the target class. The characterization of Theorem 12 makes precise how this task can be done. Moreover,the RefEx-characterization of Theorem 12 is incremental to a characterizationof Ex, since the existence of a numbering with condition (1) above is necessary
and sufficient for Ex-learning the class C (cf. [36]). Finally, the refutation space
could be “economized” in the same manner as the learning space by making it
one-to-one.
The following characterization of RelEx is a slight modification of a result
from [20].
Theorem 13. For any C ⊆ R, C ∈ RelEx iff there are a numbering ψ and afunction d ∈ R such that(1) for any f ∈ R, if Hf = {i | f [d(i)] ⊆ ψi } is finite, then Hf contains aψ-index of f ,(2) for any f ∈ C, Hf is finite.
Theorem 13 instructively clarifies where the ability to learn reliably may comefrom. Mainly, it comes from the properties of a well-chosen space of hypotheses.
In any such space ψ exhibited by Theorem 13, for any function f from the class
to be learned, there are only finitely many “candidates” for ψ-indices of f , the set
Hf . This finiteness of Hf together with the fact that Hf then contains a ψ-index
of f , make sure that the amalgamation technique [10] succeeds in learning any
such f . Conversely, the infinity of this set Hf of candidates automatically ensuresthat the learning machine as defined in the sufficiency proof of Theorem 13
diverges on f . This is achieved by causing the corresponding machine to output
arbitrarily large hypotheses on every function f ∈ R with Hf being infinite.

4. Exa -Learning and Bca -Learning Refutably
In this section, we consider Ex-learning and Bc-learning with anomalies
refutably. Again, we will derive both strengths and weaknesses of refutable learning. As it turns out, many results of standard learning, i.e. without refutation,
stand refutably. This yields several hierarchies for refutable learning. Furthermore, we show that in general one cannot trade the strictness of the refutability
constraints for the liberality of the learning criteria.
We can now define IExa and IBca for I ∈ {Ref , WRef , Rel} analogously
to Definitions 5, 6, and 7. We only give the definitions of Ref Exa and RelBca
as examples.
Definition 18. Let a ∈ N ∪ {∗} and let M be an IIM. M Ref Exa -learns C iff(a) C ⊆ Exa (M).
(b) For all f ∈ Exa (M), for all n, M(f [n]) 6= ⊥.
(c) For all f ∈ R such that f ∈/ Exa (M), there exists an n ∈ N such that(∀m < n)[M(f [m]) 6= ⊥] and (∀m ≥ n)[M(f [m]) = ⊥].

Learning Recursive Functions Refutably

295

Definition 19 ([22]). Let a ∈ N ∪ {∗} and let M be an IIM. M RelBca -learnsC iff(a) C ⊆ Bca (M).
(b) For all f ∈ R such that f ∈/ Bca (M), there exist infinitely many n ∈ N suchthat M(f [n]) = ⊥.
RelExa and RelBca were studied firstly in [21] and [22], respectively.
Our first result points out some weakness of learning refutably. It shows that
there are classes which, on the one hand, are easy to learn in the standard senseof Ex-learning without any mind change, but, on the other hand, which are
not learnable refutably, even if we allow both the most liberal type of learning
refutably, namely reliable learning, and the very rich type of Bc-learning withan arbitrarily large number of anomalies. For proving this result, we need thefollowing proposition.
Proposition 7. (a) For any a ∈ N and any σ ∈ SEG, {f ∈ R | σ ⊆ f } 6∈ Bca .
(b) For any a ∈ N and any σ ∈ SEG0,1 , {f ∈ R0,1 | σ ⊆ f } 6∈ Bca .
Next, recall that Ex-learning without mind changes is called finite learning.
Informally, here the learning machine has “one shot” only to do its learning task.
We denote the resulting learning type by Fin.
Theorem 14. For all a ∈ N, Fin \ RelBca 6= ∅.
Next we show that allowing anomalies can help in learning refutably. Indeed,
while Exa+1 \ Exa 6= ∅ was shown in [10], we now strengthen this result to
Ref Ex-learning with anomalies.
Theorem 15. For any a ∈ N, Ref Exa+1 \ Exa 6= ∅.
Theorem 15 implies the following hierarchy results ((3) was already shownin [21]).
Corollary 16. For every a ∈ N,
(1) Ref Exa ⊂ Ref Exa+1 ,(2) WRef Exa ⊂ WRef Exa+1 ,(3) RelExa ⊂ RelExa+1 .
Now a proof similar to the proof
S of Theorem 15 can be used to show thefollowing result. Notice that Ex∗ \ a∈N Exa 6= ∅ was proved in [10].
S
Theorem 17. Ref Ex∗ \ a∈N Exa 6= ∅.
Theorem 15 implies further corollaries. In [10], Ex∗ ⊆ Bc was shown. This
result extends to all our types of refutable learning.
Proposition 8. For I ∈ {Ref , WRef , Rel}, IEx∗ ⊆ IBc.
In [10] it was proved that Bc \ Ex∗ 6= ∅. This result holds refutably.
Corollary 18. Ref Bc \ Ex∗ 6= ∅.
The next corollary points out that already Ref Ex1 contains “algorithmicallyrich” classes of predicates.

296

Sanjay Jain, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmann

Corollary 19. Ref Ex1 ∩ 2R0,1 6⊆ NUM ∩ 2R0,1 .
Corollary 19 can be even strengthened by replacing Ref Ex1 with RefEx.
This another time exhibits the richness of already the most stringent of our typesof learning refutably.
Theorem 20. RefEx ∩ 2R0,1 6⊆ NUM ∩ 2R0,1 .
Note that Theorem 20 contrasts a known result on reliable Ex-learning. If
we require the Ex-learning machine’s reliability not only on R, but even on theset of all total functions, then all classes of recursive predicates belonging to thislatter type are in NUM, see [14].
We now give the analogue to Theorem 15 for Bca -learning rather than Exa learning. Note that Bca+1 \ Bca 6= ∅ was shown in [10].
Theorem 21. For any a ∈ N, Ref Bca+1 \ Bca 6= ∅.
Theorem 21 yields the following hierarchies, where (3) solves an open problem
from [22].
Corollary 22. For every a ∈ N,
(1) Ref Bca ⊂ Ref Bca+1 ,(2) WRef Bca ⊂ WRef Bca+1 ,(3) RelBca ⊂ RelBca+1 .
Theorem 23. Ref Bc∗ \Sa∈N Bca6= ∅.

In the proof of Theorem 3 we have derived that FINSUP 6∈ WRef Ex. This
result is now strengthened for WRef Bca -learning and then used in the nextcorollary below.
Theorem 24. For every a ∈ N, FINSUP 6∈ WRef Bca .
The next corollary points out the relative strength of RelEx-learning over
WRef Bca -learning. In other words, in general, one cannot compensate a stricter
refutability constraint by a more liberal learning criterion.
Corollary 25. For all a ∈ N, RelEx \ WRef Bca 6= ∅.
Our final result exhibits the strength of WRef Ex-learning over Ref Bca learning. Thus, it is in the same spirit as Corollary 25 above.
Theorem 26. For all a ∈ N, WRef Ex \ Ref Bca 6= ∅.
Note that Theorems 14, 24 and 26, and Corollary 25 hold even if we replace
Bca by any criterion of learning for which Proposition 7 holds.

References
1. D. Angluin and C. Smith. Inductive inference: Theory and methods. Computing
Surveys, 15:237–289, 1983.

Learning Recursive Functions Refutably

297

2. J. Bārzdiņš. Two theorems on the limiting synthesis of functions. In Theory of
Algorithms and Programs, Vol. 1, pp. 82–88. Latvian State University, 1974. In
Russian.
3. J. Bārzdiņš and R. Freivalds. Prediction and limiting synthesis of recursively
enumerable classes of functions. Latvijas Valsts Univ. Zimatm. Raksti, 210:101–
111, 1974.
4. S. Ben-David. Can finite samples detect singularities of real-valued functions? In
24th Annual ACM Symposium on the Theory of Computing, pp. 390–399, 1992.
5. L. Blum and M. Blum. Toward a mathematical theory of inductive inference.
Inform. and Control, 28:125–155, 1975.
6. M. Blum. A machine-independent theory of the complexity of recursive functions.
Journal of the ACM, 14:322–336, 1967.
7. J. Case. Periodicity in generations of automata. Mathematical Systems Theory,
8:15–32, 1974.
8. J. Case, S. Jain, and S. Ngo Manguelle. Refinements of inductive inference by
Popperian and reliable machines. Kybernetika, 30:23–52, 1994.
9. J. Case, E. Kinber, A. Sharma, and F. Stephan. On the classification of computablelanguages. In Proc. 14th Symposium on Theoretical Aspects of Computer Science,Vol. 1200 of Lecture Notes in Computer Science, pp. 225–236. Springer, 1997.
10. J. Case and C. Smith. Comparison of identification criteria for machine inductive
inference. Theoretical Computer Science, 25:193–220, 1983.
11. R. Freivalds. Inductive inference of recursive functions: Qualitative theory. In
Baltic Computer Science, Vol. 502 of Lecture Notes in Computer Science, pp. 77–
110. Springer, 1991.
12. R. Freivalds, E. Kinber, and C.H. Smith. On the intrinsic complexity of learning.
Information and Computation, 123(1):64–71, 1995.
13. E.M. Gold. Language identification in the limit. Inform. and Control, 10:447–474,
1967.
14. J. Grabowski. Starke Erkennung. In Strukturerkennung diskreter kybernetischer
Systeme, Teil I, pp. 168–184. Seminarbericht Nr. 82, Department of Mathematics,
Humboldt University of Berlin, 1986.
15. G. Grieser. Reflecting inductive inference machines and its improvement by therapy. In Algorithmic Learning Theory: 7th International Workshop (ALT ’96), Vol.
1160 of Lecture Notes in Artificial Intelligence, pp. 325–336. Springer, 1996.
16. S. Jain. Learning with refutation. Journal of Computer and System Sciences,
57(3):356–365, 1998.
17. S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann. Refutable inductive inferenceof recursive functions. Schriftenreihe der Institute für Informatik/Mathematik,
Serie A, SIIM-TR-A-01-06, Medical University at Lübeck, 2001.
18. S. Jain, D. Osherson, J.S. Royer, and A. Sharma. Systems that Learn: An Introduction to Learning Theory. MIT Press, Cambridge, Mass., second edition, 1999.
19. K. P. Jantke. Reflecting and self-confident inductive inference machines. In Algorithmic Learning Theory: 6th International Workshop (ALT ’95), Vol. 997 of
Lecture Notes in Artificial Intelligence, pp. 282–297. Springer, 1995.
20. W. Jekeli. Universelle Strategien zur Lösung induktiver Lernprobleme. MSc Thesis,
Dept. of Computer Science, University of Kaiserslautern, 1997.
21. E.B. Kinber and T. Zeugmann. Inductive inference of almost everywhere correct
programs by reliably working strategies. Journal of Information Processing andCybernetics (EIK), 21:91–100, 1985.

298

Sanjay Jain, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmann

22. E. Kinber and T. Zeugmann. One-sided error probabilistic inductive inference andreliable frequency identification. Information and Computation, 92(2):253–284,
1991.
23. R. Klette and R. Wiehagen. Research in the theory of inductive inference by GDR
mathematicians – A survey. Information Sciences, 22:149–169, 1980.
24. S. Lange and P. Watson. Machine discovery in the presence of incomplete or
ambiguous data. In Algorithmic Learning Theory: 4th International Workshop on
Analogical and Inductive Inference (AII ’94) and 5th International Workshop on
Algorithmic Learning Theory (ALT ’94), Vol. 872 of Lecture Notes in Artificial
Intelligence, pp. 438–452. Springer, 1994.
25. R. Lindner. Algorithmische Erkennung. Dissertation B, University of Jena, 1972.
26. M. Machtey and P. Young. An Introduction to the General Theory of Algorithms.
North Holland, New York, 1978.
27. E. Minicozzi. Some natural properties of strong identification in inductive inference. Theoretical Computer Science, 2:345–360, 1976.
28. T. Miyahara. Refutable inference of functions computed by loop programs. Technical Report RIFIS-TR-CS-112, Kyushu University, Fukuoka, 1995.
29. Y. Mukouchi and S. Arikawa. Inductive inference machines that can refute hypothesis spaces. In Algorithmic Learning Theory: 4th International Workshop (ALT’93), Vol. 744 of Lecture Notes in Artificial Intelligence, pp. 123–136. Springer,
1993.
30. Y. Mukouchi and S. Arikawa. Towards a mathematical theory of machine discovery
from facts. Theoretical Computer Science, 137:53–84, 1995.
31. K. R. Popper. The Logic of Scientific Discovery. Harper and Row, 1965.
32. H. Rice. On completely recursively enumerable classes and their key arrays. The
Journal of Symbolic Logic, 21:304–308, 1956.
33. H. Rogers. Theory of Recursive Functions and Effective Computability. McGrawHill, 1967. Reprinted by MIT Press in 1987.
34. C.H. Smith, R. Wiehagen, and T. Zeugmann. Classifying predicates and languages.
International Journal of Foundations of Computer Science, 8(1):15–41, 1997.
35. F. Stephan. On one-sided versus two-sided classification. Technical Report
Forschungsberichte Mathematische Logik 25/1996, Mathematical Institute, University of Heidelberg, 1996.
36. R. Wiehagen. Characterization problems in the theory of inductive inference. In
Proc. of the 5th International Colloquium on Automata, Languages and Programming, Vol. 62 of Lecture Notes in Computer Science, pp. 494–508. Springer, 1978.
37. R. Wiehagen and C.H. Smith. Generalization versus classification. Journal of
Experimental and Theoretical Artificial Intelligence, 7:163–174, 1995.
38. T. Zeugmann. A-posteriori characterizations in inductive inference of recursivefunctions. J. of Inform. Processing and Cybernetics (EIK), 19:559–594, 1983.