On Learning of Functions Refutably

Sanjay Jain a,1 Efim Kinber b Rolf Wiehagen c
Thomas Zeugmann da School of Computing, National University of Singapore, Singapore 119260,

Singapore, Email:sanjay@comp.nus.edu.sg
b Department of Computer Science, Sacred Heart University, Fairfield, CT

06432-1000, U.S.A., Email: kinbere@sacredheart.edu
c Department of Computer Science, University of Kaiserslautern, D-67653

Kaiserslautern, Germany, Email: wiehagen@informatik.uni-kl.ded Medizinische Universität Lübeck, Institut für Theoretische Informatik, Wallstraße

40, 23560 Lübeck, Germany, Email: thomas@tcs.mu-luebeck.de

Abstract
Learning of recursive functions refutably informally means that for every recursivefunction, the learning machine has either to learn this function or to refute it, thatis to signal that it is not able to learn it. Three modi of making precise the notion of
refuting are considered. We show that the corresponding types of learning refutably
are of strictly increasing power, where already the most stringent of them turns
out to be of remarkable topological and algorithmical richness. Furthermore, allthese types are closed under union, though in different strengths. Also, these types
are shown to be different with respect to their intrinsic complexity; two of them
do not contain function classes that are “most difficult” to learn, while the third
one does. Moreover, we present several characterizations for these types of learning
refutably. Some of these characterizations make clear where the refuting ability of
the corresponding learning machines comes from and how it can be realized, ingeneral.
For learning with anomalies refutably, we show that several results from standard
learning without refutation stand refutably. From this we derive some hierarchies
for refutable learning. Finally, we prove that in general one cannot trade stricter
refutability constraints for more liberal learning criteria.

1

Supported in part by NUS grant number R252-000-127-112.

Preprint submitted to Elsevier

25 September 2002

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 toa more 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 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 isphilosophically motivated by Popper’s logic of scientific discovery (testability,
falsifyability, refutability of scientific hypotheses), see [33] and [25], for a moredetailed discussion. Moreover, this approach has also some rather practical
implications. Indeed, if the learning machine informs a user of its inability tolearn a certain object, then the user can react upon this inability, by modifying the machine, by changing the space of hypotheses, or by weakening thelearning requirements, for example.
A crucial point of learning refutably is to formally define how the machine isallowed or required to refute a non-learnable object. In the ground-breaking
paper by Mukouchi and Arikawa [30] it is required that refuting takes place ina “one shot” manner, that is, if after some finite amount of time, the machinecomes to the conclusion that it is not able to learn the object under consideration, 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 theunknown object and signals this by outputting the refuting symbol. Nevertheless, this time the machine keeps trying to learn this object. It may happen
that the information it further receives contains a new evidence which leads
to changing its mind about its inability to learn the object. Of course, thisprocess of “alternations” can repeat. And it may end in learning the object. Or
it may end in refuting it by never revising the machine’s belief in its inability
to learn the object, or, equivalently, by forever outputting the refuting symbolfrom some point on. Or, 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, i.e., all computablefunctions being defined everywhere. The basic learning criterion used will be
Ex, learning in the limit, see Definition 1. We then consider the following
types of learning refutably:
RefEx, where refuting a non-learnable function takes place in the one shotmanner described above (cf. Definition 5).
2

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 as being refuted if the learning machine
outputs the refuting symbol infinitely often on this function, see Definition 7,(Rel stands for “reliable”, since this type coincides with so-called reliable
learning, as we shall see below).
As it immediately follows from the definitions of all these types of learning
refutably, every function from our universe will indeed either be learned or
be refuted by every machine that learns refutably. In other words, it can
not happen that such a machine converges to an incorrect hypothesis, see
Correctness Lemma below. Thus, this lemma can be viewed as a justification
for the above approaches of refutable learning.
We then show that these types of learning refutably are of strictly increasing
power, see Theorem 16. Already the most stringent of them, RefEx, turns out
to be of remarkable topological and algorithmical richness (cf. Proposition 11
and Corollary 30). Furthermore, all of these learning types are closed underunion, Proposition 18, where RefEx and WRefEx, on the one hand, andRelEx, on the other hand, do not behave completely analogous. Such a difference can also be exhibited with respect to the so-called intrinsic complexity;
actually, both RefEx and WRefEx do not contain function classes that are“most difficult” to learn, while RelEx does contain such classes, see Theorems 26 and 27, respectively. Moreover, we present several characterizations
for our types of learning refutably. Specifically, some of these characterizations
make it clear where the refuting ability of the corresponding learning machinescomes from and how it can be realized, in general (cf. Theorems 39 and 44).
Besides pure Ex-learning refutably we also consider Ex-learning with anomalies as well as Bc-learning with anomalies refutably (cf. Definitions 49 and 50).
We show that many results from standard learning without refutation standrefutably. From this we derive several hierarchies for refutable learning, thereby
solving an open problem from [22], see Corollaries 56 and 67. Moreover, we
prove that, in general, one cannot trade a stricter refutability constraint for amore liberal learning criterion (cf. Corollary 71 and Theorem 72).
Since the pioneering paper [30] learning with refutation has attracted muchattention. The line initiated by [30], i.e., studying learning with refutation forindexed families of languages, was also applied to learning of elementary formal systems in [31]. As a consequence of this model, if an indexed family ofrecursive languages can be refutably learned from text then this class cannot
contain any infinite language. This limitation led Lange and Watson [25] to
3consider a more tolerant approach. In their model a refuting learning machine
is no longer required to refute every text describing a language outside theclass to be learned. Instead, the machine has to refute only such texts containing a finite sample being not contained in any language from the class
to be learned. This indeed leads to a richer spectrum of indexed families ofrecursive languages that are learnable with so-called justified refutation. Jain
[18] then generalized the study in two directions. First, classes of arbitrary
recursively enumerable languages were considered. Second, the learning machine was allowed either to refute or to learn unrepresentative texts. For anatural interpretation of “unrepresentative”, the power of the justified refutation model has been shown to reach the power of the unrestricted model oflearning languages from text.
Learning functions with refutation was considered by Miyahara [29] for indexed classes of primitive recursive fuctions. For arbitrary classes of arbitrary
recursive functions, an alternative approach has been developed and studied by Jantke [20] and Grieser [17]. In a sense, their approach is orthogonal toours. Actually, on the one hand, their model allows to learn richer classes thanwe can. On the other hand, in certain cases every machine that learns sucha richer class converges to incorrect hypotheses on infinitely many functions
outside this class, whereas in our approach the Correctness Lemma guarantees
that no machine converges incorrectly on whatever function from the universe.
The paper is organized as follows. Section 2 provides the necessary notations
and definitions, as well as the Correctness Lemma. Section 3 deals with Exlearning refutably. In Section 4, we consider Ex- and Bc-learning with anomalies refutably.

2

Notation and Preliminaries

Recursion-theoretic concepts not explained below are treated in [35]. N denotes. j is defined as follows:
the set of natural numbers. Furthermore, i −
. j=
i−



i − j, if i ≥ j;0,otherwise.

Let ∈, ⊆, ⊂, ⊇, ⊃, respectively, denote the membership, subset, proper subset, superset and proper superset relations for sets. The empty set is denotedby ∅. We let card(S) denote the cardinality of the set S. The minimum andmaximum of a set S are denoted by min(S) and max(S), respectively. We takemax(∅) to be 0 and min(∅) to be ∞.
4h·, ·i denotes a 1-1 computable mapping from pairs of natural numbers onto
N. π1 , π2 are the corresponding projection functions. h·, ·i is extended to ntuples of natural numbers in a natural way. η, with or without subscripts,
superscripts, primes and the like, ranges over partial functions. If η1 and η2are both 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 domain(η) andrange(η), 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. We identify a partial function η with its
graph {(x, η(x)) | x ∈ domain(η)}.
For r ∈ N, the r-extension of η denotes the function f defined as follows:f (x) =

η(x), if x ∈ domain(η);
r,otherwise.

We write r-ext(η) for the r-extension of η. R denotes the class of all recursivefunctions, i.e., total computable functions with arguments and values from N.
By R0,1 we denote the class of all recursive functions with range contained in{0, 1}. C and S, with or without subscripts, superscripts, primes and the like,range over subsets of R. For C ⊆ R, we let C denote R \ C. P denotes theclass of all partial recursive functions over N. f, g, h and F , with or without
subscripts, superscripts, primes and the like, 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). In other words, ψi is the function computed by the program iin the numbering ψ. ψ and % range over numberings. Pψ denotes the set ofpartial recursive functions in the numbering ψ, i.e., Pψ = {ψi | i ∈ N}. We set
Rψ = {ψi | i ∈ N & ψi ∈ R}. That is, Rψ stands for the set of all recursivefunctions in the numbering ψ. A numbering ψ is called one-to-one iff ψi 6= ψj
for any distinct i, j. Hence, for any η ∈ Pψ , there is exactly one ψ-index isuch that ψi = η. ϕ denotes a fixed acceptable programming system (cf. [35]).
We write ϕi for the partial recursive function computed by program i in theϕ-system. We let Φ be an arbitrary Blum [6] complexity measure associatedwith the acceptable programming system ϕ; many such measures exist for any
acceptable programming system. We assume without loss of generality thatΦi (x) ≥ x, for all i, x. ϕi,s is defined as follows:

ϕi,s (x) =ϕi (x), if x < s and Φi (x) < s;↑,otherwise.

