SIIM -TR-A-07-06

SIIM Technical Report

Refutable Inductive Inference of Recursive Functions

by

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

Schriftenreihe der Institute für
Informatik/Mathematik
Serie AMay 11, 2001

Universität zu Lübeck
Technisch-Naturwissenschaftliche Fakultät
Email:

thomas@tcs.uni-luebeck.de

Phone:
Fax:+49-451-7030-422+49-451-7030-438

Refutable Inductive Inference of Recursive Functions
Sanjay Jain∗

Efim Kinber

School of Computing

Department of Computer Science

National University of Singapore

Sacred Heart University

Singapore 119260

Fairfield, CT 06432-1000, U.S.A.

sanjay@comp.nus.edu.sg

kinbere@sacredheart.edu

Rolf Wiehagen

Thomas Zeugmann

Department of Computer Science

Institut für Theoretische Informatik

University of KaiserslauternMed. Universität zu Lübeck

D-67653 Kaiserslautern

Wallstraße 40

Germany

23560 Lübeck, Germany

wiehagen@informatik.uni-kl.de

thomas@tcs.mu-luebeck.de

Abstract
Learning of recursive functions refutably informally means that for every
recursive function, the learning machine has either to learn this function or torefute it, that is 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 themost stringent of them turns out to be of remarkable topological and algorithmical richness. Furthermore, all these types are closed under union, though indifferent strengths. Also, these types are shown to be different with respect totheir 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, in general.
For learning with anomalies refutably, we show that several results fromstandard learning without refutation stand refutably. From this we derive somehierarchies for refutable learning. Finally, we prove that in general one cannot
trade stricter refutability constraints 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, that is the machine∗

Supported in part by NUS grant number RP3992710.

2

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmanncreates one or more hypotheses which eventually converge to a more or less correct andcomplete description of the object. In learning refutably the main goal is considerably
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 is philosophically motivated by Popper’s logic of scientificdiscovery (testability, falsibility, refutability of scientific hypotheses), see [33] and also[25], for a more detailed discussion. On the other hand, this approach has also somerather practical implications. Indeed, if the learning machine informs a user of its
inability to learn a certain object, then the user can react upon this inability, bymodifying the machine, by changing the space of hypotheses, or by weakening thelearning requirements, for example.
A crucial point of learning refutably is to make precise the notion of how themachine is allowed 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 in a “oneshot” manner, that is, if after some finite amount of time, the machine comes to theconclusion 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 somewhat
weaker possibilities of refuting are based on the following observation. Suppose thatat some time, the machine feels unable to learn the unknown object and signals thisby outputting the refuting symbol. However, this time the machine nevertheless keeps
trying to learn this object. And 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, this process of “alternations” can repeat. And it may end inlearning 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
symbol from 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 willallow and study all three of these modes of learning refutably.
Our universe is the class R of all recursive functions, that is all computable functions 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 shot manner
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 a correct 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).

Refutable Inductive Inference of Recursive Functions

3

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, thislemma 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 2. Already the most stringent of them, RefEx, turns out to be of remarkable topological and algorithmical richness (cf. Proposition 3 and Corollary 9).
Furthermore, all of these 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 tothe so-called intrinsic complexity; actually, both RefEx and WRefEx do not contain function classes that are “most difficult” to learn, while RelEx does contain suchclasses, see Theorems 6 and 7, 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 machines comesfrom and how it can be realized, in general (cf. Theorems 12 and 17).
Besides pure Ex-learning refutably we also consider Ex-learning with anomalies aswell as Bc-learning with anomalies refutably, see Definitions 21 and 22. We show thatmany results from standard learning without refutation stand refutably. From this wederive several hierarchies for refutable learning, thereby solving an open problem from[22], see Corollaries 22 and 29. Moreover, we prove that, in general, one cannot tradea stricter refutability constraint for a more liberal learning criterion (cf. Corollary 31
and Theorem 32).
Since the pioneering paper [30] learning with refutation has attracted much attention. The line initiated by [30], i.e., studying learning with refutation for indexedfamilies of languages, was also applied to learning of elementary formal systems in[31]. As a consequence of this model, if an indexed family of recursive languages canbe refutably learned from text then this class cannot contain any infinite language.
This limitation led Lange and Watson [25] to consider a more tolerant approach. In
their model a refuting learning machine is no longer required to refute every text describing a language outside the class to be learned. Instead, the machine has to refute
only such texts containing a finite sample being not contained in any language fromthe class to be learned. This indeed leads to a richer spectrum of indexed familiesof recursive 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 a natural interpretation of“unrepresentative”, the power of the justified refutation model has been shown toreach the power of the unrestricted model of learning languages from text.
Learning functions with refutation was considered by Miyahara [29] for indexedclasses of primitive recursive fuctions. For arbitrary classes of arbitrary recursive