A class C ⊆ R is said to be recursively enumerable iff there exists an r.e. set
X such that C = {ϕi | i ∈ X}. For any non-empty recursively enumerable
5

class C, there exists a recursive function f such that C = {ϕf (i) | i ∈ N}.
A function g is said to be an 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 theaccumulation point may or may not belong to the class. For C ⊆ R, we let
Acc(C) = {g | g is an accumulation point of C}.
The quantifier ∀∞ denotes for all but finitely many; that is, (∀∞ x)[P (x)] meanscard({x | ¬P (x)}) < ∞. The following functions and classes are commonly
considered below. Zero is the everywhere 0 function, i.e., Zero(x) = 0, for allx ∈ N. FINSUP = {f | (∀∞ x)[f (x) = 0]} denotes the class of all recursivefunctions of finite support.
2.1

Function Identification

We first describe inductive inference machines. We assume, that the graph ofa function is fed to a machine in canonical order.
For a partial function η such that η(x) is defined for all x < n, we write
η[n] for the set {(x, η(x)) | x < n}, the finite initial segment of η of length n.
Clearly, η[0] denotes the empty segment. SEG denotes the set of all finite initial
segments, i.e., {f [n] | f ∈ R & n ∈ N}. Furthermore, we set SEG0,1 = {f [n] |f ∈ R0,1 & n ∈ N}. We let σ, τ and γ, with or without subscripts, superscripts,
primes and the like, range over SEG. Λ denotes the empty segment. We assume
some computable ordering of elements of SEG. Thus, one can talk about
recursively enumerable subsets of SEG and comparison among members of
SEG, that is σ < τ , if σ appears before τ in this ordering. Similary one cantalk about the least element of a subset of SEG.
Let |σ| denote the length of σ. Thus, |f [n]| = n, for every total function fand all n ∈ N. If |σ| ≥ n, then we let σ[n] denote {(x, σ(x)) | x < n}. An
inductive inference machine (IIM) is an algorithmic device that computes a
total mapping from SEG into N (cf. [15]). Since the set of all finite initial
segments, SEG, can be coded onto N, we can view these machines as taking
natural numbers as input and emitting natural numbers as output. We saythat M(f ) converges to i (written: M(f )↓ = i) iff (∀∞ n)[M(f [n]) = i]; M(f )is undefined if no such i exists. The next definitions describe several criteria
of function identification.
Definition 1 (Gold [15]). Let f ∈ R and let M be an IIM.
(a) M Ex-identifies f (written: f ∈ Ex(M)) just in case there exists ani ∈ N such that M(f )↓ = i and ϕi = f .
(b) M Ex-identifies C iff M Ex-identifies each f ∈ C.
(c) Ex = {C ⊆ R | (∃M)[C ⊆ Ex(M)]}.
6