4

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmannfunctions, an alternative approach has been developed and studied by Jantke [20] andGrieser [17]. In a sense, their approach is orthogonal to ours. Actually, on the one
hand, their model allows to learn richer classes than we can. On the other hand,in certain cases every machine that learns such a 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 whateverfunction from the universe.
The paper is organized as follows. In Section 2, we give the necessary notations
and definitions, as well as the Correctness Lemma. Section 3 deals with Ex-learning
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 −
i − j, if i ≥ j;
.
i−j=
0,
otherwise.
Let ∈, ⊆, ⊂, ⊇, ⊃, respectively, denote the membership, subset, proper subset,
superset and proper superset relations for sets. The empty set is denoted by ∅. We
let card(S) denote the cardinality of the set S. The minimum and maximum of aset S are denoted by min(S) and max(S), respectively. We take max(∅) to be 0 andmin(∅) to be ∞.
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 n-tuples ofnatural numbers in a natural way. η, with or without subscripts, superscripts, primes
and the like, ranges over partial functions. If η1 and η2 are 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(η) and range(η), respectively, denote the domain andrange of the partial function η. η(x)↓ and η(x) =↓ both denote that η(x) is definedand η(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:η(x), if x ∈ domain(η);
f (x) =r,otherwise.
We write r-ext(η) for the r-extension of η. R denotes the class of all recursive functions, 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 andS, with or without subscripts, superscripts, primes and the like, range over subsetsof R. For C ⊆ R, we let C denote R \ C. P denotes the class of all partial recursiveRefutable Inductive Inference of Recursive Functions

5functions over N. f, g, h and F , with or without subscripts, superscripts, primes andthe like, range over recursive functions unless otherwise specified.
A computable numbering (or just numbering) is a partial recursive function of twoarguments. For a numbering ψ(·, ·), we use ψi to denote the function λx.ψ(i, x). In
other words, ψi is the function computed by the program i in the numbering ψ. ψ
and % range over numberings. Pψ denotes the set of partial 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 recursive functions 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 i such that ψi = η. ϕ denotes a fixed acceptable
programming system (cf. [35]). We write ϕi for the partial recursive function computedby program i in the ϕ-system. We let Φ be an arbitrary Blum [6] complexity measureassociated with 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 (x), if x < s and Φi (x) < s;
ϕi,s (x) =↑,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 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 the accumulation
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 consideredbelow. Zero is the everywhere 0 function, i.e., Zero(x) = 0, for all x ∈ N. FINSUP ={f | (∀∞ x)[f (x) = 0]} denotes the class of all recursive functions of finite support.
2.1. Function Identification
We first describe inductive inference machines. We assume, that the graph of afunction is fed to a machine in canonical order.
For a partial function η such that η(x) is defined for all x < n, we write η[n] forthe 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 ofelements of SEG. Thus, one can talk about recursively enumerable subsets of SEG

6

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmannand comparison among members of SEG, that is σ < τ , if σ appears before τ in thisordering. Similary one can talk about the least element of a subset of SEG.
Let |σ| denote the length of σ. Thus, |f [n]| = n, for every total function f andall 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 say that 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 an i ∈ N suchthat 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)]}.
By the definition of convergence, only finitely many data points from a function fhave 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 this reason,
hereafter the terms identify, learn and infer are used interchangeably.
Definition 2 (Bārzdiņš [2]). Let f ∈ R and let M be an IIM.
(a) M Bc-identifies f (written: f ∈ Bc(M)) iff, for all but finitely many n ∈ 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 Exidentifies 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].