By the definition of convergence, only finitely many data points from a function
f have been observed by an IIM M at the (unknown) point of convergence.
Hence, some form of learning must take place in order for M to learn f . For thisreason, hereafter the terms identify, learn and infer are used interchangeably.
Definition 2 (Bārzdiņš [2], Case and Smith [10]). Let f ∈ R and let M
be an IIM.
(a) M Bc-identifies f (written: f ∈ Bc(M)) iff, for all but finitely manyn ∈ N, M(f [n]) is a program for f , i.e., ϕM(f [n]) = f .
(b) M Bc-identifies C iff M Bc-identifies each f ∈ C.
(c) Bc = {C ⊆ R | (∃M)[C ⊆ Bc(M)]}.
Definition 3 (Minicozzi [28], 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-identifies C (written: C ⊆ RelEx(M)) iff M is reliable and M
Ex-identifies C.
(c) RelEx = {C ⊆ R | (∃M)[M RelEx-identifies C]}.
Thus, intuitively, a machine is reliable if it does not converge on functions it
fails to identify. For further references on reliable learning besides [28,5], see[23,16,22,41,8].
Definition 4 NUM = {C | (∃C 0 | C ⊆ C 0 ⊆ R)[C 0 is recursively enumerable]}.
For references on inductive inference within NUM, the set of all recursively
enumerable classes and their subclasses, the reader is referred to [15,3,12]. For
references surveying the general theory of learning recursive functions, we refer
the reader to [1,5,10,11,24,32,19].

2.2

Learning Refutably

In this subsection we introduce learning with refutation. The idea is that thelearning machine should “refute” functions which it does not identify. We
consider three versions of refutation based on how the machine is required torefute a function. First we need to extend the definition of IIM to allow amachine to output a special symbol ⊥. Thus, now an IIM is a mapping from
SEG to N∪{⊥}. Convergence of an IIM on a function can be defined as before(where a machine may now converge to a natural number 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= ⊥.
7(c) For all f ∈ R such that f 6∈ Ex(M), there exists an n such that (∀m <n)[M(f [m]) 6= ⊥] and (∀m ≥ n)[M(f [m]) = ⊥].
Intuitively, for RefEx-identification, the IIM M outputs the special symbol⊥ on input function f to indicate that it is not going to Ex-identify f .
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-identifies 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, the machine just needs to converge to therefutation symbol ⊥. Before convergence, it may change its mind finitely manytimes whether or not it is going to refute the function.
There is another possible way a machine may refute a function f , i.e., it
outputs ⊥ on f infinitely often. This version actually turns out to be equivalent
to RelEx-learning considered above.
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 exist infinitely many n suchthat M(f [n]) = ⊥.
Proposition 8 RelEx = RelEx0 .
Proof. We first show that RelEx ⊆ RelEx0 .
Suppose M RelEx-identifies C. Define M0 as follows:0

M (f [n]) =M(f [n]), if n = 0 or M(f [n − 1]) = M(f [n]);⊥,otherwise.

It is easy to verify that M0 RelEx0 -identifies C.
We now show that RelEx0 ⊆ RelEx. Suppose M RelEx0 -identifies C. Define
M0 as follows:0

M (f [n]) =M(f [n]), if M(f [n]) 6= ⊥;n,otherwise.

It is easy to verify that M0 Ex-identifies each f Ex-identified by M. Also, if
M outputs ⊥ on f infinitely often, then M(f )↑, since it outputs arbitrarily8large numbers on f . It follows that M0 RelEx-identifies C.

As it immediately follows from their definitions, for any of the learning types
RefEx, WRefEx and RelEx, we get that any recursive function has either tobe learned or to be refuted. We make this point formally precise by stating thefollowing Correctness Lemma. Informally, this lemma says that for every typeof learning refutably and for every machine that learns in the corresponding
sense, one can trust in the correctness of every hypothesis from N the machine
may converge to.
Lemma 9 (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 .
Proof. We prove the lemma here for RefEx. The remaining cases can be handled analogously. Let C ⊆ R and let M be any IIM such that C ⊆ RefEx.
Furthermore, let f ∈ R and assume that M(f )↓ ∈ N. Thus, we can conclude that f ∈ Ex(M). Otherwise condition (c) in Definition 5 must have
happened, and hence M (f [m]) = ⊥ for all but finitely many m, a contradiction to M(f )↓ ∈ N. Finally, by Definition 1, part (a), we directly obtainϕM(f ) = f .
Using essentially the idea from Gold [14], (for Ex-identification), for I being
any of the learning criteria considered in this paper, one can show that:
There exists an r.e. sequence M0 , M1 , M2 , . . . of total inductive inferencemachines such that, for all C ∈ I, there exists an i ∈ N such that C ⊆ I(Mi ).
In the following, we assume M0 , M1 , M2 , . . . to be one such sequence of machines.

3

Ex-Learning Refutably

In this section, we first derive several properties of the types of learning
refutably defined above. We then relate these types by their so-called intrinsic
complexity. Finally, we present several characterizations for refutable learnability.
93.1

Properties and Relations

We start with exhibiting some properties of the classes being learnable refutably. Specifically, these properties imply that the corresponding learning types
are of strictly increasing power, where already the most stringent of thesetypes, RefEx, turns out to be of surprising richness. The first of these properties consists in that any class from RefEx can be enriched by including allof its accumulation points. Note that, in general, this is not possible for theclasses from WRefEx and RelEx, as it immediately follows from the proofof Theorem 16.
Proposition 10 For any C ∈ RefEx, C ∪ Acc(C) ∈ RefEx.
Proof. Informally, the result follows from the fact that in any type of refutablelearning, any function f ∈ R, will either be identified or refuted. Since in
RefEx-learning an accumulation point can never be refuted, it has to belearned. Formally, 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 the contrary that for some n, M(g[n]) = ⊥. Then, by the definitionof accumulation point, there is a function f ∈ C such that g[n] ⊆ f . Hence
M(f [n]) = ⊥, too, a contradiction 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 usual Ex-learning without any mind change, since
any class being learnable in that latter sense may not contain any of its accumulation points (cf. [26]). More precisely, RefEx and Ex-learning without
mind changes are set-theoretically incomparable; the missing direction easily
follows from Theorem 53 below.
Proposition 11 RefEx contains non-discrete classes.
Proof. For i ∈ N, define fi as follows.


fi (x) =0, if x < i;1, otherwise.

Let C = {fi | i ∈ N} ∪ {Zero}. Then, clearly, C is non-discrete and RefExlearnable.
The following proposition establishes some bound on the topological richnessof the classes from WRefEx.
Definition 12 A class C ⊆ R is called initially complete iff for every σ ∈10SEG, there is a function f ∈ C such that σ ⊆ f .
Proposition 13 WRefEx does not contain any initially complete class.
Proof. Assume to the contrary that there is an initially complete class C that
is WRefEx-learnable by some total IIM M.
Claim 14 For all σ ∈ SEG, there exists a τ ∈ SEG such that σ ⊆ τ , andM(σ) 6= M(τ ).
Proof. If for all extensions τ of σ, M(σ) = M(τ ), then M can Ex-identify atmost one extension of σ. But then C is not initially complete. 2
Now, let σi , i ∈ N, be defined such that σi can be obtained effectively fromi, σ0 = Λ, and for all i, σi ⊆ σi+1 and M(σi ) 6= M(σi+1 ). Note that this isSpossible due to Claim 14. Now let f = i∈N σi . Clearly, f ∈ R, but M onf makes infinitely many mind changes. Thus, M neither Ex-identifies, nor
refutes f . Thus, M does not WRef -identify C.

The following result is needed for proving Theorem 16 below.
Lemma 15 C = {f ∈ R | (∀x ∈ N)[f (x) 6= 0]} 6∈ Ex.
Proof. Suppose by way of contradiction M Ex-identifies C. For any σ ∈ SEG,
let τσ be defined as follows:τσ (x) =σ(x) + 1, if σ(x)↓;↑,otherwise.

Let prog be a recursive function such that, for any program p, ϕprog(p) (x) =. 1. Note that by the s-m-n theorem, there exists such a recursiveϕp (x) −function prog. Now define M0 (σ) = prog(M(τσ )).
It is easy to verify that if M Ex-identifies C, then M0 Ex-identifies R. However,R 6∈ Ex, see [15]. Thus C 6∈ Ex.
We are now ready to prove that RefEx, WRefEx and RelEx, respectively,
are of strictly increasing power.
Theorem 16 RefEx ⊂ WRefEx ⊂ RelEx.
Proof. RefEx ⊆ WRefEx ⊆ RelEx follows easily from the definitions andProposition 8.
11

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 = {0ext(σ) | σ ∈ SEG+ }. Then Acc(C) = {f ∈ R | (∀x ∈ N)[f (x) 6= 0]}, which is
not in Ex, by Lemma 15. Thus, C ∪ Acc(C) 6∈ Ex, and hence, C ∈/ RefEx, by
Proposition 10.
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= ∅. Clearly, FINSUP is initially complete and FINSUP ∈ NUM. Since NUM ⊆ RelEx, see [28], we have that
FINSUP ∈ RelEx. On the other hand, FINSUP ∈/ WRefEx by Proposition 13.
As a consequence from the proof of Theorem 16, we can derive that the types
RefEx, WRefEx and RelEx already differ on recursively enumerable classes.
Corollary 17 RefEx ∩ NUM ⊂ WRefEx ∩ NUM ⊂ RelEx ∩ NUM.
Proof. Immediately from the proof of Theorem 16.

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 18 RefEx, WRefEx and RelEx are closed under union.
Proof. In [28] it was shown that RelEx is closed under union. Now, supposeI ∈ {RefEx, WRefEx}, C ⊆ I(M0 ) and S ⊆ I(M00 ). Then, define an IIM M
as follows.
M(f [n]) =M0 (f [n]), if M0 (f [n]) 6= ⊥;M00 (f [n]), otherwise.

Thus, informally, M simulates the first machine that currently does not refute
the given function. It is easy to verify that C ∪ S ⊆ I(M).
12Proposition 18 obviously applies also to the union of any finite number ofclasses. RelEx is even closed under the union of any effectively given infinite
sequence of classes, see [28]. However, 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 [13]. As usual, with every reducibility notion
comes a notion of completeness. Intuitively, a function class is complete forsome learning type, if this class is “most difficult” to learn among all the classes
from this learning type. As we will show, the types RefEx and WRefEx do
not contain such complete classes, while RelEx does. We now proceed moreformally.
Definition 19 A sequence P = p0 , p1 , . . . of natural numbers is called Exadmissible for f ∈ R iff P converges to a program p for f .
Definition 20 (Rogers [35]). A recursive operator is an effective total mapping, Θ, from (possibly partial) functions to (possibly partial) functions, which
satisfies the following properties:(a) Monotonicity: For all functions η, η 0 , if η ⊆ η 0 then Θ(η) ⊆ Θ(η 0 ).
(b) Compactness: For all η, if (x, y) ∈ Θ(η), then there exists a finite functionα ⊆ η such that (x, y) ∈ Θ(α).
(c) Recursiveness: For all finite functions α, one can effectively enumerate(in α) all (x, y) ∈ Θ(α).
For each recursive operator Θ, we can effectively (from Θ) find a recursive
operator Θ0 such 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 21 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 .
13

Definition 22 (Freivalds et al. [13]). 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 .
Intuitively, if S is Ex-reducible to C, then C is at least as difficult to Ex-learn
as S is. Actually, if M Ex-learns C, then S can be Ex-learned by a machine
that, on any function f ∈ S, outputs the sequence Ξ(M(Θ(f ))).
Definition 23 Let I be a learning type and C ⊆ R. C is called Ex-completein I iff C ∈ I, and for all S ∈ I, S ≤Ex C .
Theorem 24 Let C ∈ WRefEx. Then there exists a class S ∈ RefEx suchthat S 6≤Ex C.
Proof. Suppose C ∈ WRefEx as witnessed by M. Note that for all recursivefunctions f , M(f ) converges to a program for f , or converges to ⊥. In particular, there is no recursive function f on which M makes infinitely many mindchanges. Based on this we define a class S ∈ RefEx that is not Ex-reducible
to C. Let Θ0 , Θ1 , . . . be an enumeration of the operators as in Proposition 21.
We will construct S, with the following two properties:(1) For each i, there exist distinct functions f, f 0 in S such that M(Θi (f )) =M(Θi (f 0 )). This would immediately imply that S 6≤Ex C.
(2) S ∈ RefEx.
For each i, we will define some functions in S, which have f (0) = i. These will
be used to diagonalize against Θi (to satisfy (1) above).
For each i, do the following (independent staging construction for each i).
Let σ0 = {(0, i)}. Go to stage 0.

Stage s
1. Put 0-ext(σs ) and 1-ext(σs ) in S.
2. Let f0 = 0-ext(σs ), and f1 = 1-ext(σs ).
3. Search for t, if any, such that M(Θi (f0 [t])) 6= M(Θi (f1 [t])).
4. If and when such a t is found, pick the least such t.
5. Suppose M(Θi (fw [t])) 6= M(Θi (σs )), where w ∈ {0, 1}.
6. Let σs+1 = fw [t].
7. Go to stage s + 1.
End stage s

14Claim 25 For each i, there are only finitely many stages.
Proof. Otherwise M makes infinitely many mind changes on the recursiveSfunction Θi ( s∈N σs ).
2
For each i, one can effectively (in i) enumerate the initial segments which startwith i, but are not extended by any function in S. To see this, consider anyτ ⊇ {(0, i)}. Execute the stages as above, until(i) a σs is defined such that τ ⊆ 0-ext(σs ) or τ ⊆ 1-ext(σs ) (in which case τ isextended by a function in S), or(ii) a stage s is reached such that σs is inconsistent with τ , and σs−1 ⊆ τ (inwhich case τ is extended by a function in S iff τ ⊆ 0-ext(σs−1 ) or τ ⊆ 1ext(σs−1 )), or(iii) a stage s is reached such that σs ⊆ τ , and, for f0 = 0-ext(σs ) and f1 = 1ext(σs ), it is observed that M(Θi (f0 [z])) = M(Θi (f1 [z])), for all z ≤ t, and τ
is inconsistent with both f0 [t] and f1 [t] (in which case τ is not extended byany function in S).
Note that above exhausts all the possible cases by the construction of S.
Moreover, for each i, there are only finitely many f such that f (0) = i andf ∈ S, and these f can be recursively enumerated (effectively in i). It follows
that S ∈ RefEx.
Now by construction, for each i, (1) is satisfied, since for the last stage s whichis executed, M(Θi (0-ext(σs ))) = M(Θi (1-ext(σs ))), where both 0-ext(σs ) and1-ext(σs ) are in S.
Theorem 24 immediately yields the following result.
Theorem 26 (1) There is no Ex-complete class in RefEx.
(2) There is no Ex-complete class in WRefEx.
In contrast to Theorem 26, RelEx contains an Ex-complete class.
Theorem 27 There is an Ex-complete class in RelEx.
Proof. In [13] it was shown that FINSUP is Ex-complete in Ex. Moreover,
FINSUP ∈ RelEx, see proof of Theorem 16. Hence, FINSUP is Ex-complete
in RelEx.

15

3.3

Characterizations

We now present several characterizations for RefEx, WRefEx and RelEx.
The first group of characterizations relates refutable learning to the establishedconcept of classification. The main goal in recursion theoretic classification canbe informally 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 has to find out which of these classes the corresponding
function belongs to, see [4,39,37,36,9]. What we need in our characterization
theorems below will be some special cases of classification, namely classification where only two classes are involved in the classification process, moreexactly, a class together with its complement; and semi-classification which issome weakening of classification. Notice 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. Furthermore, they also allow
to create classes being learnable refutably in a given sense.
Let R0,? denote the class of all computable functions mapping the set N into
the set {0, ?} and being everywhere defined.
Definition 28 A class S ⊆ R is called finitely semi-classifiable iff there isc ∈ 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 any function fromthat class, after some finite amount of time one finds out that the function
belongs to the class, whereas for any other function, i.e. for any function from
S, one finds out “nothing”.
Theorem 29 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= ⊥.
16

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 29, C
is RefEx-learnable. Moreover, C 6∈ NUM was shown in [40], 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.
Corollary 30 RefEx \ NUM 6= ∅.
We now characterize WRefEx.
Definition 31 (Wiehagen and Smith [39]). Let C, S ⊆ R, where C, S are
disjoint. (C, S) is called classifiable iff there is c ∈ R0,1 such that for any f ∈ C
and for almost all n ∈ N, c(f [n]) = 0; and for any f ∈ S and for almost alln ∈ N, c(f [n]) = 1.
Thus, intuitively, a pair of disjoint classes C, S is classifiable if for any function
from the union of C and S, in the limit one can find out which of the classes C or
S this function belongs to. For characterizing WRefEx, we need a special caseof classification, namely where the classes under consideration form a partitionof the class of all recursive functions, i.e. one class is just the complement of
the other.
Definition 32 A class C ⊆ R is called classifiable iff (C, C) is classifiable.
Theorem 33 For any C ⊆ R, C ∈ WRefEx iff C is contained in someclassifiable class S ∈ 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.
17c(f [n]) =0, if M(f [n]) 6= ⊥;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.
0M (f [n]) =M(f [n]), if c(f [n]) = 0⊥,
if c(f [n]) = 1.

Clearly, M0 witnesses that C ∈ WRefEx.
Finally, we give a characterization of RelEx in terms of semi-classifiability.
Definition 34 (Stephan [37]). A class S ⊆ R is called 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]) = ?.
Intuitively, a class of recursive functions is semi-classifiable if for any function
from this class, in the limit one is able to find out that this function belongs
to the class, while for any recursive function outside that class, there is norequired evidence in the limit to know where this function comes from.
Theorem 35 For any C ⊆ R, C ∈ RelEx iff C is contained in some semiclassifiable class S ∈ 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.
c(f [n]) =0, if n = 0 or M(f [n − 1]) = M(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.
Sufficiency. Suppose C ⊆ S ⊆ Ex(M). Suppose S be semi-classifiable by somec ∈ R0,? . Define M0 as follows.
M0 (f [n]) =M(f [n]), if c(f [n]) = 0;n,if c(f [n]) = ?.
18

Clearly, for any f ∈ S, for almost all n, c(f [n]) = 0. Hence M0 will Exidentify 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-identifies C.
Notice that there is some kind of “dualism” in the characterizations of RefEx
and RelEx above. Indeed, a class is RefEx-learnable in case this class is
contained in some Ex-learnable class the complement of which is finitely semiclassifiable. In contrast, a class is RelEx-learnable if this class is contained in
an Ex-learnable class that itself is semi-classifiable.
The characterizations of the second group below, this time for RefEx andRelEx, significantly differ from the characterizations presented above in two
points. First, the characteristic conditions are stated here in terms that formally have nothing to do with learning. And second, the sufficiency proofs
are again constructive and they make clear where the “refuting ability” ofthe corresponding learning machines in general comes from. For stating thecorresponding characterization of RefEx, we need the following notions.
Definition 36 A numbering ψ is called strongly one-to-one iff there is a recursive function d of two arguments such that for any distinct i, j ∈ N, there
exists an x < d(i, j) such that ψi (x) 6= ψj (x).
Obviously, 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 can effectively compute a bound on the least argument on which thesefunctions differ.
Definition 37 (Rice [34]). A class Π ⊆ P is called completely r.e. iff{i | ϕi ∈ Π } is recursively enumerable.
Thus, a class of partial recursive functions is completely r.e. if its complete
index set, i.e. the set of all programs of functions from Π in the acceptable
programming system ϕ, is recursively enumerable. We will need the following
characterization of completely r.e. classes.
Lemma 38 ([34,27]). For any Π ⊆ P, Π is completely r.e. iff there is anr.e. subset S of SEG such that Π = {g | g ∈ P & (∃ σ ∈ S)[σ ⊆ g]}.
Hence, a class Π is completely r.e. if for some effective class of finite functions,Π contains exactly all the computable superfunctions of these finite functions.
Theorem 39 For any C ⊆ R, C ∈ RefEx iff there are numberings ψ and %such that(1) ψ is strongly one-to-one and C ⊆ Pψ ,19

(2) P% is completely r.e. and R% = Rψ .
Proof. Necessity. Without loss of generality assume that C is infinite. Let
C ∈ RefEx as witnessed by a total IIM M. Then let
Z = {(z, n) | (∀x < n)[ϕz (x)↓] & M(ϕz [n]) = z &[n = 0 ∨ M(ϕz [n − 1]) 6= M(ϕz [n])]}.
Intuitively, the set Z contains “initial segments” of any function where M
might begin to converge to a correct hypothesis. Let e be a 1–1 recursivefunction such that Z = range(e). For any i, j, x ∈ N , where e(i) = (z, n) ande(j) = (w, m), defineϕz (x),


if x < n;ϕz (x), if x ≥ n and (∀y ≤ x)[ϕz (y)↓] andψi (x) =(∀y | n < y ≤ x + 1)[M(ϕz [y]) = M(ϕz [n])];↑,otherwise.
and d(i, j) = max({n, m}).
Then it can easily be seen that ψ is a strongly one-to-one numbering as witnessed by the function d.
In order to show C ⊆ Pψ we prove a somewhat stronger result which is neededin the following. Therefore, let S denote the class of all recursive functions
that are Ex-learnable by M. Clearly, C ⊆ S.
Claim 40 S = Rψ .
Proof. Let f ∈ S. Then there is a minimal n ∈ N and a z ∈ N such that ϕz = f
and for all m ≥ n, M(f [m]) = z. Consequently, (z, n) ∈ Z and ψi = ϕz = f ,where e(i) = (z, n). Hence f ∈ Rψ .
Let now f ∈ Rψ . Let f = ψi and e(i) = (z, n). Then ψi = ϕz , since ψi = f
is everywhere defined. Consequently, for all m ≥ n, M(f [m]) = M(ϕz [m]) =M(ϕz [n]) = z. Hence f is Ex-learnable by M, and thus f ∈ S.
2Claim 40 above completes the proof of condition (1).
In order to show condition (2) let
A = {σ ∈ SEG | M(σ) = ⊥}.
Clearly, A is recursively enumerable.
Finally, let % be an arbitrary numbering such that
P% = {η | η ∈ P & (∃σ ∈ A)[σ ⊆ η]}.
20

Obviously, P% is completely r.e. by Lemma 38.
Claim 41 R% = Rψ .
Proof. By Claim 40, it suffices to prove that R% = S.
Let f ∈ R% . Then, by the definitions of P% and A, M(f [n]) = ⊥ for some n.
Consequently, f cannot be Ex-learned by M. Hence f ∈ S.
Suppose now f ∈ S. Then, by definition of RefEx, f must be refuted by M.
Thus, M(f [n]) = ⊥ for some n, and hence f ∈ P% .
2
Claim 41 completes the proof of condition (2).
Sufficiency. Let ψ be a strongly one-to-one numbering as witnessed by a corresponding function d. Let % be a numbering such that for some r.e. S ⊆ SEG,
P% = {η | η ∈ P & (∃σ ∈ S)[σ ⊆ η]}, and R% = Rψ . Then an IIM M that
RefEx-learns Rψ ⊇ C can be defined as follows. Let f ∈ R.

M(f ) = “ In parallel do both (A) and (B).
(A) Go to stage 0.
Stage i.
Output i. Check if there is j 6= i such thatf [d(i, j)] ⊆ ψjin which case go to stage i + 1.
End Stage i.
(B) Check if there is σ ∈ S such thatσ ⊆ fin which case output ⊥ forever.”
Claim 42 M Ex-learns any function from Rψ .
Proof. Let f ∈ Rψ . First notice that (B) can never happen, since otherwisef ∈ R% would follow, a contradiction to R% and Rψ being disjoint. Let f = ψz .
Then, clearly, for any i < z, f [d(i, z)] ⊆ ψz will hold. Hence, in (A), stage z will
be reached. But stage z can never be left, since this would yield f [d(z, j)] ⊆ ψjfor some j 6= z, implying the contradiction ψz 6= f via [(∃x < d(z, j))[ψz (x) 6=
ψj (x)]]. Consequently, on f , M will converge to z, thus Ex-learning f .
2
Claim 43 M refutes any function from Rψ .
Proof. For any function f ∈ Rψ = R% , (B) happens by the definition of P% .
Hence M refutes f .
2
Claims 42 and 43 complete the sufficiency proof.
21

It follows from the proof of Theorem 39 that in RefEx-learning the processesof learning and refuting, respectively, can be nicely separated. Actually, in
general, a suitable machine can be provided with two spaces, one for learning, ψ, and one for refuting, %. If and when the “search for refutation” inthe refutation space has been successful, then the learning process can be
stopped forever. This search for refutation is based on the property that thewhole space for refutation forms a completely r.e. class P% of partial recursivefunctions. Then, by the characterization lemma for completely r.e. classes,
any system S of “representatives” for P% can serve as a set of indicators forrefutation. The spaces for learning and for refuting are interconnected by the
essential property that their recursive kernels, Rψ and R% , disjointly exhaustthe class of all recursive functions. This property eventually guarantees thateach recursive function either will be learned or refuted. Notice that the above
characterization of RefEx is in a sense “more granular” than the characterization of RefEx by Theorem 29. Intuitively, the characterization of Theorem 29
requires that one should be able to find out anyhow if the given function does
not belong to the class to be learned. The characterization of Theorem 39 now
makes precise how this task can be done. Indeed, the set S may be thought asjust sampling all possibilities of violating the structure of the functions fromthe class to be learned, thereby indicating if and when the corresponding function has to be refuted. Furthermore, notice that the RefEx-characterizationof Theorem 39 is incremental to a characterization of Ex in that the existenceof a numbering with condition (1) above is just necessary and sufficient for
Ex-learning the corresponding class C, see [38]. Finally, notice that the refutation space could be “economized” in the same strict manner as the learningspace, that is, it can be made one-to-one.
The following characterization of RelEx is a slight modification of a result
from [21].
Theorem 44 For every C ⊆ R, C ∈ RelEx iff there are a numbering ψ anda function d ∈ R such that(1) for all f ∈ R, if Hf = {i | f [d(i)] ⊆ ψi } is finite, then Hf contains aψ-index of f ,(2) for every f ∈ C, Hf is finite.
Proof. Necessity. Let C ∈ RelEx as witnessed by some total IIM M, and let
Y = {f [n] | f ∈ R & [n = 0 ∨ M(f [n − 1]) 6= M(f [n])]}.
Suppose e is a 1–1 recursive function such that range(e) = Y . For i, x ∈ N
and e(i) = f [n], let d(i) = n and(ψi (x) =f (x),
if x < n;ϕM(f [n]) (x), otherwise.
22

Clearly, ψ is a numbering and d ∈ R. Now let f ∈ R be such that Hf ={i0 , . . . , im } is finite. Notice that Hf must be non-empty, since f [0] ∈ Y and,hence, by definition of ψ, i0 ∈ Hf , where e(i0 ) = f [0]. For j ≤ m, let αj =e(ij ). Without loss of generality, let m be such that |αm | is maximum among|αj | for j ≤ m. Then, by definition of Y and ψ, M(f [n]) = M(αm ), for any
n ≥ |αm |. Hence M converges on f . Since M is reliable, f = ϕM(αm ) follows.
Moreover, by the definition of ψ, we have ψim = f . Consequently, Hf containsa ψ-index of f . This proves condition (1). For showing condition (2) supposef ∈ C. Then M converges on f . Consequently, there are at most finitely manyn ∈ N such that f [n] ∈ Y . By definition of ψ, this implies that Hf is finite.
Sufficiency. Informally, an IIM reliably learning C, on every function f ∈ R,
searches for all the elements of the set Hf and applies the amalgamation
technique, see [10], to this set. In order to proceed more formally, let c ∈ R besuch that for any i ∈ N, ψi = ϕc(i) . Let amal be a recursive function mapping
any finite set I of ψ-indices to a ϕ-index such that for any x ∈ N, ϕamal(I) (x)is defined by running ϕc(i) (x) for every i ∈ I in parallel and taking the firstvalue obtained, if any. For any f ∈ R and n ∈ N, let
Hf,n = {i | i ≤ n & d(i) ≤ n & (∀x < d(i))[Φc(i) (x) ≤ n & ϕc(i) (x) = f (x)]}.
Intuitively, Hf,n is the set of all ψ-indices i such that i ∈ Hf can be verified
within a uniformly (in n) bounded number of computation steps. Let+
Hf,n= {i | i ∈ Hf,n & (∀x < n)[Φc(i) (x) ≤ n ⇒ ϕc(i) (x) = f (x)]}.

+Thus, Hf,nis the subset of Hf,n consisting of all indices i such that on any
argument less than n, ψi does not contradict f within n steps of computation.
Finally, let Hf,−1 = ∅.

Then define an IIM M as follows.
M(f [n]) = “+
If Hf,n = Hf,n−1 6= ∅, then output amal(Hf,n).

If Hf,n = ∅ or Hf,n 6= Hf,n−1 , then output n.”
Claim 45 For any f ∈ R, if Hf is finite, then M Ex-identifies f .
Proof. By assumption of the claim we can conclude limn→∞ Hf,n = Hf . There+
exists, and Hf+ contains exactly every i ∈ Hf suchfore, Hf+ = limn→∞ Hf,nthat ψi is a subfunction of f , including some ψ-index of f , by condition (1).
Clearly, M(f [n]) converges to j = amal(Hf+ ), and ϕj = f .
2
By Claim 45 and condition (2), M identifies C.
23

It remains to show that M works reliably.
Claim 46 For any f ∈ R, if M converges on f , then M Ex-identifies f .
Proof. By Claim 45, it suffices to prove that if M converges on f , then Hf isfinite. Suppose to the contrary that Hf is infinite. Then, by definition of M,
M diverges on f , a contradiction.
2
This completes the proof of sufficiency.

Theorem 44 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 44, for any function f from theclass to be learned, there are only finitely many “candidates” for ψ-indices off , 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 succeeds inlearning any such f . Conversely, the infinity of this set Hf of candidates automatically ensures that the learning machine as defined in the sufficiency proofof Theorem 44 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. Specifically, 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.
For η, η 0 ∈ P 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.
Definition 47 ([15,5,10]). Let a ∈ N ∪ {∗}, let f ∈ R and let M be an IIM.
(a) M Exa -identifies f (written: f ∈ Exa (M)) just in case, there exists an isuch that M(f )↓ = i and ϕi =a f .
(b) M Exa -identifies C iff M Exa -identifies each f ∈ C.
(c) Exa = {C ⊆ R | (∃M)[C ⊆ Exa (M)]}.
Thus, in Exa -learning the final hypothesis may be slightly incorrect in that it24

is allowed to contain at most a anomalies. Note that Ex = Ex0 .
Definition 48 ([2,10]). Let a ∈ N ∪ {∗}, let f ∈ R and let M be an IIM.
(a) M Bca -identifies f (written: f ∈ Bca (M)) iff, for all but finitely manyn ∈ N, ϕM(f [n]) =a f .
(b) M Bca -identifies C iff M Bca -identifies each f ∈ C.
(c) Bca = {C ⊆ R | (∃M)[C ⊆ Bca (M)]}.
Note that Bc = Bc0 .
Harrington [10] showed that R ∈ Bc∗ . Thus, we shall consider mainly Bca fora ∈ N in the following.
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 49 Let a ∈ N ∪ {∗} and let M be an IIM. M Ref Exa -identifies
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 6∈ Exa (M), there exists an n such that (∀m <n)[M(f [m]) 6= ⊥] and (∀m ≥ n)[M(f [m]) = ⊥].
Definition 50 (Kinber and Zeugmann [22]). Let a ∈ N ∪ {∗} and let M
be an IIM. M RelBca -identifies C iff(a) C ⊆ Bca (M).
(b) For all f ∈ R such that f 6∈ Bca (M), there exist infinitely many n suchthat M(f [n]) = ⊥.
Note that the learning types RelExa and RelBca were studied firstly in [23]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 51 (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 .
25

Proof. We only show part (a). Part (b) can be shown similarly. Suppose by
way of contradiction that a ∈ N and σ ∈ SEG are such that {f ∈ R | σ ⊆f } ∈ Bca . Suppose M Bca -identifies {f ∈ R | σ ⊆ f }. Let gf be defined asfollows:gf (x) =σ(x),if x < |σ|;f (x − |σ|), otherwise.

Let gf [n] = gf [n + |σ|].
Let prog be a recursive function such that ϕprog(p) (x) = ϕp (x + |σ|).
Define M0 as follows: M0 (f [n]) = prog(M(gf [n] )). It is easy to verify that if M
Bca -identifies gf , then M0 Bca -identifies f . It follows that M0 Bca -identifies R.
This contradicts the Bca -hierarchy theorem in [10], and thus the proposition
follows.
Next, we define Ex-learning without mind changes, or, equivalently, finite
learning. Informally, here the learning machine has “one shot” only to do its
learning task.
Definition 52 (Gold [15]). Let f ∈ R and let M be an IIM.
(a) M Fin-identifies f (written: f ∈ Fin(M)) iff there is n ∈ N such thatfor any x < n, M(f [x]) = ?, M(f [n]) ∈ N, and ϕM(f [n]) = f .
(b) M Fin-identifies C iff M Fin-identifies each f ∈ C.
(c) Fin = {C ⊆ R | (∃M)[C ⊆ Fin(M)]}.
Theorem 53 For all a ∈ N, Fin \ RelBca 6= ∅.
Proof. Let C = {f ∈ R0,1 | f 6= Zero & ϕmin({x|f (x)=1}) = f }. Clearly, C ∈ Fin.
Suppose by way of contradiction that M RelBca -identifies C. Then, by Kleene
recursion theorem [35], there exists an e such that ϕe may be defined in stages
as follows. Let ϕe (x) = 0, for x < e, and ϕe (e) = 1.
Let ϕse denote ϕe defined before stage s. Go to stage 0.
Stage s.
1. Search for a τ ∈ SEG0,1 properly extending ϕse such that M(τ ) = ⊥.
2. If and when such a τ is found, let ϕs+1
= τ , and go to stage s + 1.
e
End stage s
We consider two cases.
Case 1. All stages finish (i.e. step 1 succeeds in all stages).
26

In this case ϕe ∈ R ∩ C, and M outputs ⊥ on infinitely many initial segmentsof ϕe .
Case 2. Stage s starts but does not finish.
In this case, by definition of RelBca , M must Bca -identify {f ∈ R0,1 | ϕse ⊆f }, a contradiction to Proposition 51.
From the above cases it follows that M does not RelBca -identify C.
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. Therefore, we need the following lemma.
Lemma 54 For every a ∈ N, there exists a function p ∈ R such that, for alli ∈ N:(a) range(ϕp(i) ) ⊆ {0, 1}.
(b) ϕp(i) is undefined on at most a + 1 inputs.
(c) ϕp(i) (i) = 1, and, for all x < i, ϕp(i) (x) = 0.
(d) {f ∈ R0,1 | ϕp(i) ⊆ f } 6⊆ Exa (Mi ).
Proof. The lemma is proved by a modification of the proof of Exa+1 \ Exa 6= ∅in [10]. By the parameterized recursion theorem [35], there exists a recursivefunction p such that ϕp(i) may be defined in stages as follows. ϕp(i) (i) = 1, and
ϕp(i) (x) = 0, for x < i. Let xs denote the least x such that ϕp(i) (x) has notbeen defined before stage s.
Go to stage 0.

Stage s
1. Dovetail steps 2 and 3, until step 2 succeeds. If and when step 2 succeeds,
go to step 4.
2. Search for a τ ∈ SEG0,1 such that
τ (x) = ϕp(i) (x), for x < xs ,
τ (x)↓, for xs ≤ x ≤ xs + a,
τ (x) = 0 or undefined, for x > xs + a,
and Mi (τ ) 6= Mi (ϕp(i) [xs ]).
3. For x = xs + a + 1 to ∞Let ϕp(i) (x) = 0.
EndFor
4. If and when such a τ is found let,27

5. ϕp(i) (x) = τ (x), for x < |τ | such that ϕp(i) (x) has not been defined uptonow.
6. Go to stage s + 1.
End stage s

Fix i. (a) and (c) clearly hold. We now consider two cases.
Case 1. All stages terminate.
In this case ϕp(i) is total. Thus (b) is satisfied. Also due to step 5, Mi changes
its mind infinitely often on ϕp(i) .
Case 2. Stage s starts but does not terminate.
In this case ϕp(i) is undefined only on {x | xs ≤ x ≤ xs + a}, thus (b) issatisfied. Also, for all f ∈ R0,1 such that ϕp(i) ⊆ f , Mi (f ) = Mi (ϕp(i) [xs ]).
Let e = Mi (ϕp(i) [xs ]). Let g be defined as follows: ϕp(i) (x),if x < xs or x > xs + a;g(x) = 0,
if xs ≤ x ≤ xs + a, and ϕe (x)↑; .
1 − ϕe (x), otherwise.
It is easy to verify that g ∈ R0,1 , g ⊇ ϕp(i) , and Mi (g)↓ = Mi (ϕp(i) [xs ]) = e.
However, ϕe 6=a g, since g(x) 6= ϕe (x), for xs ≤ x ≤ xs + a. Thus (d) holds.
Lemma follows from above cases.
Theorem 55 For all a ∈ N, Ref Exa+1 \ Exa 6= ∅.
Proof. Let p be as in Lemma 54. Let Ci = {Zero} ∪ {f ∈ R0,1 | ϕp(i) ⊆ f }. LetS
C = i∈N Ci . By Lemma 54 (d), it follows that C 6∈ Exa .
Now define M as follows. Let z be a program for Zero. Let MinO(σ) = min({x |σ(x) = 1}),M(σ)
1. If σ ⊆ Zero, then output z.
Else, let i = MinO(σ).
2. If there exists an x such that ϕp(i) (x) converges in at most |σ| steps, and
ϕp(i) (x) 6= σ(x), then output ⊥.
Else output p(i).
End M(σ)

28Clearly, M Exa+1 -identifies C. If f 6∈ C, then let i = MinO(f ). Now, there
must exist an x such that f (x) 6= ϕp(i) (x). Thus, M on some initial segmentof f , outputs ⊥. Also, if M(σ) = ⊥, then M(τ ) = ⊥, for all extensions τ of σ.
It follows that M Ref Exa+1 -identifies C.
Clearly, from Theorem 55 we immediately get the following hierarchy results,
where the last one was already obtained in [23].
Corollary 56 For every a ∈ N,
(1) Ref Exa ⊂ Ref Exa+1 ,(2) WRef Exa ⊂ WRef Exa+1 ,(3) RelExa ⊂ RelExa+1 .
A proof similar to Lemma 54 can be used to show that
Lemma 57 There exists a function p ∈ R such that, for all i, j ∈ N:(a) range(ϕp(hi,ji) ) ⊆ {0, 1}.
(b) ϕp(hi,ji) is undefined on at most j + 1 inputs.
(c) ϕp(hi,ji) (hi, ji) = 1, and, for all x < hi, ji, ϕp(hi,ji) (x) = 0.
(d) {f ∈ R0,1 | ϕp(hi,ji) ⊆ f } 6⊆ Exj (Mi ).
Now a proof similar to the proof of Theorem 55 can be used to show theSfollowing result. Notice that Ex∗ \ a∈N Exa 6= ∅ was proved in [10].
Theorem 58 Ref Ex∗ \Sa∈N Exa6= ∅.

From Theorem 55 we can derive further corollaries. Therefore, we need thefollowing notation. For η ∈ P, let cylη be defined as follows: cylη (hx, yi) =η(x). For C ⊆ R, let cylC = {cylf |f ∈ C}.
Proposition 59 (a) If C ∈ Ref Bc, then cylC ∈ Ref Bc.
(b) cylC ∈ Ex∗ iff cylC ∈ Ex iff C ∈ Ex.
Proof. (a) Suppose M Ref Bc-identifes C.
For any σ, let uncylσ be defined as follows. Let fσ (x) = σ(hx, 0i). Let m be thesmallest value such that fσ is not defined. Then, let uncylσ = fσ [m]. It is easy
to verify that, for all g, n, uncylcylg [n] ⊆ g. Moreover, limn→∞ |uncylcylg [n] | = ∞.
Let progcyl(p) be a program obtained effectively from p for cylϕp . Now define29

M0 as follows:


 ⊥,

 ⊥,

if (∃x, y, z)[σ(hx, yi)↓ =6 σ(hx, zi)↓];if
M(uncyl)=⊥;σ
M0 (σ) =
progcyl(p),ifM(uncylσ ) = p and¬(∃x, y, z)[σ(hx, yi)↓ =6 σ(hx, zi)↓].
It is easy to verify that M0 Ref Bc-identifies cylC .
Assertion (b) is an immediate consequence of the corresponding definitions.
In [10], Ex∗ ⊆ Bc was shown. This result also holds for all of our types ofrefutable learning.
Proposition 60 For I ∈ {Ref , WRef , Rel}, IEx∗ ⊆ IBc.
Proof. Suppose C ∈ IEx∗ as witnessed by M. Here for RelEx∗ -identification,
we assume that M is doing the identification in the sense of Definition 7 (thatis if f 6∈ Ex∗ (M), then M on f outputs ⊥ infinitely often). Suppose C ∈ Bc as
witnessed by M0 (since Ex∗ ⊆ Bc, such an M0 exists). Define M00 as follows.

00

M (f [n]) =M0 (f [n]), if M(f [n]) 6= ⊥;⊥,otherwise.

It is easy to verify that M00 IBc-identifies C.
In [10] it was proved that Bc \ Ex∗ 6= ∅. This result holds refutably, as ournext corollary shows.
Corollary 61 Ref Bc \ Ex∗ 6= ∅.
Proof. By Theorem 55, there exists a class C ∈ Ref Ex1 \Ex. Thus, by Proposition 60, there exists a class C ∈ Ref Bc \ Ex. Now, cylC ∈ Ref Bc \ Ex∗ , by
Proposition 59.
The next corollary points out that already Ref Ex1 contains “algorithmicallyrich” classes of predicates.
Corollary 62 Ref Ex1 ∩ 2R0,1 6⊆ NUM ∩ 2R0,1 .
Proof. Let a = 0, and let C ∈ 2R0,1 be defined as in the proof of Theorem 55.
Then, by that proof, C ∈ Ref Ex1 \ Ex. Hence C ∈/ NUM, since NUM ⊆ Ex,
see [15].
30

Corollary 62 can be even strengthened by replacing Ref Ex1 with RefEx.
This another time exhibits the richness of already the most stringent of ourtypes of learning refutably.
Theorem 63 RefEx ∩ 2R0,1 6⊆ NUM ∩ 2R0,1 .
Proof. Let (∀n x) denote for all but at most n of x. That is, (∀n x)[P (x)],denotes card({x | ¬P (x)}) ≤ n. In [8] it was shown that there exist recursivefunctions g and p such that for each e, the following three conditions are
satisfied.
(a) ϕp(e) (e) = 1 and, for x < e, ϕp(e) (x) = 0.
(b) domain(ϕp(e) ) is either N or an initial segment of N and range(ϕp(e) ) ⊆{0, 1}.
(c) If ϕe is total, then(c.1) ϕp(e) is total,(c.2) (∀j)(∀j+1 x > max({e, j}))[(∃y ≤ x)[ϕj (y) 6= ϕp(e) (y)] ∨ [Φp(e) (x) ≤g(e, x, Φj (x))]], and(c.3) (∀j | ϕj = ϕp(e) )(∀∞ x)[Φj (x) > ϕe (x)].
Let C = {ϕp(e) | ϕe is total}. It was shown in [8] that this class contains
arbitrarily complex functions from R0,1 (based on clause c.3 above), and thus
C 6∈ NUM.
We now define an IIM that RefEx-learns C. Let q be a program for Zero.

M(f [n]) =




q,
if(∀x < n)[f (x) = 0];







p(e), if e < n & f (e) = 1 & (∀x < e)[f (x) = 0] &








¬[(∃x < n)[Φp(e) (x) < n & ϕp(e) (x) 6= f (x)]] &¬[(∃j ≤ n)(∃S ⊆ N| card(S) = j +2, min(S) > max({e, j}))




















 ⊥,

[(∀y ≤ max(S))[Φj (y) ≤ n & ϕj (y) = f (y)] &(∀x ∈ S)[Φp(e) (x) > g(e, x, Φj (x))]]];
otherwise.

It is easy to verify that M Ref Ex-identifies C. Theorem follows.
Note that Theorem 63 contrasts a known result on reliable Ex-learning. Actually, if we require the Ex-learning machine’s reliability not only on the set
R of all recursive functions, but even on the set of all total functions, then all
the classes of recursive predicates belonging to this latter type turn out to be
in NUM, see [16].
31We now prove the analogue to Theorem 55 for Bca -learning rather than Exa learning. Note that Bca+1 \ Bca 6= ∅ was shown in [10]. We need the following
lemma.
Lemma 64 For any a ∈ N, there exist a recursive function p and a partial
recursive function q such that, for all i:(a) The following three conditions hold:(a.1) for all j, range(ϕp(i,j) ) ⊆ {0, 1},(a.2) ϕp(i,0) (i) = 1,(a.3) for all x < i, ϕp(i,0) (x) = 0.
(b) Either {x | q(i, x)↓} = N or there exists an s such that {x | q(i, x)↓} ={x | x ≤ s}.
(c) If {x | q(i, x)↓} = N, then the following two conditions hold:(c.1) for all j, ϕp(i,j) =a+1 ϕp(i,0) ,(c.2) ϕp(i,0) ∈ R and ϕp(i,0) 6∈ Bca (Mi ).
(d) If {x | q(i, x)↓} = {x | x ≤ s}, then the following three conditions hold:(d.1) ϕp(i,0) ⊆ ϕp(i,s) ,(d.2) ϕp(i,s) ∈ R and ϕp(i,s) 6∈ Bca (Mi ),(d.3) for all j such that 1 ≤ j < s, domain(ϕp(i,j) ) = domain(ϕp(i,0) ) andϕp(i,j) =a+1 ϕp(i,0) .
Proof. The lemma is proved using a modification of the proof of Bca+1 \Bca 6=∅ in [10]. By the Operator Recursion Theorem [7], there exists a recursive psuch that ϕp(i,j) may be defined as follows. For a fixed i, we will define ϕp(i,·) ,and q(i, ·), in stages as follows. The construction can be easily seen to beeffective in i. Note that if ϕp(i,j) (x) (respectively q(i, y)) is not defined instages below then ϕp(i,j) (x)↑ (respectively, q(i, y)↑). Initially, letq(i, 0) = 0,ϕp(i,0) (i) = 1, andϕp(i,0) (x) = 0, for x < i.
Let xs denote the least x such that ϕp(i,0) (x) has not been defined before stages. Thus, x1 = i + 1. Go to stage 1.
32

Stage s
1. Let q(i, s) = 0.
For x < xs , let ϕp(i,s) (x) = ϕp(i,0) (x).
2. Let f = 0-ext(ϕp(i,0) ).
3. Dovetail steps 4 and 5 until step 4 succeeds. If and when step 4 succeeds,
go to step 6.
4. Search for a set Ss of cardinality a + 1 and ms > xs such that(∀x ∈ Ss )[x > ms & ϕM(f [ms ]) (x)↓].
5. For x = xs to ∞ do
Let ϕp(i,s) (x) = 0.
EndFor
6. If and when such an Ss and ms are found,
let w = max(Ss ∪ {x | ϕp(i,s) (x) was defined in step 5 above }).
. ϕ
6.1 For x ∈ Ss , let ϕp(i,0) (x) = 1 −M(f [ms ]) (x).
6.2 For xs ≤ x ≤ w such that x 6∈ Ss , let ϕp(i,0) (x) = 0.
6.3 For xs ≤ x ≤ w such that ϕp(i,s) (x) has not been defined upto now, let
ϕp(i,s) (x) = 0.
6.4 Let ϕp(i,s) follow ϕp(i,0) from now on. That is, for x > w such that ϕp(i,s) (x)has not been defined upto now, ϕp(i,s) (x) is made to be same as ϕp(i,0) (x)whenever, if ever, ϕp(i,0) (x) gets defined.
(* This ensures that ϕp(i,s) and ϕp(i,0) are same on all x 6∈ Ss *).
6.5 Go to stage s + 1.
(* Note that xs+1 = w + 1. *)End stage s
Fix i. Clearly, parts (a) and (b) of Lemma are satisfied. To show parts (c) and(d) we consider two cases.
Case 1. All stages terminate.
In this case q(i, x) is defined for all x. (c.1) holds due to step 6.4. (Note thatϕp(i,s) and ϕp(i,0) are same on all x 6∈ Ss ).
Also, due to step 6.1, for all s, ϕM(ϕp(i,0) [ms ]) 6=a ϕp(i,0) . Thus (c.2) is satisfied.
Case 2. Stage s starts but does not terminate.
In this case q(i, x) is defined for x ≤ s, and undefined for x > s. (d.1) clearlyholds due to step 1. (d.2) holds since, for all but finitely many m, ϕM(ϕp(i,s) [m])is finite (otherwise step 4 would succeed). Comment at the end of step 6.4
implies (d.3).
This proves the lemma.
Theorem 65 For all a ∈ N, Ref Bca+1 \ Bca 6= ∅.
33

Proof. Let p and q be as in Lemma 64. Let(Ci ={ϕp(i,0) },if {x | q(i, x)↓} = N.
{f ∈ R0,1 | ϕp(i,0) ⊆ f & f =a+1 ϕp(i,s) }, if {x | q(i, x)↓} = {x | x ≤ s}.

Let C = {Zero} ∪Si∈N Ci .

We claim that C ∈ Ref Bca+1 \ Bca . By Lemma 64, it follows that Ci 6⊆
Bca (Mi ). Thus, C 6∈ Bca .
Let
MinO(σ) = min({x | σ(x) = 1}),Z1 = {σ ∈ SEG0,1 | σ 6⊆ Zero & MinO(σ) = i & (∃x ∈ N)[ϕp(i,0) (x)↓ =6 σ(x)↓]},
Z2 = {σ ∈ SEG0,1 | σ 6⊆ Zero & MinO(σ) = i &(∃s ∈ N)(∃S ⊆ N | card(S) = a+2)[q(i, s)↓ & (∀x ∈ S)[ϕp(i,s) (x)↓ 6= σ(x)↓]]}.
The following claim follows easily from the definition of C.
Claim 66 f ∈ C iff (∀n ∈ N)[f [n] 6∈ Z1 ∪ Z2 ].
Note that Z1 and Z2 are recursively enumerable. Let Z1s and Z2s respectively
denote Z1 , Z2 enumerated upto s steps in some standard recursive enumeration.
Now define M as follows. Let z denote a program for Zero.

if σ ⊆ Zero;|σ||σ|
if (∃τ ⊆ σ)[τ ∈ Z1 ∪ Z2 ];M(σ) =
p(i, s), otherwise, where MinO(σ) = i, ands = max({x ≤ |σ| | q(i, x) converges within |σ| steps}).

z,



 ⊥,

It is easy to verify that,(i) if f 6∈ C, then M(f [m]) = ⊥ for all but finitely many m. Moreover, M(σ) =⊥ implies M(σ 0 ) = ⊥ for all extensions σ 0 of σ,(ii) if f = Zero then M outputs z as its only program on f ,(iii) if f ∈ Ci and {x | q(i, x)↓} = N, then M Bca+1 -identifies f , due toproperty (c.1) in Lemma 64,
34

(iv) if f ∈ Ci and {x | q(i, x)↓} = {x | x ≤ s}, then M(f ) converges to p(i, s),which is an a + 1 error program for f (by definition of Ci ).
It thus follows that C ∈ Ref Bca+1 .
Again, Theorem 65 yields the following hierarchies, where the last one solves
an open problem from [22].
Corollary 67 For every a ∈ N,
(1) Ref Bca ⊂ Ref Bca+1 ,(2) WRef Bca ⊂ WRef Bca+1 ,(3) RelBca ⊂ RelBca+1 .
Proposition 68 Ref Bc∗ \Saa∈N Bc 6= ∅.

Proof. Since R ∈ Bc∗ , see [10], we have that R ∈ Ref Bc∗ . Since R 6∈Saa∈N Bc , see [10], proposition follows.
Recall that in the proof of Theorem 16 we have derived that FINSUP 6∈
WRef Ex. This result will now be strengthened for WRef Bca -learning andthen used in the next corollary below.
Theorem 69 For every a ∈ N, FINSUP 6∈ WRef Bca .
Proof. Suppose by way of contradiction that M WRef Bca -identifies FINSUP .
Claim 70 (a) For all σ, there exists a τ ⊇ σ such that M(τ ) 6= ⊥.
(b) For all σ, there exists a τ ⊇ σ such that M(τ ) = ⊥.
Proof. Part (a) holds, since otherwise M does not Bc-identify 0-ext(σ). Part(b) holds since M cannot Bca -identify all extensions of σ.
2
Now define σi , τi as follows. σ0 = Λ. Let τi be an extension of σi such that
M(τi ) = ⊥. Let σi+1 be an extension of τi such that M(τi ) 6= ⊥. Note thatall σi and τi are defined by Claim 70 and can be effectively obtained. Now M
S
outputs ⊥ infinitely often on i∈N σi , without converging to ⊥. A contradiction
to M WRef Bca -identifying FINSUP . Theorem follows.
The following corollary points out the relative strength of RelEx-learningover WRef Bca -learning. In other words, in general, one cannot compensate
a stricter refutability constraint by a more liberal learning criterion.
Corollary 71 For all a ∈ N, RelEx \ WRef Bca 6= ∅.
35

Proof. Follows from Theorem 69, since FINSUP ∈ RelEx.
Our final result exhibits the strength of WRef Ex-learning over Ref Bca learning. Thus, it is in the same spirit as Corollary 71 above.
Theorem 72 For all a ∈ N, WRef Ex \ Ref Bca 6= ∅.
Proof. Let 0,

if x < i;σi (x) = 1, if x = i;↑, otherwise.
Define Ci as follows: {0-ext(τ )},Ci = 
∅,if τ is the least extension (in SEG0,1 ) of σisuch that Mi (τ ) = ⊥;otherwise.

Let C = {Zero} ∪ i∈N Ci . It is easy to verify that C ∈ WRef Ex. Supposeby way of contradiction that Mi Ref Bca -identifies C. Then, we consider twocases.
S

Case 1. There exists an extension τ 0 (in SEG0,1 ) of σi such that Mi (τ 0 ) = ⊥.
In this case, let τ be least such τ 0 . Now 0-ext(τ ) ∈ Ci , but Mi (τ ) = ⊥.
Case 2. There does not exist an extension τ 0 (in SEG0,1 ) of σi such that
Mi (τ 0 ) = ⊥.
In this case Mi must Bca -identify all f ∈ R0,1 such that σi ⊆ f . However,this contradicts Proposition 51.
From the above cases it follows that Mi does not Ref Bca -identify C.
Note that Theorems 53, 69 and 72, and Corollary 71 hold even if we replace
Bca by any criterion of inference for which Proposition 51 holds.

Acknowledgement

We would like to thank the referees for their valuable comments and suggestions which have resulted in several improvements of the presentation of thepaper.
36

References[1] D. Angluin and C. Smith. Inductive inference: Theory and methods. Computing
Surveys, 15:237–289, 1983.
[2] J. Bārzdiņš. Two theorems on the limiting synthesis of functions. In Theory of
Algorithms and Programs, Vol. 1, pages 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 Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theoryof Computing, Victoria, B.C., ACM Press, pages 390–399, 1992.
[5] L. Blum and M. Blum. Toward a mathematical theory of inductive inference.
Information and Control, 28:125–155, 1975.
[6] M. Blum. A machine-independent theory of the complexity of recursivefunctions. 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 ofcomputable languages. In R. Reischuk and M. Morvan, editors, STACS 97,
14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck,Germany, February/March 1997, Proceedings, volume 1200 of Lecture Notes in
Computer Science, pages 225–236. Springer-Verlag, 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
J. Bārzdiņš and D. Bjørner, editors, Baltic Computer Science, volume 502 of
Lecture Notes in Computer Science, pages 77–110. Springer-Verlag, 1991.
[12] R. Freivalds, J. Bārzdiņš, and K. Podnieks. Inductive inference of recursivefunctions: Complexity bounds. In J. Bārzdiņš and D. Bjørner, editors, Baltic
Computer Science, volume 502 of Lecture Notes in Computer Science, pages
111–155. Springer-Verlag, 1991.
[13] R. Freivalds, E. Kinber, and C. H. Smith. On the intrinsic complexity oflearning. Information and Computation, 123(1):64–71, 1995.
[14] E. M. Gold. Limiting recursion. The Journal of Symbolic Logic, 30:28–48, 1965.

37

[15] E. M. Gold. Language identification in the limit. Information and Control,
10:447–474, 1967.
[16] J. Grabowski. Starke Erkennung. In R. Lindner and H. Thiele, editors,
Strukturerkennung diskreter kybernetischer Systeme, Teil I, pages 168–184.
Seminarbericht Nr.82, Department of Mathematics, Humboldt University of
Berlin, 1986.
[17] G. Grieser. Reflecting inductive inference machines and its improvementby therapy. In S. Arikawa and A. Sharma, editors, Algorithmic Learning
Theory: 7th International Workshop, ALT ’96, Sydney, Australia, October
1996, Proceedings, volume 1160 of Lecture Notes in Artificial Intelligence, pages
325–336. Springer-Verlag, 1996.
[18] S. Jain. Learning with refutation. Journal of Computer and System Sciences,
57(3):356–365, 1998.
[19] 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.
[20] K. P. Jantke. Reflecting and self-confident inductive inference machines. In
K. Jantke, T. Shinohara, and T. Zeugmann, editors, Algorithmic Learning
Theory: 6th International Workshop, ALT ’95, Fukuoka, Japan, October 1995,
Proceedings, volume 997 of Lecture Notes in Artificial Intelligence, pages 282–
297. Springer-Verlag, 1995.
[21] W. Jekeli. Universelle Strategien zur Lösung induktiver Lernprobleme. Dept.
of Computer Science, University of Kaiserslautern, 1997. MSc Thesis.
[22] E. Kinber and T. Zeugmann. One-sided error probabilistic inductive inference
and reliable frequency identification. Information and Computation, 92:253–
284, 1991.
[23] E. B. Kinber and T. Zeugmann. Inductive inference of almost everywhere
correct programs by reliably working strategies. Journal of Information
Processing and Cybernetics (EIK), 21:91–100, 1985.
[24] R. Klette and R. Wiehagen. Research in the theory of inductive inference by
GDR mathematicians – A survey. Information Sciences, 22:149–169, 1980.
[25] S. Lange and P. Watson. Machine discovery in the presence of incomplete or
ambiguous data. In S. Arikawa and K. Jantke, editors, Algorithmic Learning
Theory: 4th International Workshop on Analogical and Inductive Inference, AII’94, 5th International Workshop on Algorithmic Learning Theory, ALT ’94,
Reinhardsbrunn Castle, Germany, October 1994, Proceedings, volume 872 of
Lecture Notes in Artificial Intelligence, pages 438–452. Springer-Verlag, 1994.
[26] R. Lindner. Algorithmische Erkennung.
Universität, Jena, 1972. In German.

Dissertation B, Friedrich-Schiller-[27] M. Machtey and P. Young. An Introduction to the General Theory of
Algorithms. North Holland, New York, 1978.

38

[28] E. Minicozzi. Some natural properties of strong identification in inductive
inference. Theoretical Computer Science, 2:345–360, 1976.
[29] T. Miyahara. Refutable inference of functions computed by loop programs.
Technical Report RIFIS-TR-CS-112, Kyushu University, Fukuoka, 1995.
[30] Y. Mukouchi and S. Arikawa. Inductive inference machines that can refute
hypothesis spaces. In K.P. Jantke, S. Kobayashi, E. Tomita, and T. Yokomori,editors, Algorithmic Learning Theory: 4th International Workshop, ALT ’93,
Tokyo, Japan, November 1993, Proceedings, volume 744 of Lecture Notes in
Artificial Intelligence, pages 123–136. Springer-Verlag, 1993.
[31] Y. Mukouchi and S. Arikawa. Towards a mathematical theory of machine
discovery from facts. Theoretical Computer Science, 137:53–84, 1995.
[32] D. Osherson, M. Stob, and S. Weinstein. Systems that Learn: An Introduction
to Learning Theory for Cognitive and Computer Scientists. MIT Press, 1986.
[33] K. R. Popper. The Logic of Scientific Discovery. Harper and Row, 1965.
[34] H. Rice. On completely recursively enumerable classes and their key arrays.
The Journal of Symbolic Logic, 21:304–308, 1956.
[35] H. Rogers. Theory of Recursive Functions and Effective Computability.
McGraw-Hill, 1967. Reprinted by MIT Press in 1987.
[36] C. H. Smith, R. Wiehagen, and T. Zeugmann. Classifying predicates andlanguages. International Journal of Foundations of Computer Science, 8:15–
41, 1997.
[37] F. Stephan. On one-sided versus two-sided classification. Technical Report
Forschungsberichte Mathematische Logik 25/1996, Mathematical Institute,
University of Heidelberg, 1996.
[38] R. Wiehagen. Characterization problems in the theory of inductive inference.
In G. Ausiello and C. Böhm, editors, Proceedings of the 5th International
Colloquium on Automata, Languages and Programming, volume 62 of Lecture
Notes in Computer Science, pages 494–508. Springer-Verlag, 1978.
[39] R. Wiehagen and C. H. Smith. Generalization versus classification. Journal of
Experimental and Theoretical Artificial Intelligence, 7:163–174, 1995.
[40] T. Zeugmann. A-posteriori characterizations in inductive inference of recursivefunctions. Journal of Information Processing and Cybernetics (EIK), 19:559–
594, 1983.
[41] T. Zeugmann. Algorithmisches Lernen von Funktionen und Sprachen. Habilitationsschrift, Technische Hochschule Darmstadt, Fachbereich Informatik,
1993.

39