Refutable Inductive Inference of Recursive Functions

7

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 to refute a function.
First we need to extend the definition of IIM to allow a machine 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 anatural 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= ⊥.
(c) For all 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 themachine 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 6∈ Ex(M), M(f )↓ = ⊥.
For weakly refuting a function, the machine just needs to converge to the refutation
symbol ⊥. Before convergence, it may change its mind finitely many times 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 RelExlearning 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 6∈ Ex(M), there exists infinitely many n such that M(f [n]) = ⊥.
Proposition 1. RelEx = RelEx0 .
Proof. We first show that RelEx ⊆ RelEx0 .

8

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

Suppose M RelEx-identifies C. Define M0 as follows:M(f [n]), if n = 0 or M(f [n − 1]) = M(f [n]);0M (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:M(f [n]), if M(f [n]) 6= ⊥;0
M (f [n]) =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 arbitrarily 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 to belearned or to be refuted. We make this point formally precise by stating the following
Correctness Lemma. Informally, this lemma says that for every type of learning
refutably and for every machine that learns in the corresponding sense, one can trustin the correctness of every hypothesis from N the machine may converge to.
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 .
Proof. Directly from the definitions of RefEx, WRefEx and RelEx, respectively.
Using essentially the idea from Gold [14], (for Ex-identification), for I being anyof the learning criteria considered in this paper, one can show that:
There exists an r.e. sequence M0 , M1 , M2 , . . . of total inductive inference machines 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.
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Refutable Inductive Inference of Recursive Functions

9

strictly increasing power, where already the most stringent of these types, RefEx,
turns out to be of surprising richness. The first of these properties consists in thatany class from RefEx can be enriched by including all of its accumulation points.
Note that, in general, this is not possible for the classes from WRefEx and RelEx,
as it immediately follows from the proof of Theorem 2.
Proposition 2. For any C ∈ RefEx, C ∪ Acc(C) ∈ RefEx.
Proof. Informally, the result follows from the fact that in any type of refutable learning, any function f ∈ R, will either be identified or refuted. Since in RefEx-learning
an accumulation point can never be refuted, it has to be learned. Formally, supposeC ∈ RefEx as witnessed by total IIM M. Suppose g ∈ R is an accumulation pointof C. We claim that M must Ex-identify g. Assume to the contrary that for somen, 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, 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 20 below.
Proposition 3. 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 richness ofthe 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.
Proof. Assume to the contrary that there is an initially complete class C that is
WRefEx-learnable by some total IIM M.
Claim 1. For all σ ∈ SEG, there is a τ ∈ SEG such that σ ⊆ τ and M(σ) 6= M(τ ).
Proof. If for all extensions τ of σ, M(σ) = M(τ ), then M can Ex-identify at mostone extension of σ. But then C is not initially complete. 2

10

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

Now, let σi , i ∈ N, be defined such that σi can be obtained effectively from i,
σ0 = Λ, and for all i, σi ⊆ σi+1 and M(σi ) 6= M(σi+1 ). Note that this is possibleS
due to Claim 1. Now let f = i∈N σi . Clearly, f ∈ R, but M on f 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 2 below.
Lemma 2. 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) + 1, if σ(x)↓;τσ (x) =↑,otherwise.
. 1.
Let prog be a recursive function such that, for any program p, ϕ(x) = ϕ (x) −prog(p)pNote that by the s-m-n theorem, there exists such a recursive 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, areof strictly increasing power.
Theorem 2. RefEx ⊂ WRefEx ⊂ RelEx.
Proof. RefEx ⊆ WRefEx ⊆ RelEx follows easily from the 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, by Lemma 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 suchthat for any σ ∈ SEG+ , prog(σ) is a ϕ-program for 0-ext(σ). Let M be defined asfollows.
 ⊥,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 4.
As a consequence from the proof of Theorem 2, we can derive that the types
RefEx, WRefEx and RelEx already differ on recursively enumerable classes.

Refutable Inductive Inference of Recursive Functions

11

Corollary 3. RefEx ∩ NUM ⊂ WRefEx ∩ NUM ⊂ RelEx ∩ NUM.
Proof. Immediately from the proof of Theorem 2.
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 union.
Proof. In [28] it was shown that RelEx is closed under union. Now, suppose I ∈{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 thegiven function. It is easy to verify that C ∪ S ⊆ I(M).
Proposition 5 obviously applies also to the union of any finite number of classes.
RelEx is even closed under the union of any effectively given infinite sequence ofclasses, 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, and RelEx,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 for some learning type, if this class is “mostdifficult” to learn among all the classes from this learning type. As we will show, thetypes RefEx and WRefEx do not contain such complete classes, while RelEx does.
We now proceed more formally.
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 [35]). A recursive operator is an effective total mapping,Θ, from (possibly partial) functions to (possibly partial) functions, which satisfies thefollowing 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) ∈ Θ(α).

12S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

For each recursive operator Θ, we can effectively (from Θ) find a recursive operator
Θ such that0(d) for each finite function α, Θ0 (α) is finite, and its canonical index can be effectively 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. [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 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 4. Let C ∈ WRefEx. Then there exists a class S ∈ RefEx such that
S 6≤Ex C.
Proof. Suppose C ∈ WRefEx as witnessed by M. Note that for all recursive functions
f , M(f ) converges to a program for f , or converges to ⊥. In particular, there is norecursive function f on which M makes infinitely many mind changes. Based on
this we define a class S ∈ RefEx that is not Ex-reducible to C. Let Θ0 , Θ1 , . . . bean enumeration of the operators as in Proposition 6. We will construct S, with thefollowing 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.

Refutable Inductive Inference of Recursive Functions

13

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

Claim 5. For each i, there are only finitely many stages.
Proof. Otherwise M makes infinitely many mind changes on the recursive functionSΘi ( s∈N σs ).
2
For each i, one can effectively (in i) enumerate the initial segments which start withi, 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 ⊆ τ (in whichcase τ is extended by a function in S iff τ ⊆ 0-ext(σs−1 ) or τ ⊆ 1-ext(σ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 τ isinconsistent with both f0 [t] and f1 [t] (in which case τ is not extended by any functionin 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 and f ∈ 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 which is
executed, M(Θi (0-ext(σs ))) = M(Θi (1-ext(σs ))), where both 0-ext(σs ) and 1-ext(σs )are in S.
Theorem 4 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.

14

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

Theorem 7. 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 2. Hence, FINSUP is Ex-complete in RelEx.

3.3. Characterizations
We now present several characterizations for RefEx, WRefEx and RelEx. The
first group of characterizations relates refutable learning to the established concept ofclassification. The main goal in recursion theoretic classification can be 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 findout 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, more exactly, a class together with its complement; and semi-classification
which is some 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 their characteristic conditions are easily testable, i.e. they allow to check, whether or not a givenclass 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 theset {0, ?} and being everywhere defined.
Definition 13. A class S ⊆ R is called 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 any function from thatclass, 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 8. For any C ⊆ R, C ∈ RefEx iff C is contained in some class S ∈ 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.

Refutable Inductive Inference of Recursive Functions

c(f [n]) =150, 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 by somec ∈ 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 RefExlearnable. Moreover, C 6∈ NUM was shown in [40], Theorem 4.2. Hence, we get thefollowing corollary illustrating that RefEx contains “algorithmically rich” classes,that is classes being not contained in any recursively enumerable class.
Corollary 9. RefEx \ NUM 6= ∅.
We now characterize WRefEx.
Definition 14 (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 foralmost all n ∈ N, c(f [n]) = 0; and for any f ∈ S and for almost all n ∈ 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 case ofclassification, namely where the classes under consideration form a partition of theclass of all recursive functions, i.e. one class is just the complement of the other.
Definition 15. A class C ⊆ R is called classifiable iff (C, C) is classifiable.
Theorem 10. For any C ⊆ R, C ∈ WRefEx iff C is contained in some classifiableclass 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.
c(f [n]) =0, if M(f [n]) 6= ⊥;1, if M(f [n]) = ⊥.

Then, clearly, S is classifiable by c.

16

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

Sufficiency. Suppose C ⊆ S ⊆ Ex(M), and let S be classifiable by some c ∈ 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 16 (Stephan [37]). A class S ⊆ R is called semi-classifiable iff thereis 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 fromthis 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 no required evidence inthe limit to know where this function comes from.
Theorem 11. 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 theother 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. Hence c(f [n]) = ? forinfinitely 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.
M(f [n]), if c(f [n]) = 0;0
M (f [n]) =n,if c(f [n]) = ?.
Clearly, for any f ∈ S, for almost all n, c(f [n]) = 0. Hence M0 will Ex-identify 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Refutable Inductive Inference of Recursive Functions

17

in some Ex-learnable class the complement of which is finitely semi-classifiable. In
contrast, a class is RelEx-learnable if this class is contained in an Ex-learnable classthat 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, thecharacteristic conditions are stated here in terms that formally have nothing to dowith learning. And second, the sufficiency proofs being constructively again makeclear where the “refuting ability” of the corresponding learning machines comes fromin general. For stating the corresponding characterization of RefEx, we need thefollowing notions.
Definition 17. A numbering ψ is called strongly one-to-one iff there is a recursivefunction d of two arguments such that for any distinct i, j ∈ N, there exists anx < 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 caneffectively compute a bound on the least argument on which these functions differ.
Definition 18 (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 ofcompletely r.e. classes.
Lemma 3 ([34, 27]). For any Π ⊆ P, Π is completely r.e. iff there is an r.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 12. For any C ⊆ R, C ∈ RefEx iff there are numberings ψ and % suchthat(1) ψ is strongly one-to-one and C ⊆ Pψ ,(2) P% is completely r.e. and R% = Rψ .
Proof. Necessity. 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 recursive function such thatZ = range(e). For any i, j, x ∈ N , where e(i) = (z, n) and e(j) = (w, m), define

18

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann
ϕ (x), z
ϕz (x),
ψi (x) =↑,

if x < n;if x ≥ n and (∀y ≤ x)[ϕz (y)↓] and(∀y | n < y ≤ x + 1)[M(ϕz [y]) = M(ϕz [n])];otherwise.

andd(i, j) = max({n, m}).
Then it can easily be seen that ψ is a strongly one-to-one numbering as witnessedby the function d.
In order to show C ⊆ Pψ we prove a somewhat stronger result which is needed in
the following. Therefore, let S denote the class of all recursive functions that are
Ex-learnable by M. Clearly, C ⊆ S.
Claim 13. 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 , wheree(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 13 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)[σ ⊆ η]}.
Obviously, P% is completely r.e. by Lemma 3.
Claim 14. R% = Rψ .
Proof. By Claim 13, 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 14 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,

Refutable Inductive Inference of Recursive Functions

19

P% = {η | η ∈ P & (∃σ ∈ S)[σ ⊆ η]}. Let 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 15. M Ex-learns any function from Rψ .
Proof. Let f ∈ Rψ . First notice that then (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)] ⊆ ψj forsome 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 16. 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 15 and 16 complete the sufficiency proof.
It follows from the proof of Theorem 12 that in RefEx-learning the processes oflearning and refuting, respectively, can be nicely separated. Actually, in general, asuitable machine can be provided with two spaces, one for learning, ψ, and one forrefuting, %. If and when the “search for refutation” in the refutation space has beensuccessful, then the learning process can be stopped forever. This search for refutation is based on the property that the whole space for refutation forms a completely
r.e. class P% of partial recursive functions. Then, by the characterization lemma forcompletely r.e. classes, any system S of “representatives” for P% can serve as a set ofindicators for refutation. The spaces for learning and for refuting are interconnectedby the essential property that their recursive kernels, Rψ and R% , disjointly exhaustthe class of all recursive functions. This property eventually guarantees that eachrecursive 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 8. Intuitively, the characterization of Theorem 8 requires that one shouldbe able to find out anyhow if the given function does not belong to the class to be

20

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

learned. The characterization of Theorem 12 now makes precise how this task canbe done. Indeed, the set S may be thought as just sampling all possibilities of violating the structure of the functions from the class to be learned, thereby indicating
if and when the corresponding function has to be refuted. Furthermore, notice that
the RefEx-characterization of Theorem 12 is incremental to a characterization of Ex
in that the existence of a numbering with condition (1) above is just necessary andsufficient for Ex-learning the corresponding class C, see [38]. Finally, notice that therefutation 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 17. For every C ⊆ R, C ∈ RelEx iff there are a numbering ψ and afunction 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. Then, 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 ande(i) = f [n], letd(i) = nandψi (x) =f (x),
if x < n;ϕM(f [n]) (x), otherwise.

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 definitionof ψ, i0 ∈ Hf , where e(i0 ) = f [0]. For j ≤ m, let αj = e(ij ). Without loss ofgenerality, 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 contains a ψ-index of f . This proves condition (1). In
order to show condition (2) suppose f ∈ C. Then M converges on f . Consequently,
there are at most finitely many n ∈ 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 be such that for
any i ∈ N, ψi = ϕc(i) . Let amal be a recursive function mapping any finite set I

Refutable Inductive Inference of Recursive Functions

21of ψ-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 first value 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 withina 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 18. 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 . Therefore,+
Hf+ = limn→∞ Hf,nexists, and Hf+ contains exactly every i ∈ Hf such that ψ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 18 and condition (2), M identifies C.
It remains to show that M works reliably.
Claim 19. For any f ∈ R, if M converges on f , then M Ex-identifies f .
Proof. By Claim 18, it suffices to prove that if M converges on f , then Hf is finite.
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 17 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 17, for any function f from the class to belearned, 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 surethat the amalgamation technique succeeds in learning any such f . Conversely, theinfinity of this set Hf of candidates automatically ensures that the learning machineas defined in the sufficiency proof of Theorem 17 diverges on f . This is achieved by

22

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmanncausing 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 itturns out, many results of standard learning, i.e. without refutation, stand refutably.
Specifically, this yields several hierarchies for refutable learning. Furthermore, weshow that in general one cannot trade the strictness of the refutability constraints forthe 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 19 ([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 i suchthat 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 it isallowed to contain at most a anomalies. Note that Ex = Ex0 .
Definition 20 ([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 many n ∈ 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 will be mostly consider only Bca
for a ∈ 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 21. 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 6∈ Exa (M), there exists an n such that (∀m < n)[M(f [m]) 6= ⊥] and(∀m ≥ n)[M(f [m]) = ⊥].

Refutable Inductive Inference of Recursive Functions

23

Definition 22 (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 6∈ Bca (M), there exist infinitely many n such that 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 notlearnable refutably, even if we allow both the most liberal type of learning refutably,
namely reliable learning, and the very rich type of Bc-learning with an arbitrarily
large number of anomalies. For proving this result, we need the following 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 .
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 as follows:σ(x),if x < |σ|;gf (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 23 (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 that for 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 20. 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.

24

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

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).
In this case ϕe ∈ R∩C, and M outputs ⊥ on infinitely many initial segments of ϕ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 }, acontradiction to Proposition 7.
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-learningwith anomalies. Therefore, we need the following lemma.
Lemma 4. For every a ∈ N, there exists a function p ∈ R such that, for all i ∈ 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 recursive function p suchthat ϕ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 not been 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 tostep 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.

Refutable Inductive Inference of Recursive Functions

25

EndFor
4. If and when such a τ is found let,
5. ϕp(i) (x) = τ (x), for x < |τ | such that ϕp(i) (x) has not been defined upto now.
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) is satisfied. 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:
if x < xs or x > xs + a;
 ϕp(i) (x),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 21. For all a ∈ N, Ref Exa+1 \ Exa 6= ∅.
Proof. Let p be as in Lemma 4. Let Ci = {Zero} ∪ {f ∈ R0,1 | ϕp(i) ⊆ f }. LetS
C = i∈N Ci . By Lemma 4 (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(σ)

26

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

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 segment of f , outputs⊥. Also, if M(σ) = ⊥, then M(τ ) = ⊥, for all extensions τ of σ.
It follows that M Ref Exa+1 -identifies C.
Clearly, from Theorem 21 we immediately get the following hierarchy results, where
the last one was already obtained in [23].
Corollary 22. 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 4 can be used to show that
Lemma 5. 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 21 can be used to show the followingS
result. Notice that Ex∗ \ a∈N Exa 6= ∅ was proved in [10].
S
Theorem 23. Ref Ex∗ \ a∈N Exa 6= ∅.
From Theorem 21 we can derive further corollaries. Therefore, we need the following notation. For η ∈ P, let cylη be defined as follows: cylη (hx, yi) = η(x). For
C ⊆ R, let cylC = {cylf |f ∈ C}.
Proposition 8. (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 toverify 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 define M0
as follows:⊥,
if (∃x, y, z)[σ(hx, yi)↓ =6 σ(hx, zi)↓];⊥,
if M(uncylσ ) = ⊥;M0 (σ) =progcyl(p), if M(uncylσ ) = p and¬(∃x, y, z)[σ(hx, yi)↓ =6 σ(hx, zi)↓].

Refutable Inductive Inference of Recursive Functions

27

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 stands refutably.
Proposition 9. 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 (that is if
f 6∈ Ex∗ (M), then M on f outputs ⊥ infinitely often). Suppose C ∈ Bc as witnessedby 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.
Note that Bc \ Ex∗ 6= ∅ (cf. [10]). This result holds refutably, as our next corollaryshows.
Corollary 24. Ref Bc \ Ex∗ 6= ∅.
Proof. By Theorem 21, there exists a class C ∈ Ref Ex1 \ Ex. Thus, by Proposition 9,
there exists a class C ∈ Ref Bc \ Ex. Now, cylC ∈ Ref Bc \ Ex∗ , by Proposition 8.
The next corollary points out that already Ref Ex1 contains “algorithmically rich”
classes of predicates.
Corollary 25. 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 21. Then,by that proof, C ∈ Ref Ex1 \ Ex. Hence C ∈/ NUM, since NUM ⊆ Ex, see [15].
Corollary 25 can be even strengthened by replacing Ref Ex1 with RefEx. This
another time exhibits the richness of already the most stringent of our types of learning
refutably.
Theorem 26. 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)], denotescard({x | ¬P (x)}) ≤ n. In [8] it was shown that there exist recursive functions g andp 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)].

28

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

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.
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)]] &M(f [n]) =¬[(∃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 26 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 recursivefunctions, 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].
We now prove the analogue to Theorem 21 for Bca -learning rather than Exa learning. Note that Bca+1 \ Bca 6= ∅ was shown in [10]. We need the following
lemma.
Lemma 6. For any a ∈ N, there exist a recursive function p and a partial recursivefunction 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 p such thatϕp(i,j) may be defined as follows. For a fixed i, we will define ϕp(i,·) , and q(i, ·), inRefutable Inductive Inference of Recursive Functions

29

stages as follows. The construction can be easily seen to be effective in i. Notethat if ϕp(i,j) (x) (respectively q(i, y)) is not defined in stages 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 stage s.
Thus, x1 = i + 1. Go to stage 1.
Stage s1. 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 tostep 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 ∈ S , let ϕ(x) = 1 −(x).
sp(i,0)M(f [ms ])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 ).

30

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

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 27. For all a ∈ N, Ref Bca+1 \ Bca 6= ∅.
Proof. Let p and q be as in Lemma 6. Let{ϕp(i,0) },if {x | q(i, x)↓} = N.
Ci ={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 6, it follows that Ci 6⊆ Bca (Mi ).
Thus, C 6∈ Bca .
Let
MinO(σ) = min({x | σ(x) = 1}),Z1 = {σ ∈ SEG0,1 | MinO(σ) = i & (∃x ∈ N)[ϕp(i,0) (x)↓ =6 σ(x)↓]},
Z2 = {σ ∈ SEG0,1 | 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 28. 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.
z,if σ ⊆ Zero;


|σ|
|σ|
⊥,
if (∃τ ⊆ σ)[τ ∈ Z1 ∪ Z2 ];M(σ) =
 p(i, s), otherwise, where MinO(σ) = i, ands = max({x ≤ |σ| | q(i, x) converges within |σ| steps}).
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 to property(c.1) in Lemma 6,

31

Refutable Inductive Inference of Recursive Functions(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 27 yields the following hierarchies, where the last one solves anopen problem from [22].
Corollary 29. For every a ∈ N,
(1) Ref Bca ⊂ Ref Bca+1 ,(2) WRef Bca ⊂ WRef Bca+1 ,(3) RelBca ⊂ RelBca+1 .
Proposition 10. Ref Bc∗ \Saa∈N Bc 6= ∅.

Proof. Since R ∈ Bc∗ , see [10], we have that R ∈ Ref Bc∗ . Since R 6∈[10], proposition follows.

Saa∈N Bc , see

Recall that in the proof of Theorem 2 we have derived that FINSUP 6∈ WRef Ex.
This result will now be strengthened for WRef Bca -learning and then used in thenext corollary below.
Theorem 30. For every a ∈ N, FINSUP 6∈ WRef Bca .
Proof. Suppose by way of contradiction that M WRef Bca -identifies FINSUP . Then,by the Kleene recursion theorem there exists an e such that ϕe may be defined asfollows. Let xs denote the least x such that ϕe (x) has not been defined before stage s.
Stage s.
1. Let ϕe (xs ) = 1.
2. Search for a τ ∈ SEG0,1 such that ϕe [xs + 1] ⊆ τ and M(τ ) 6= ⊥.
3. If and when such a τ is found, for x > xs such that τ (x)↓, let ϕe (x) = τ (x).
Go to stage s + 1.
End Stage s.
We now consider two cases.
Case 1. All stages terminate.
In this case clearly ϕe is total, ϕe 6∈ FINSUP , and M(ϕe ) does not converge to ⊥.
Case 2. Stage s starts but does not end.
In this case M converges to ⊥ on all extensions of ϕe [xs + 1]. Thus, M does not
Bca -identify FINSUP .
From the above cases, the theorem follows.

32

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann

The following 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 31. For all a ∈ N, RelEx \ WRef Bca 6= ∅.
Proof. Follows from Theorem 30, 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 31 above.
Theorem 32. For all a ∈ N, WRef Ex \ Ref Bca 6= ∅.
Proof. Let(σi (x) =0, if x < i;1, if x = i;↑, otherwise.

Define Ci as follows: {0-ext(τ )}, if τ is the least extension (in SEG0,1 ) of σiCi =such that Mi (τ ) = ⊥;∅,otherwise.
S
Let C = {Zero} ∪ i∈N Ci . It is easy to verify that C ∈ WRef Ex. Suppose by way
of contradiction that Mi Ref Bca -identifies C. Then, we consider two cases.
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, thiscontradicts Proposition 7.
From the above cases it follows that Mi does not Ref Bca -identify C.
Note that Theorems 20, 30 and 32, and Corollary 31 hold even if we replace Bca
by any criterion of inference for which Proposition 7 holds.

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.

Refutable Inductive Inference of Recursive Functions

33[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 Theory ofComputing, 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 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 computable 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 of learning.
Information and Computation, 123(1):64–71, 1995.
[14] E. M. Gold. Limiting recursion. Journal of Symbolic Logic, 30:28–48, 1965.
[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.

34

S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann[17] G. Grieser. Reflecting inductive inference machines and its improvement by therapy. In S. Arikawa and A. Sharma, editors, Algorithmic Learning Theory: 7thInternational Workshop (ALT ’96), 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), 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. ofComputer 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 andCybernetics (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, 5thInternational 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.
[28] E. Minicozzi. Some natural properties of strong identification in inductive inference. Theoretical Computer Science, 2:345–360, 1976.

Refutable Inductive Inference of Recursive Functions

35[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: Fourth International Workshop (ALT ’93),
volume 744 of Lecture Notes in Artificial Intelligence, pages 123–136. SpringerVerlag, 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.
Journal of Symbolic Logic, 21:304–308, 1956.
[35] H. Rogers. Theory of Recursive Functions and Effective Computability. McGrawHill, 1967. Reprinted by MIT Press in 1987.
[36] C. H. Smith, R. Wiehagen, and T. Zeugmann. Classifying predicates and languages. 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.