TCS -TR-A-17-82

TCS Technical Report

On the Help of Bounded Shot Verifiers, Comparers,
and Standardisers in Inductive InferencebyZiyuan Gao, Sanjay Jain, Frank Stephan, andThomas Zeugmann

Division of Computer Science
Report Series A
November 4, 2017

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

thomas@ist.hokudai.ac.jp

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

On the Help of Bounded Shot Verifiers, Comparers,
and Standardisers in Inductive Inference
Z IYUAN G AOS ANJAY JAIN

Department of Mathematics

School of Computing

National University of Singapore

National University of Singapore

Singapore 119076

Singapore 117417

Republic of Singapore

Republic of Singapore

matgaoz@nus.edu.sg

sanjay@comp.nus.edu.sg

F RANK S TEPHANT HOMAS Z EUGMANN

Department of Mathematics

Division of Computer Science

National University of Singapore

Hokkaido University

Singapore 119076

N-14, W-9, Sapporo 060-0814

Republic of SingaporeJapanfstephan@comp.nus.edu.sg

thomas@ist.hokudai.ac.jp

Abstract. The present paper deals with the inductive inference of recursively enumerable languages
from positive data (also called text). It introduces the learning models of verifiability and comparability. The input to a verifier is an index e and a text of the target language L, and the learner has toverify whether or not the index e input is correct for the target language L. A comparator receives two
indices of languages from the target class L as input and has to decide in the limit whether or not these
indices generate the same language. Furthermore, standardisability is studied, where a standardiser
receives an index j of some target language L from the class L, and for every L ∈ L there must be
an index e such that e generates L and the standardiser has to map j to e. Additionally, the common
learning models of explanatory learning, conservative explanatory learning, and behaviourally
correct learning are considered. For almost all learning models mentioned above it is also appropriate
to consider the number of times a learner changes its mind. In particular, if no mind change occurs
then we obtain the finite variant of the models considered. Occasionally, also learning with the helpof an oracle is taken into consideration.
The main goal of the present paper is to figure out to what extent verifiability, comparability,
and standardisability are helpful for the inductive inference of classes of recursively enumerable
languages. Here we also distinguish between indexed families, one-one enumerable classes, andrecursively enumerable classes. Our results are manyfold, and an almost complete picture is obtained.
In particular, for indexed families and recursively enumerable classes finite comparability, finite
standardisability, and finite verifiability always imply finite learnability. If at least one mind change isallowed, then there are differences, i.e., comparability or verifiability imply conservative explanatory
learning, but standardisability does not; still explanatory learning can be achieved.

1

2

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

1. Introduction
The process of hypothesising a general rule from “eventually” complete positive data iscalled inductive inference. Philosophy of science has studied inductive inference during thelast centuries. Some of the principles developed are very much alive in algorithmic learningtheory. Computer scientists widely use their insight into the theory of computability toobtain a better and deeper understanding of processes performing inductive generalisations.
The present paper mainly deals with formal language learning, a field in which many
interesting and sometimes surprising results have been elaborated within the last decades(see Jain, Osherson, Royer, and Sharma [16]; Zeugmann and Zilles [24]) and the references
therein. Inductive inference of formal languages may be characterised as the study ofsystems that map evidence on a language into hypotheses about it. Of special interest is
the investigation of scenarios in which the sequence of hypotheses stabilises to an accurate
and finite description (a grammar) of the target language. If stabilisation is formalised
syntactically then we obtain explanatory learning (see Case and Smith [9]), which is also
called learning in the limit (see Gold [15]). Replacing syntactically by semantically results
in behaviourally correct learning (see Feldman [10], Barzdin [4, 5], Case and Smith [9]and Case [7]). A further special case is finite learning, where the learner outputs essentiallyjust one hypothesis which has to be a correct one. In the learning models described so far,evidence is provided by successively growing initial segments of any infinite sequence ofstrings that eventually contains all strings of the target language L and none of the strings
outside of L (such a sequence is called a text for L or a sequence of positive data for L).
The hypotheses output by the learner are natural numbers (also called indices). The
set of all admissible hypotheses is called the hypothesis space. In the present paper the
hypothesis space is any fixed universal numbering W0 , W1 , W2 , . . . of all recursively enumerable languages, which are identified with the recursively enumerable subsets of the natural
numbers, and any index is interpreted as a grammar. We are then in general interested in thelearnability of classes L of languages; i.e., we ask whether or not there is one learner thatcan learn every language L ∈ L.
Furthermore, in the present paper we consider learning scenarios in which evidence may
also be provided in the form of indices. We introduce the model of verifiability, where theevidence is any index e and a text of the target language L, and the learner has to verify
whether or not the index input is correct for the target language; i.e., whether or not We = L.
Second, we also define comparability, where the learner receives two indices of languages
from the target class L as input and has to decide in the limit whether or not these indices
generate the same language. Third, we study standardisability in the sense that evidence
is provided by any index j of a target language L from the class L. Then for every L ∈ L
there has to exist an index e such that We = L and the standardiser has to map j to e. This
mapping may be performed in the limit or just by outputting a single guess which then must
be e (called finite standardisability). Standardisability has been considered previously inthe literature (see, e.g., Kinber [18], Freivald and Wiehagen [12], Freivalds, Kinber, andWiehagen [13], and Jain and Sharma [17]).

On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference3

For almost all the learning models described above it is also meaningful to take a closer
look at the number of times a learner changes its mind. For the technical details we refer thereader to Definition 3.
The main problem studied in the present paper is the question to what extent verifiability,
comparability, and standardisability are useful for the inductive inference of classes ofrecursively enumerable languages. For example, we are interested in learning whether or not
a verifiable class is also explanatorily learnable, and if it is, whether or not the number ofmind changes is preserved. Table 1 provides a summary of the results obtained, where thelast three columns give the best obtained results for learning an Indexed, One–One R.E. or
R.E. class which is n-shot comparable/standardisable/verifiable as provided in the first twocolumns. In the table, Ex[A] denotes Ex-learning using oracle A, and a ? beside a criterion
denotes open problem at this point.
Notation

Shots

IndexedFin(Thm 1)

One-One R.E.
Fin
(Thm 1)

2

ConsvEx(Thm 7)

Ex (Thm 5),
ConsvEx?

3

Ex (Thm 9),
Not ConsvEx (Thm 11)

1

Comparator

4 and More
1
Standardiser

2
3 and More
1

Verifier2
3 and MoreNone
(Thm 13)
Fin(Cor 1)
Ex (Thm 4),
Not ConsvEx (Thm 12)
None(Thm 13)
Fin(Prop 2)
ConsvEx(Thm 6)
Ex (Prop 3),
Not ConsvEx(Thm 11)

ConsvEx[K](Thm 10),
Not Ex(Thm 3), BC?
None(Thm 13)
Fin(Cor 1)
Ex (Thm 4),
Not ConsvEx(Thm 12)
None(Thm 13)
Fin(Prop 2)
ConsvEx(Thm 6)
Ex (Prop 3),
Not ConsvEx(Thm 11)

R.E.
Fin(Thm 1)
Not Ex(Thm 2),
ConsvEx[K](Thm 8)None(Exmp 4)
None
(Thm 13)
Fin(Cor 1)None(Exmp 4)
None
(Thm 13)
Fin(Prop 2)
ConsvEx(Thm 6)
Ex (Prop 3),
Not ConsvEx(Thm 11)

Table 1: Summary of main results
The paper is structured as follows: Section 2 introduces the necessary notations, andin Section 3 the learning models studied in the present paper are defined. All results arepresented in Section 4. Finally, a summary is given and open problems are discussed.

4

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

2. Preliminaries
The notation and terminology from recursion theory adopted in this paper follows Rogers [21].
For background on inductive inference we refer the reader to Jain et al. [16] and Zeugmann
and Zilles [24].
We use N = {0, 1, 2, . . .} to denote the set of all natural numbers. The set of all partial
recursive functions and of all recursive functions from N into N is denoted by P and R,
respectively. We write R{0,1} to denote the set of all {0, 1}-valued recursive functions. Let
ϕ0 , ϕ1 , ϕ2 , . . . denote a fixed acceptable programming system (also called Gödel numbering)of all partial recursive functions (see Rogers[21]). Let W0 , W1 , W2 , . . . be a universal
numbering of all recursively enumerable sets (abbr. r.e. sets) of natural numbers, where We
is the domain of ϕe for all e ∈ N.
Let e, x ∈ N; if ϕe (x) is defined then we write ϕe (x) ↓ and also say that ϕe (x) converges.
Otherwise, ϕe (x) is said to diverge (abbr. ϕe (x) ↑). Furthermore, if the computation of ϕe (x)halts within s steps of computation then we write ϕe,s (x) ↓= ϕe(x) ; otherwise ϕe,s (x) ↑. For
all e, s ∈ N the set We,s is defined as the domain of ϕe,s .
Given any set S, we use S to denote the complement of S, and S ∗ to denote the set of
all finite sequences of elements from S. By D0 , D1 , D2 , . . . we denote any fixed canonicalindexing of all finite sets of natural numbers. We recall that Cantor’s pairing functionh · , · i : N × N → N is given by hx, yi = 21 (x + y)(x + y + 1) + y for all x, y ∈ N.
The symbol K denotes the diagonal halting problem, i.e., K = {e : e ∈ N, ϕe (e)↓}.
Furthermore, we use C(x) to denote the plain Kolmogorov complexity of x (see Li andVitányi [19, chap. 2]).
For any two sets A and B, we define A ⊕ B := {2x : x ∈ A} ∪ {2y + 1 : y ∈ B}.
Analogously, one defines A⊕B ⊕C = {3x : x ∈ A}∪{3y +1 : y ∈ B}∪{3z +2 : z ∈ C}.
We continue with some technical notations needed for our definitions of variants oflearnability. In the following we always assume that # ∈/ N. For any σ, τ ∈ (N ∪ {#})∗ , wewrite σ  τ iff σ = τ or τ is an extension of σ, and σ ≺ τ if and only if σ  τ and σ 6= τ .
Furthermore, for σ ∈ (N ∪ {#})∗ and n ∈ N we write σ(n) to denote the element in the nth
position of σ. Additionally, σ[n] denotes the sequence σ(0), σ(1), . . . , σ(n − 1). Given a
number a ∈ N and some fixed n ∈ N, n ≥ 1, we denote by an the finite sequence a, . . . , a,where a occurs exactly n times. Moreover, we identify a0 with the empty string λ. For any
finite sequence σ we use |σ| to denote the length of σ. The concatenation of two sequences σand τ is denoted by σ ◦ τ ; for convenience, and whenever there is no possibility of confusion,
this is occasionally denoted by στ .

3. Learnability
Let L be a class of r.e. languages. Throughout this paper, the mode of data presentation isthat of a text. A text is any infinite sequence of natural numbers and the # symbol, where thesymbol # indicates a pause in the data presentation. More formally, a text TL for a language

On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference5

L ∈ L is any total mapping TL : N → N ∪ {#} such that L = range(TL ) \ {#}. We use
content(T ) to denote the set range(T ) \ {#}, i.e., the content of a text T contains only thenatural numbers appearing in T . Furthermore, for every n ∈ N we use T [n] to denote thefinite sequence T (0), . . . , T (n − 1), i.e., the initial segment of length n of T . Analogously,
for a finite sequence σ ∈ (N ∪ {#})∗ we use content(σ) to denote the set of all numbers in
the range of σ.
The main learning criteria studied in this paper are explanatory learning (also called
learning in the limit) introduced by [15] and behaviourally correct learning, which goesback to Feldman [10], who called it matching in the limit. The name behaviourally correct
learning was coined by Case and Smith [9]. It was also studied by Barzdin [4, 5] andCase [8]. Furthermore, we shall also consider finite learning (see Gold [15]). In thefollowing definitions, an inductive inference machine (abbr. IIM) M is a recursive function
mapping (N ∪ {#})∗ into N ∪ {?}; the ? symbol permits M to abstain from conjecturing at
any stage.
Definition 1. Let L be any class of r.e. languages.
(1) An IIM M explanatorily (Ex) learns L if, for every L in L and each text TL for L, there
is a number n for which L = WM (TL [n]) and, for every j ≥ n, M (TL [j]) = M (TL [n]).
(2) An IIM M behaviourally correctly (BC) learns L if, for every L in L and each text TL
for L, there is a number n for which L = WM (TL [j]) whenever j ≥ n.
(3) An IIM M finitely (FinEx) learns L if, for every L in L and each text TL for L, there
is a number n for which L = WM (TL [n]) and for every m < n, M (TL [m]) = ? and forevery j ≥ n, M (TL [j]) = M (TL [n]).
(4) An IIM M (n+1)-shot learns L if it Ex learns L and for every text T for an L ∈ L there
are at most n distinct values k for which M (T [k]) 6=? and M (T [k]) 6= M (T [k + 1]).
Note that for finite learning the IIM itself indicates that it has successfully finished its
learning task, since the first hypothesis output, which is different from ?, is correct.
For every learning criterion I considered in the present paper, there exists a recursive
enumeration M0 , M1 , . . . of the learning machines such that if a class is I-learnable, thensome Mi I-learns the class. We fix one such enumeration of learning machines.
Angluin [1] considered an important condition for learnability of classes based on tell-talesets as defined below.
Definition 2. Assume L is a class of languages. A set S is said to be a tell-tale with respect
to L for a language L ∈ L if S ⊆ L, the set S is finite and for all L0 ∈ L, S ⊆ L0 ⊆ L
implies L = L0 .
The class L satisfies the tell-tale property if every L ∈ L has a tell-tale with respect to L.

6

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

It was shown by Angluin [1] and Baliga et al. [3] that every behaviourally correctly
learnable class of languages satisfies the tell-tale property.
In this paper, we consider a learning scenario in which the learner may not be required
to output a correct index for the target language (in the limit), but only has to (iii) verify
whether or not a given index is correct, or (i) to decide whether or not any two given r.e.
indices of sets in the target class are indices for the same set. We shall also study classes ofr.e. languages that can be finitely standardised in the sense that for a target class L, there
exists a partial-recursive function f such that for any given language L in L, there is an ewith We = L for which f outputs e when fed with any r.e. index for L. Replacing thefunction f by a limiting recursive function yields mutatis mutandis standardisation (in thelimit) of languages (see (ii) below). Finite standardisation was introduced by Freivald andWiehagen [12], while standardisation goes back to Kinber [18]. Their motivation was tostudy whether a given index of the object to be learnt is more useful than the graph of atarget function or a text of the target language. It was further investigated in Freivalds etal. [13] for function learning, and in Jain and Sharma [17] for the inductive inference of r.e.
languages.
Definition 3. Let L be any class of r.e. languages.
(i) The class L is said to be (n+1)-shot comparable if there is a partial-recursive function
F : N × N × N → {yes, no, ?} (called an (n + 1)-shot comparator for L) such thatfor all i, j ∈ N with Wi , Wj ∈ L,
(1) G(i, j) := lim F (i, j, k) exists and G(i, j) ∈ {yes, no};k→∞(2) G(i, j) = yes if Wi = Wj and G(i, j) = no if Wi 6= Wj ;(3) there are at most n distinct values of k for which F (i, j, k) ∈ {yes, no}, andF (i, j, k) 6= F (i, j, k + 1).
Intuitively, this means that F “changes its value” at most n times.1
A 1-shot comparable class will also be called finitely comparable.
(ii) The class L is said to be (n + 1)-shot standardisable if there is a partial-recursivefunction F : N × N → N ∪ {?} (called an (n + 1)-shot standardiser for L) such that(1) for all i with Wi ∈ L, G(i) := lim F (i, k) exists, G(i) ∈ N and WG(i) = Wi ;k→∞(2) for all i, j ∈ N with Wi , Wj ∈ L, G(i) = G(j) iff Wi = Wj ;(3) there are at most n distinct values of k for which F (i, k) ∈ N and F (i, k) 6=
F (i, k + 1).
1

In order to minimise notation, we will often omit the third argument in the definition of F and simply write“F changes its value at most n times”, where F is a given (n + 1)-shot comparator for a class; the meaning of
this statement will be clear from the context.

On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference

7

Intuitively, this means that F “changes its value” at most n times.2
A 1-shot standardisable class will also be called finitely standardisable.
(iii) M is said to verify L if on any input given by an index e for a language in L and a text
T for some perhaps different language in L, M converges to “yes” in the case that e
is an index for the language of the text and “no” if that is not the case; M is called averifier for L. Similarly one defines finite verifiability and (n + 1)-shot verifiability.
(iv) The class S is said to be finitely (m, n)-standardisable if there are n finitely standardisable classes S1 , S2 , . . . , Sn such that every L ∈ S is contained in at least m of theclasses S1 , S2 , . . . , Sn .

4. Verifiability, Comparability, Standardisability
We start this section with two examples that compare the power of verifiers with finite
learnability and explanatory learnability. Taking into account that the collection of all finitely
learnable classes is a proper subset of the collection of all explanatorily learnable classes,
these examples show that the power of verifiers is incomparable to the power of explanatory
learners.
Moreover, it is useful to have the following notions: A class L is said to be uniformly
r.e. (or just r.e.) if there is an r.e. set S ⊆ N such that L = {Wi : i ∈ S}. A class is said
to be 1–1 r.e., if the r.e. set S as above additionally satisfies the condition that for i, j ∈ S,
Wi = Wj iff i = j. An r.e. class as above said to be uniformly recursive or an indexedfamily if there exists a recursive function f ∈ R{0,1} such that for all i ∈ S and x ∈ N,
f (i, x) = 1 iff x ∈ Wi .
Example 1. The class K consisting of K and all singleton languages {x} with x ∈/ K isfinitely learnable but not finitely verifiable. A finite verification algorithm on an index efor K and a text x, x, x, x, . . . would have to eventually output “no” iff x ∈/ K and thatwould, combined with the enumeration procedure of K, lead to a decision procedure of K.
In order to show that K is finitely learnable we recall that every non-empty r.e. setis the range of a function f ∈ R. We define a numbering ψ : N × N → N as follows:ψ(x, y) := x if ϕx,y (x) ↑. If ϕx,y (x) ↓ then x ∈ K and then we set ψ(x, y) := ek if ek
is least such that 0 ≤ ek ≤ y, ϕek ,y (ek ) ↓ and ψ(x, ỹ) 6= ek for all ỹ < y. If there isno such ek , then ψ(x, y) := ψ(x, y − 1). Hence the range of ψ(x, · ) is K iff x ∈ K
and range(ψ(x, · )) = {x}, otherwise. Now, the finite learner outputs the canonical indexof ψ(x, · ) in the universal numbering W0 , W1 , W2 , . . . on input text T , if the first non-#symbol in the text T is x (that is, for some i, T (i) = x, and T (i0 ) = # for all i0 < i).
Note that the second part of the proof in Example 1 also shows that K is a uniformly r.e.
class.
2

As in the definition of an (n + 1)-shot comparator, we will often omit the second argument in the definitionof F and simply write “F changes its value at most n times” for any given (n + 1)-shot standardiser F for aclass.

8

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

Example 2. Consider a class L of languages which contains for every e ∈ N exactly one
language Le ⊆ {he, 0i, he, 1i, . . .} which is not empty and not behaviourally correctly learnt
by the learner Me . The class L is then verifiable by an algorithm which on input an index dand a text T enumerates the set Wd and tracks the text until a member (i, s) is enumerated
into Wd and a non-pause datum (j, t) is found in the text. Then the index d is for the languageof T iff i = j, as the verifier needs only to work on members of the class. However, by choice,
L is not behaviourally learnable.
Assume that a class L has an n-shot standardiser. Then the class is (2n − 1)-shot comparable.
This can be seen as follows: Let d and e be two indices such that both Wd and We are in L.
Then the algorithm runs two instances of the standardiser in parallel on the two inputs dand e, respectively, and waits until each of them has produced an output. If the two outputs
are equal, then the algorithm outputs “yes”, and if the two outputs are different, then it
outputs “no”. Note that the two instances must produce an output, since both Wd and We
are in L. Once this is done, every mind change of the comparator requires that at least oneof the standardisers makes another shot and so one can bound the number of shots of thecomparator by 1 + 2 · (n − 1) = 2n − 1. Hence, we have the following proposition:
Proposition 1. Every n-shot standardisable class is (2n − 1)-shot comparable.
Proposition 2. Let L be a uniformly r.e. class. Then we have the following: If L is finitely
verifiable, then L is also finitely learnable.
Proof. If a class L has a recursively enumerable list of indices, a finite verifier can be turned
into a finite learner by dovetailing the enumeration of the indices e0 , e1 , . . . and by simulating
the verifier on e0 versus T , e1 versus T , . . . until one of them outputs “yes”. The finite
learner then conjectures the first index ek , where the simulation gives the answer “yes”.
The following result is due to the learning algorithm, which for a recursive list of indicese0 , e1 , . . . of a class converges to the first index ek where the verifier is, on the text T ,converging to “yes” while the verifier converges, for all previous indices e0 , . . . , ek−1 ,to “no”.
Proposition 3. If an r.e. class is verifiable in the limit then it is also explanatorily learnable.
In order to show further results we need the following: A class L of languages is said to be
inclusion-free if there are no two languages A and B in the class L such that A ⊂ B.
Proposition 4. Any class which is 2-shot comparable must be inclusion-free. Thus, anyclass which is finitely standardisable must be inclusion-free.
Proof. If the class contains two sets A and B with A ⊂ B, and has a 2-shot comparator F ,then using the double recursion theorem (see Smullyan [22]), one can construct two grammars i and j such that Wi = Wj = A, if the comparator never outputs “yes” on input (i, j).
If the comparator outputs “yes” on input (i, j) at some point, and then never outputs “no”
after that, then Wi = A and Wj = B. Otherwise, Wi = Wj = B. So it follows that thecomparator is wrong on input (i, j).

On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference

9

Theorem 1. Every uniformly r.e. and finitely comparable class L is finitely learnable.
Proof. Suppose L is a finitely comparable class as witnessed by comparator F . First, by
Proposition 4, the class L must be inclusion-free.
Second one shows that if L is a uniformly r.e. class with an r.e. list e0 , e1 , e2 , . . . of indicescovering the class and if L is inclusion-free and finitely comparable then one constructs foreach k a set Wh(k) which is related to ek as outlined below.
For each ek , there is an index h(k) such that Wh(k) starts enumerating the elements enumerated into Wek until F (ek , h(k)) terminates and outputs “yes”. When this has happened,
let Dh0 (k) denote the set, given by canonical index h0 (k), of elements enumerated so far. Now
the algorithm searches for an index e` such that Dh0 (k) ⊆ We` and F (ek , e` ) has the value“no”. If this search terminates then Wh(k) = We` else Wh(k) = Dh0 (k) .
Third, this information can now be used to make the following finite learner M : M
reads elements of the text T until a k is found such that all members of Dh0 (k) have been
enumerated into T and then M conjectures ek for this k.
Fourth, for the verification of correctness, note that for each index ek , the function
F (ek , h(k)) must output “yes” as otherwise Wek = Wh(k) and both ek , h(k) are indices forthe same set in the class without F indicating this. Thus also h0 (k) is defined for all k. Now,
for each ek , Dh0 (k) ⊆ Wek and Wek is the only superset of Dh0 (k) in the r.e. class. The reason
is that in the search for e` after the definition of Dh0 (k) , the search cannot terminate for any k
as otherwise either F (ek , h(k)) or F (ek , e` ) for the ` found in the search are wrong; whenF (ek , h(k)) is right then Wek = We` and F (ek , e` ) had wrongly said that they are different.
So Wek is the only superset in the class of Wh0 (k) , although there might be several indicesfor Wek in the r.e. enumeration e0 , e1 , . . . of the indices. From the above it is easy to see thatthe learning algorithm is correct.
The next corollary follows from Proposition 1 and Theorem 1.
Corollary 1. Every uniformly r.e. and finitely standardisable class L is finitely learnable.
Remark. Note that a slight modification of the above proof gives that whenever a uniformly
r.e. class L is finitely comparable then L is also finitely standardisable and finitely verifiable:
The verifier just checks whether on input a text T and an index e the above constructed
learner M outputs on the text T an index d with F (d, e) having the value “yes”; thestandardiser outputs for an index d the first index ek in the given recursive enumeration,
where F (d, ek ) has the value “yes”.
Example 3. For each n ∈ N, n ≥ 1, let FINSn be the class of all sets of cardinality at
most n. Then FINSn is (2n + 1)-shot comparable but not 2n-shot comparable.
A (2n + 1)-shot comparator F works as follows: on input (i, j), F outputs “yes” at
the sth computational step if Wi,s = Wj,s and “no” otherwise. Therefore, if |Wi | ≤ n
and |Wj | ≤ n, F changes its value at most 2n times and its last value is correct, i.e., F isa (2n + 1)-shot comparator.

10

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

To see that FINSn is not 2n-shot comparable, by way of a contradiction let us assume
that such a 2n-shot comparator G does exist. In particular, the comparator G on any
input (i, j) such that |Wi | ≤ n and |Wj | ≤ n changes its value at most 2n − 1 times. By
the recursion theorem (see Rogers [21, chap. 11]), there are r.e. sets Wi and Wj for which
either (1) Wi = Wj = ∅ and G never outputs “yes” on input (i, j), or (2) there exists aleast m ≤ n such that Wi = {x : 0 ≤ x ≤ m − 1} and Wj = Wi \ {m − 1}, and G
on input (i, j) does not output “no” in the limit, or (3) there is a least m0 ≤ n such that
Wi = Wj = {x : 0 ≤ x ≤ m0 − 1} and G on input (i, j) does not output “yes” in the limit.
This contradicts the fact that G is a 2n-shot comparator for FINSn .
Example 4. The r.e. class L consisting of N and all sets N \ {x} with C(x) ≥ log(x),where C(x) denotes the plain Kolomogorov complexity of x (see Li and Vitányi [19, chap. 2]),
has the following properties:(i) The class is not behaviourally correctly learnable;(ii) the class is 2-shot standardisable but not finitely standardisable;(iii) the class is 3-shot comparable but not 2-shot comparable;(iv) the class is not verifiable.
Proof. The non-learnability follows from the fact that the set N does not have any tell-tale
set with respect to this class (see Angluin [1] and Baliga et al. [3]). This also implies thatthe class is not verifiable. The positive results are obtained by the following fact: From anindex e of N \ {x} and an upper bound on x, one can compute x by enumerating the set We
until all elements below the upper bound but x have shown up, as the upper bounds can havevery small Kolmogorov complexity compared to x, this means that all sufficiently large x
satisfy that either We 6= N \ {x} or C(x) < log(x). Hence there exists a recursive function fsuch that whenever We is of the form N \ {x} with C(x) ≥ log(x) then we have x < f (e).
Thus a 2-shot standardiser would first enumerate the elements of We below f (e) until all but
one x have shown up. Then the learner outputs an index g(x) computed from x from theset N \ {x}. Once this element x is also enumerated into We , the standardiser revises the
hypothesis and outputs a fixed index for N.
However, the class is not finitely standardisable, as it is not inclusion-free; for the same
reason it can also not be 2-shot comparable. The 3-shot comparability follows from thegeneral implication that every 2-shot standardisable class is 3-shot comparable.
We continue with further properties of the r.e. class K defined in Example 1. Recall that K is
finitely learnable.
Example 5. The uniformly r.e. class K is neither finitely comparable nor finitely standardisable.
The proof is in both cases indirect. Suppose the converse, and let k ∈ N be any fixedindex of K, i.e., Wk = K. Then one can design an algorithm deciding K. This algorithmOn the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference

11

uses the numbering ψ constructed in the second part of the proof of Example 1. Using
standard techniques, one obtains from ψ a numbering χ such that the range of ψi is equal
to the domain of χi for every i ∈ N. Since the numbering of the sets W0 , W1 , W2 , . . . isuniversal, there is a recursive function c ∈ R such that χx = ϕc(x) for all x ∈ N. Hence theset Wc(x) is equal to K iff x ∈ K and equal to {x} iff x ∈/ K.
Consequently, for every x ∈ N one runs the finite comparator on input c(x) and k. Notethat by construction, Wk , Wc(x) ∈ K for all x ∈ N, and thus the finite comparator must be
defined on all these inputs. Also, it must return “yes” iff Wc(x) = K and “no” otherwise; acontradiction to the undecidability of the set K.
For the finite standardiser the algorithm works mutatis mutandis. First, we run it on
input k to find out to which index k is finitely standardised, say to s. In order to decide K one
executes the finite standardiser on input c(x) for any given x ∈ N. If it returns s, then x ∈ K
and otherwise x ∈/ K.
Remark. Example 5 shows in particular that finite learnability does not imply finite standardisability if learning of r.e. languages is considered. This contrasts the corresponding
result for learning classes of recursive functions, where every finitely learnable function
class is also finitely standardisable (see Freivald and Wiehagen [12]).
However, 2-shot comparable classes do not need to be learnable in the limit (cf. Theorem 2).
Theorem 2. There is an r.e. 2-shot comparable class which is not explanatorily learnable.
Proof. The class consists of languages Le,x which are defined as follows:(i) 2e is the unique even element of Le,x ;(ii) for each e there is an “event-horizon” te,s which moves up in stages (that is, te,s ismonotonically non-decreasing in s) and converges to a limit value te ∈ N ∪ {∞};
(iii) if x < te or C(x) < log(x) then Le,x contains besides 2e all odd numbers below te
and all odd numbers 2y + 1 with C(y) < log(y); and(iv) if x > te and C(x) ≥ log(x) then Le,x contains 2e, 2x + 1 and all odd numbers
below te .
For the ease of notation, let z be a fixed element with C(z) < log(z). In the case that te = ∞,for all x, Le,x = {e} ⊕ N.
Now one defines the movements of the te through a diagonalisation of the explanatory
learner Me on a text constructed as the limit of sequences σ0 , σ1 , . . .; at the beginning, σ0 isjust the single entry 2e and te,0 = 0. At stage s > 0, one assumes that only numbers below s
are enumerated into sets Le,x . Now one searches for an x with te,s ≤ x < (s2 − 1)/2, suchthat Me makes a mind change somewhere on the way from Me (σs ) towards Me (σs (2x+1)s ).
If this x is found then one sets te,s+1 = s2 and σs+1 to be the extension of σs (2x + 1)s12Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

which contains all the data {2x + 1 : 2x + 1 < s2 } ∪ {2e}; else one defines te,s = te,s−1
and σs = σs−1 .
If te = ∞ then this construction produces a text for Le,z on which Me does not converge
and Me does not learn Le,z . If te < ∞ then Me learns at most one of the Le,x with x > te andC(x) ≥ log(x), as on each of the texts σte (2x + 1)∞ for these Le,x the learner converges tothe same index Me (σte ). Thus the class does not have any learner which learns it in the limit.
The class is also r.e., since one can take a canonical enumeration of the Le,x with e, x ∈ N.
Note that if We0 = Le,x 6= Le,z , then, C(x) ≤ 2 log(e0 ) + 2 log(e) + log s + const, where s
is maximal such that te,s 6= te,s+1 . Since x > te ≥ s2 , we havelog(te ) ≤ C(x) ≤ 2 log(e0 ) + 2 log(e) + 0.5 log(te ) + const , or
0.5 log(te ) ≤ 2 log(e0 ) + 2 log(e) + const .
Thus, one can compute for each index e0 with We0 containing a number 2e, an upperbound f (e, e0 ) such that whenever te > f (e, e0 ) then either We0 = Le,z or We0 is not in theclass.
To see that the class is 2-shot comparable, consider any indices e0 , e00 of languages in theclass; if the languages are not in the class, then the comparator can do whatever it wants,
including remaining undefined. On e0 , e00 , the comparator waits until each of them enumerates
an even number; if e0 , e00 are indices for languages in the class, then these must show up andbe unique. If these even numbers are different, the comparator just guesses “no” and does notchange the mind. If they are the same number 2e then the comparator simulates We0 and We00
until a stage s > f (e, e0 ) + f (e, e00 ) is reached such either te,s > f (e, e0 ) + f (e, e00 ) or x0 , x00
have been found such that te,s < (2x0 +1), te,s < (2x00 +1), 2x0 +1 ∈ We0 and 2x00 +1 ∈ We00 .
In the case that te,s > f (e, e0 ) + f (e, e00 ), the comparator conjectures “yes”, as both setsare equal to Le,z . In the case that x0 , x00 are found, the comparator checks whether x0 = x00 .
Now if x0 = x00 then the comparator conjectures “yes”, else the comparator conjectures“no”; furthermore, the comparator makes in the latter case a mind change from “no” to “yes”
iff either te,∞ > f (e, e0 ) + f (e, e00 ) or both C(x0 ) < log(x0 ) and C(x00 ) < log(x00 ). These
conditions imply that both sets are equal to Le,z ; for the verification also note that te iseither te,s or larger than f (e, e0 ) + f (e, e00 ), so that whenever te,s becomes updated to a larger
number, this is immediately above f (e, e0 ) + f (e, e00 ).
The next lemma states that any uniformly r.e. class of infinite sets that is n-shot comparable
can be expanded to a 1–1 r.e. class that is (n + 1)-shot comparable. This will allow us toextend Theorem 2 (albeit in a weaker form) to 1–1 r.e. families.
Lemma 1. Assume L = {Wf (i) : i ∈ N} is an r.e. class of infinite languages, each of whichis contained in {h1, xi : x ∈ N}, where f ∈ R. Suppose that L is n-shot comparable. Then
there is a 1–1 r.e. class L0 of infinite languages such that L ⊆ L0 and L0 is (n + 1)-shot
comparable.
Proof. Let L be the class as given in the lemma. Let h(i, t) be a recursive function suchthat limt→∞ h(i, t) = 1 iff for all j < i, Wf (j) 6= Wf (i) . Note that such a recursive h can beOn the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference

13

easily constructed. Also note that in case Wf (j) = Wf (i) for some j < i, then limt→∞ h(i, t)
may not exist. Let Ui,t = Wf (i) if t is minimal such that h(i, t0 ) = 1 for all t0 ≥ t. Otherwise,
let Ui,t = {h1, xi : x < hi, t, zi} ∪ {h0, hi, t, zii} ∪ {h2, xi : x ∈ N}, where z is the least
number t0 ≥ t such that h(i, t0 ) = 0 (the element h0, hi, t, zii ensures that Ui,t 6= Uj,swhenever hi, ti =6 hj, si). Clearly, L0 = {Ui,t : i, t ∈ N} is a 1–1 r.e. class which is (n + 1)shot comparable. The comparator essentially uses the comparator for {Wf (i) : i ∈ N} until
it finds that one of the languages contains h0, yi, for some y. Then it waits for either h0, y 0 i
or some element h1, zi with z > y, to appear in the other language, and then outputs thecorrect comparison as “yes” iff h0, y 0 i appears in the other language with y 0 = y.
We now deduce the following theorem from Lemma 1 and Theorem 2:
Theorem 3. There is a 1–1 r.e. 3-shot comparable class which is not explanatorily learnable.
Proof. One can cylindrify the 2-shot comparable and uniformly r.e. class {Le,x : e, x ∈ N}
constructed in the proof of Theorem 2; i.e. we define Ue,x = {h1, hy, zii : y ∈ Le,x ∧ z ∈ N}
for all e, x ∈ N, to obtain a uniformly r.e. class L of infinite languages which is containedin {h1, zi : z ∈ N}. Note that L, like the uniformly r.e. class in the proof of Theorem 2, is
not explanatorily learnable. Lemma 1 then gives a 1–1 r.e. class L0 such that L0 ⊇ L, L0 is
3-shot comparable and L0 is not explanatorily learnable.
Example 6. Assume that each language in L contains exactly one even element and that notwo languages in L contain the same even element. Then L is finitely verifiable and finitely
comparable. However, one can choose the sets in L such that the e-th behaviourally correct
learner does not converge to the right index on the text for the language in L with the evenelement 2e and similarly one can also fool the standardiser and thus this class L can bechosen such that it is neither behaviourally correctly learnable nor standardisable in thelimit.
Proposition 5. If a class is n-shot learnable then it has a 2n-shot comparator.
Proof. Assume that L has an n-shot learner M . Without loss generality assume that M does
not use more than n-shots on any text, even for texts for languages outside L. On input (d, e),a 2n-shot comparator F for L builds σ1 , σ2 , . . . , σn as follows (some of these σi may not
be defined): Initially, it searches for σ1 with content(σ1 ) ⊆ Wd ∪ We such that M (σ1 ) 6=?.
Then, inductively, after defining σi , it searches for a σi+1 such that σi+1 is an extension of σi ,content(σi+1 ) ⊆ Wd ∪ We and M (σi ) 6= M (σi+1 ) 6=?. The comparator F outputs ? until σ1gets defined. After that, at any stage s, it considers the last σi that is defined, and outputs “yes”
iff σi ⊆ Wd,s ∩ We,s ; otherwise, it outputs “no”. As the learner M is a n-shot learner, thecomparator is a 2n-shot comparator, as it possibly starts with “no” output and then perhaps
changes to “yes” output for each σi . Now assume both Wd , We are in L. If Wd = We , thenclearly all σi will satisfy that content(σi ) ⊆ Wd ∩ We and thus the comparator will converge
to “yes”. If Wd 6= We , then for the last σi that gets defined, content(σi ) 6⊆ Wd ∩ We ,as otherwise, the learner converges on texts for Wd or We which extend σi , to the same
conjecture, contradicting that M explanatorily learns both.

14

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

Theorem 4. If a class has a 2-shot standardiser and has a one-one r.e. numbering, then it isexplanatorily learnable.
Proof. Assume that F is a 2-shot standardiser for L = {Wh(0) , Wh(1) , . . .}, where h is arecursive function with Wh(i) 6= Wh(j) for i 6= j.
Below, we will have that grammars h(j) would be either in group 1 or group 2. They are
in group 1, if F (h(j)) outputs at most one grammar, and in group 2, if F (h(j)) outputs twogrammars. Let F 1 (h(j)) denote the first and F 2 (h(j)) denote the second grammar output
by F on h(j).

Algorithm 1: Construction of Wg1 (i,j) and Wg2 (i,j) , for i 6= j(i) Wg1 (i,j) starts simulating Wh(i) until it observes that current values of F (g1 (i, j)) andF (h(i)) are same and not in {F 1 (h(j)), ?}. Then, suppose that Wg1 (i,j) enumerated
up to now is S1,i,j . For g2 usage, correspondingly, we use F 2 (h(j)) and S2,i,j .
(ii) Wait until Wh(j) contains S1,i,j .
(iii) Simulate Wh(j) until F (g1 (i, j)) becomes equal to F 1 (h(j)). Note that this means
F (g1 (i, j)) must have output second value.
Let R1,i,j denote the Wg1 (i,j) enumerated up to now. Note that if the algorithm reaches
this step, the above must eventually succeed.
Go to Step (iv)
For g2 usage, correspondingly, we use F 2 (h(j)) and R2,i,j .
(iv) Now, Wg1 (i,j) searches for a k 6= j such that Wh(k) contains R1,i,j , and then switches
to simulating Wh(k) .
Similarly, Wg2 (i,j) searches for a k 6= j such that Wh(k) contains R2,i,j , and thenswitches to simulating Wh(k) .
Note that above should never happen (except when g1 ’s assumption about F (h(j))
outputting only one grammar is wrong).
Thus, R1,i,j (or R2,i,j ) would be a characteristic sample for Wh(j) .
Let g1 (i, j) (similarly g2 (i, j)), i 6= j, be defined such that Wg1 (i,j) and Wg2 (i,j) are asin Algorithm 1. Note that g1 (i, j) and g2 (i, j) (for i 6= j) are similar, except that theywork on grammars h(j) from group 1 or 2 respectively, thus in Algorithm 1, g2 (i, j) would
correspondingly start only after F (h(j)) has output the second grammar.
A grammar h(j) starts in group 1 and then later may move to group 2. Within eachgroup, it starts in active list, moves to cancelled list, and then to “correct grammar” list when
the characteristic sample as in Algorithm 1 is observed. Note that a grammar which is inOn the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference

15

cancelled list/correct grammar for group 1 may move to group 2 at some point (where it
starts as active grammar).
A grammar h(j) in active list in group 1 (group 2) gets cancelled if there exists i 6= jsuch that S1,i,j (respectively, S2,i,j ) gets defined and is contained in the input.
A grammar h(j) in group 1 (group 2) becomes “correct grammar” when the input
contains R1,i,j (respectively R2,i,j ) for some i 6= j.
The learner outputs the least grammar which is not in cancelled list (irrespective of whichgroup it belongs to).
Note that if h(j) is the correct grammar for input, then eventually for all i < j, S1,j,i(or S2,j,i , in case F (h(i)) outputs two grammars) would get defined, and thus h(i) would
go to cancelled list of that group. It will not move to “correct grammar” list of the eventual
group h(i) is in, as otherwise, g1 (j, i) or g2 (j, i) would then be able to follow h(j), forcing F
to make three outputs on g1 (j, i) or g2 (j, i) based on which group h(i) belongs to.
If h(j) gets into cancelled list of group 1 (or group 2) due to some h(i), i 6= j, (thatis S1,i,j or S2,i,j getting defined), then eventually it moves to the correct grammar list in
the corresponding group as g1 (i, j) (or g2 (i, j) respectively) would eventually have Step (ii)and (iii) succeed as S1,i,j was in the input text and thus in Wh(j) .
Thus, eventually h(j) is the grammar which is output by the learner.
Example 7. The graphs of the functions with only finitely many non-zero values, is 2-shot
comparable and 2-shot verifiable and has a one-one enumeration. However, this classcannot be learnt by any confident learner even if it uses an oracle. Thus there is no upperbound on the number of shots of the learner.
Here a confident learner (see Osherson et al. [20]) is a learner which converges to somehypothesis on all texts, even for texts for languages not in the class being learnt.
An analogue of Algorithm 1 (see the proof of Theorem 4) shows that any 2-shot comparable
r.e. class with a one-one numbering is explanatorily learnable.
Theorem 5. If a class L has a 2-shot comparator and a one-one r.e. numbering, then L is
explanatorily learnable.
Proof. We adopt the notation of the proof of Theorem 4. Let {Wh(0) , Wh(1) , . . .} be a oneone r.e. numbering of a class L and let F be a 2-shot comparator for L. Given any i, j ∈ Nwith i 6= j, define a recursive function g so that Wg(i,j) is as in Algorithm 2.
An Ex learner M for L runs Algorithm 2 and does the following: Each index may be
assigned one of two possible states, “cancelled” or “correct”. An index j is assigned the state“cancelled” if there is an i 6= j such that Si,j is contained in the range of the input text but j
is not in state “correct”; it is assigned the state “correct” if, for some i 6= j, Ri,j is containedin the range of the input text. Furthermore, the state of an index may change at any stage(or it may not be assigned any state at all). At each stage, M outputs the least index j such

16

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmannthat j is not in a “cancelled” state (note that in particular, j may not have been assigned any
state up to the current stage).

Algorithm 2: Construction of Wg(i,j) , for i 6= j(i) Enumerate Wh(i) into Wg(i,j) until F (g(i, j), h(j)) = no. Let Si,j be the set ofelements enumerated into Wg(i,j) up to the point where F (g(i, j), h(j)) outputs “no”.
(ii) Wait until Wh(j) contains Si,j (if Si,j 6⊆ Wh(j) , then this step does not terminate).
(iii) Enumerate Wh(j) into Wg(i,j) until F (g(i, j), h(j)) outputs “yes” (after the above“no”). Let Ri,j be the set of elements enumerated into Wg(i,j) up to this point.
(iv) Wait until Wh(k) contains Ri,j for some k 6= j; Wh(k) is then enumerated into Wg(i,j) .
(Note that this step should never succeed, because otherwise g(i, j) would be an r.e.
index for Wh(k) such that F (g(i, j), h(j)) changes its value at least twice, from “no”
to “yes” and then to “no” again.)Suppose that M is fed a text T for Wh(j) . As argued in the proof of Theorem 4, if theindex j is assigned the state “cancelled” at any stage, then it will eventually be assigned thestate “correct” and its state will henceforth never change. On the other hand, for every i < j,the index i will eventually be assigned the state “cancelled”, since Sj,i is contained in
the range of the text T . Also, it will never be assigned the state “correct” after being inthe state “cancelled”, since otherwise there would be some j 0 6= i such that Algorithm 2
on input (j 0 , i) goes through Step (iv), resulting in g(j 0 , i) becoming an index for Wh(k)with k 6= i, and F (g(j 0 , i), h(i)) changing its value at least twice, a contradiction.
Next, we turn our attention to conservative learning of uniformly r.e. classes of languages.
A learner M is said to be conservative if the following condition is satisfied: If M on
input T [n] makes the guess jn and then makes the guess jn+k at some subsequent step on
input T [n + k], where k ≥ 1, and jn 6= ? 6= jn+k then content(T [n + k]) 6⊆ Wjn . Intuitively
speaking, a conservative learner performs exclusively justified mind changes. In particular, aconservative learner can never overgeneralise; i.e., it can never guess a proper superset of
the target language (see, e.g., Angluin [1], Zeugmann, Lange and Kapur [23], and Jain etal. [16]). We use ConsvEx to express that a class has a conservative explanatory learner.
Theorem 6. If a uniformly r.e. class L is 2-shot verifiable, then L is ConsvEx learnable.
Proof. Let L = {Wf (0) , Wf (1) , Wf (2) , . . .} be a uniformly r.e. class that has a 2-shot verifier h, where f is a given recursive function. By Gao et al. [14, Observation 35], it suffices
to show that L has an Ex learner N such that for every L ∈ L, N does not conjecture asuperset of L on any segment of any given text for L.

On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference

17

Let T be any given text, define a learner M as follows: on input T [n], M outputs f (i)for the least i ≤ n such that h outputs “yes” on (f (i), T [n]); if no such i exists, then Mjust outputs its prior conjecture (or an r.e. index for the empty set if n = 0). Suppose T isa text for some Wf (e) ∈ L. Let ` be the least index such that Wf (`) = Wf (e) . Then for all
sufficiently large m, h will output “no” on pairs (f (`0 ), T [m]) for each `0 < `, while h will
output “yes” on (f (`), T [m]). As a 2-shot verifiable class is inclusion-free, M will never
output a proper superset on input languages from the class.
As any class which is 2-shot comparable is inclusion-free, it is easy to show the following
result:Theorem 7. Every indexed family which is 2-shot comparable is ConsvEx learnable.
Furthermore, as the membership problem for indices of r.e. sets can be solved using K
as an oracle, we obtain the following theorem:
Theorem 8. Every uniformly r.e. class L which is 2-shot comparable is ConsvEx[K]learnable.
Proof. By Proposition 4 we know that any class which is 2-shot comparable must be
inclusion-free. Let e0 , e1 , . . . be any fixed enumeration of the class L. Consequently, thealgorithm, which has access to the K-oracle always takes the enumeration e0 , e1 , . . . of theindices of the class L and conjectures the first en such that either n is the number of data
items seen so far or Wen contains all the data observed. The first case is only included to
avoid partialness of the K-recursive learner.
In order to see that the learner is conservative we use that L is inclusion-free. Hence,on each wrong hypothesis en the learner will eventually see a counterexample, that is, anelement outside Wen and drop it eventually.
We have seen that for indexed families, 1-shot comparability implies finite learnability (Theorem 1) while 2-shot comparability implies conservative explanatory learnability (Theorem 7).
The next theorem completes this fairly neat hierarchy of learnability notions implied byn-shot comparability for indexed families: 3-shot comparability, while insufficient for guaranteeing conservative learnability (see Theorem 11), still implies explanatory learnability.
We first show that 3-shot comparable 1-1 r.e. classes have uniformly r.e. families of finite
tell-tale sets.
Proposition 6. Assume L = {U0 , U1 , . . .} is a 1–1 r.e. class with Ui 6= Uj for i 6= j.
Suppose L is 3-shot comparable. Then one can effectively (in i) enumerate tell-tale setsfor Ui with respect to L.
Proof. Assume that F is a 3-shot comparator for L = {U0 , U1 , . . .}.
Let g, h be recursive functions, obtained via the operator recursion theorem (see Case [6]),such that Wg(e,d) and Wh(e,d) are defined as follows for e 6= d:18

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

1. Wg(e,d) and Wh(e,d) follow Ud , until it is observed that F (g(e, d), h(e, d)) = “yes”.
Assume that Wh(e,d) , enumerated until now, is Se,d .
2. Wg(e,d) continues to follow Ud . Wh(e,d) waits until it is observed that Se,d ⊆ Ue . Then,
Wh(e,d) starts following Ue until it is observed that F (g(e, d), h(e, d)) = “no” (after
the above observed “yes”). Assume that Wg(e,d) enumerated until now is Re,d .
3. Wh(e,d) continues to follow Ue and Wg(e,d) waits until it is observed that Re,d ⊆ Ue .
Then, Wg(e,d) starts following Ue until it is observed that F (g(e, d), h(e, d)) = “yes”(after the above observed “no”). Assume that Wg(e,d) enumerated until now is Xe,d .
4. Wh(e,d) continues to follow Ue and Wg(e,d) waits until it is observed that Xe,d ⊆ Uk ,for some k 6= e. Then, Wg(e,d) starts following Uk . Note that the above search should
never succeed, as otherwise, F (h(e, d), g(e, d)) needs to output “no” in the limit, but
it has no more mind changes available.
Thus, Xe,d (if defined) is a subset of Ue but not contained in any Uk , where k 6= e.
Note also that if Ud ⊆ Ue , then the above process must reach Step 4, though it would
not succeed in finding k. This happens as Se,d is always defined due to the comparator
F (g(e, d), h(e, d)) needing to eventually output “yes” when both g(e, d) and h(e, d) arefollowing Ud . Since we have Se,d ⊆ Ud ⊆ Ue , Step 2 will eventually succeed in finding
this, and thus Wh(e,d) would start following Ue . Hence eventually F (g(e, d), h(e, d)) needs
to output “no” and the procedure will reach Step 3. Here again Re,d ⊆ Ud ⊆ Ue , andtherefore Wg(e,d) would also start following Ue and thus eventually F (g(e, d), h(e, d)) will
output “yes”, and the process will reach Step 4.
Thus, we have the following:(a) if Ue has no proper subset in L, then ∅ is a tell-tale set for Ue ;(b) if Ue has a proper subset in L, then there exists a d such that Xe,d as above gets defined;(c) for any e, d, if Xe,d get defined then Xe,d is a tell-tale set for Ue with respect to L.
It thus follows that one can enumerate tell-tale sets for members of L: on input e, thetell-tale set enumerator initially just enumerates ∅, and searches for a d such that Xe,d isdefined by the above process. It then enumerates Xe,d .
The following theorem now follows from the characterisation of explanatory learnability
using tell-tale sets by Angluin [1] (and the fact that every indexed family containing infinitely
many distinct sets has a 1–1 r.e. numbering).
Theorem 9. Any 3-shot comparable indexed family is explanatorily learnable.

On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference

19

When given an oracle for K, a 1–1 r.e. family behaves like an indexed family for the purposesof the earlier proof of Proposition 6. Furthermore, using an oracle for K and an analogue ofthe construction of Wg(e,d) , Wh(e,d) in Proposition 6, one can determine for each member L ofa 1–1 r.e. family L = {U0 , U1 , U2 , . . .} a finite tell-tale set for L w.r.t. L as follows: First, test
whether or not there exists a j 0 for which Xi,j 0 (as constructed in the proof of Proposition 6)
is nonempty; if no such j 0 exists, then the empty set is a tell-tale; otherwise, search for the
first j such that Xi,j , a tell-tale for L w.r.t. L, is defined. Thus, on any input σ, a learnerequipped with an oracle for K may test whether or not a potential hypothesis Ui contains
content(σ) as well as whether a tell-tale for Ui found earlier is contained in content(σ),
thereby ensuring that it is conservative.
Consequently, we have the following result:
Theorem 10. Any 3-shot comparable 1–1 r.e. family is ConsvEx[K] learnable.
Next we show that Theorem 6 and Theorem 7 do not generalise to 3-shot verifiable classes
and 3-shot comparable classes.
Theorem 11. For indexed families 3-shot comparability or 3-shot verifiability do not imply
conservative learnability.
Proof. This can be seen as follows: For all e, s ∈ N, we define Le,0 := {e} ⊕ N, andfor s > 0 we set{e} ⊕ D , if there is a first step t ≤ s at which some σ ∈ N∗ is foundsuch that there is a D ⊆ N with content(σ) = {e} ⊕ D
Le,s :=and WMe,t (σ) ⊃ content(σ) ;{e} ⊕ N , otherwise.
Here, we assume without loss of generality that at any step, at most one σ is found in
the first clause above. We set L := {Le,s : e, s ∈ N} and note that L has a uniformly
recursive numbering. Furthermore, if Me were a behaviourally correct learner of L, then,since Me must learn {e} ⊕ N ∈ L, there must exist some σ ∈ N∗ and D ⊂ N with
content(σ) = {e} ⊕ D such that Me overgeneralises on input σ. Hence L does not have aconservative behaviourally correct learner.
On the other hand, the class L is 3-shot comparable. Given indices i and j, a 3-shot
comparator F simulates Wi and Wj , and it outputs ? until Wi and Wj each enumerates aneven element. If the first even element enumerated by Wi is different to that enumerated
by Wj , then F outputs “no”. Suppose the first even element enumerated by both Wi
and Wj is 2e. Then the comparator F outputs “yes” until it finds an s such that for somefinite set D ⊂ N, Le,s = {e} ⊕ D and exactly one of the sets Wi , Wj enumerates some
2y + 1 ∈/ {2x + 1 : x ∈ D}; it will then output “no” until Wi and Wj each enumerates
some odd number not belonging to {2x + 1 : x ∈ D}; F (i, j) will now output “yes”. Notethat if Wi , Wj ∈ L, then F (i, j) will change its value at most twice; moreover, F (i, j) will
converge to the correct value.
A similar proof as above also shows that L is 3-shot verifiable.

20

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

Theorem 12. There exists a 2-shot standardisable indexed family which is not conservatively
learnable.
Proof. For each e, let ye be the first y > 3 found, if any, in some standard search, such thatfor some σ with content(σ) = {e} ⊕ {x : x ≤ y} ⊕ ∅, WMe (σ) ⊃ {e} ⊕ {x : x ≤ 4y } ⊕ ∅.
Consider the class L consisting ofi. Le = {e} ⊕ N ⊕ ∅ ;ii. if ye is defined then, for ye < z < 4ye , the sets
• Xe,z , if C(z) ≥ ye
• Ye,z , if C(z) < ye
whereXe,z = {e} ⊕ {x : x ≤ ye } ∪ {z} ⊕ ∅, andYe,z = {e} ⊕ {x : x ≤ ye } ∪ {z} ⊕ {2z (2t + 1)}, where t is the time needed to find ye
and that C(z) < ye .
Note that L is an indexed family. Moreover, it is not conservatively learnable as if alearner Me conservatively learns Le , then using a locking sequence argument, ye is defined.
Furthermore, for some z, ye < z < 4ye , C(z) ≥ ye . Now, the learner cannot conservatively
learn Xe,z .
Next it is shown that L is 2-standardisable. Note that if We0 is an index for Xe,z , where ye
is defined, then ye ≤ C(z) ≤ log(e0 )+constant. Thus, for standardising it can be assumed,
without loss of generality, that ye ≤ e0 , as standardising for the e0 where e0 − log(e0 ) issmaller than the constant above can be done by patching.
Now, the standardiser on input e0 first searches for an e such that We0 contains 3e. Then,0• if We0 contains 3(4e ) + 3 + 1, then the standardiser outputs the canonical index for Le
and never changes its mind after that;• if We0 contains 3(2z (2t + 1)) + 2, for some z, t, then it outputs the canonical index
for Ye,z and never changes its mind after that;• if ye is defined and We0 = Xe,z for some z, then it outputs the canonical index for Xe,z .
It is easy to see that the above standardiser is a 2-shot standardiser and standardises L.
At this point it is only natural to ask what holds for 4-shot comparators. The answer isprovided by the following theorem, where U denotes a fixed universal Turing machine used
to define the Kolmogorov complexity.

On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference

21

Theorem 13. There is an indexed family L which is 4-shot comparable and 3-shot standardisable but not behaviourally correct learnable.
Proof. Let L = {L0 , L1 , L2 , . . . , } be a class of r.e. sets such that L0 = {2y : y ∈ N}; andfor all x ∈ N,({2y : y ∈ N ∧ y ≤ t} \ {2x}) ∪ {2t + 1} , if t is the first step at which
some p < log(x) is foundLx+1 =
such that U (p, ε) = x ;{2y : y ∈ N ∧ y 6= x} ,if no such p is found .
Note that L has a uniformly recursive numbering. Furthermore, one can define a 4-shot
comparator F for L as follows: First, as in Example 4, let f be a recursive function suchthat whenever We = {2y : y ∈ N ∧ y 6= x} for some x with C(x) ≥ log(x), x < f (e).
Given d, e ∈ N, simulate Wd and We . At every step, F performs the instructions in the case(among the four cases below) with the highest priority that applies; Case i has higher priority
than Case j iff i < j.
Case 1: One of the sets, say Wd , enumerates an odd number 2y + 1. Simulate Wd until alleven numbers but one (say 2x) below 2y + 1 appear in Wd . Simulate We until the firstof the following cases applies:
Case 1.1: Either 2x or some even number larger than 2y appears in We , or an odd
number different from 2y + 1 occurs in We . Output “no”.
Case 1.2: The set We enumerates all elements of {2z : 0 ≤ z ≤ y∧z 6= x}∪{2y+1}.
Output “yes”.
Case 2: All the even numbers below f (d) + f (e) have been enumerated into both Wd
and We . Output “yes”.
Case 3: All the even numbers below f (d) + f (e) have been enumerated into exactly oneof Wd and We . Output “no”.
Case 4: There is exactly one even number x1 < f (d) + f (e) that has not been enumerated
into Wd , and there is exactly one even number x2 < f (d) + f (e) that has not been
enumerated into We . If x1 = x2 , output “yes”. If x1 6= x2 , output “no”.
Now it is verified that F is indeed a 4-shot comparator for L. Suppose Wd , We ∈ L. Consider
the following case distinction:
Case i: At least one of Wd , We contains an odd number. Then Case 1 will almost always
apply, and either (a) both Wd and We are equal to {2z : 0 ≤ z ≤ y ∧z 6= x}∪{2y +1}
for some y, x ∈ N, so that F will output “yes” in the limit, or (ii) one of Wd , We is
equal to {2z : 0 ≤ z ≤ y ∧ z 6= x} ∪ {2y + 1} for some y, x ∈ N while the othercontains 2x or some odd number different from 2y + 1 or an even number larger than2y, so that F will output “no” in the limit.

22

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

Case ii: Wd = {2z : z ∈ N} \ {2x1 } and We = {2z : z ∈ N} \ {2x2 } for some x1 , x2 ∈ N.
Then Case 4 will almost always apply, and if x1 = x2 , then F will output “yes” in thelimit; if x1 6= x2 , then F will output “no” in the limit.
Case iii: Both sets Wd and We contain only even numbers, and at least one of Wd , We is
equal to {2z : z ∈ N}. If both Wd and We are equal to {2z : z ∈ N}, then Case 2 willalmost always apply, so that F will output “yes” in the limit. If exactly one of Wd
and We is equal to {2z : z ∈ N}, then Case 3 will almost always apply, so that F will
output “no” in the limit.
Furthermore, note that F (d, e) changes its value between Steps t1 and t2 (where t2 > t1 ) only
if there are distinct i, j with j < i such that F performs the instructions in Case i at Step t01
and then performs the instructions in Case j at Step t02 for some t01 , t02 with t1 ≤ t01 < t02 ≤ t2 ;in particular, if Case 1 applies at some step, then F (d, e) will not change its value at any
subsequent step. Thus F changes its value at most thrice on input (d, e), and it is therefore a
4-shot comparator for L.
A 3-shot standardiser G for L can be defined similarly. Given any index e, G outputs ?
until the first of the following cases applies:
Case a: The set We enumerates all even numbers but one (say 2x1 ) below f (e). Then G
keeps outputting a canonical index for {2z : z ∈ N ∧ z 6= x1 }. If We enumerates 2x1
at any later step, then G switches to outputting a canonical index for {2z : z ∈ N}. If
We enumerates an odd number at any step, then G follows the instructions in Case b.
Case b: The set We enumerates an odd number 2y + 1. Then G waits until We enumerates
all even numbers but one (say 2x2 ) below 2y + 1; it will then output a canonical index
for {2z : z ≤ y ∧ z 6= x2 } ∪ {2y + 1} in the limit.
That G is indeed a 3-shot standardiser for L can be verified using ideas very similar to thosein the earlier proof that F is a 4-shot comparator for L.
Moreover, L is not behaviourally correctly learnable because L0 does not have a finite
tell-tale (see Baliga et al. [3, Corollary 3]): for every set D of even numbers, there is somex > max(D) with C(x) ≥ log(x), so that D ⊂ Lx+1 ⊂ L0 .
We continue with further results concerning finite standardisation, finite verifiability, finite
learning, and explanatory learning, when the classes considered may not be recursively
enumerable. We formulate the following example in terms of function learning. Note thatfunction learning is just a special case of language learning, since learning functions is in
general equivalent to learning their graphs as sets from text.
Example 8. We define f0 (x) := 0 for all x ∈ N, and for n ≥ 1 we set fn (x) := 0 for
all x ∈ N \ {n} and fn (n) := 1. Furthermore, we use minϕ f to denote the least index isuch that ϕi = f . Next, consider the class F := {fn | n ∈ N, n ≤ minϕ fn }. Then F isfinitely standardisable but neither finitely learnable nor finitely verifiable. Note that F is not
an r.e. class.

On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference

23

Finite standardisability of F as well as that F is not finitely learnable has been shown in
Freivald and Wiehagen [12].
In order to see that F is not finitely verifiable let e ∈ N be an index for f0 , and let T bea text for f0 such that T = ((0, f0 (0)), (1, f0 (1)), (2, f0 (2)) . . .). Then, on input e and T , afinite verifier would have to eventually output “yes”, since otherwise it could not verify that T
is a text for the function f0 . Let this happen when the verifier has seen T [m]. Consequently,
for every n > m and a text T 0 in the same order (0, fn (0)), (1, fn (1)), (2, fn (2)) . . . for fn
it must, on input e and T 0 , also output “yes”, a contradiction to the fact that T 0 is not a text
for f0 .
Note that Examples 1, 2 and 8 show both that the collection of finitely learnable classes isincomparable to the collections of finitely standardisable classes and to the collection offinitely verifiable classes.
Next, we ask whether or not finite standardisability is of any help for explanatory learning.
This question deserves attention, since it deals with the problem of information presentation
versus the mode of convergence. The affirmative answer is given below.
In the following, for all e, s ∈ N, let We,s denote the subset of We enumerated in s steps.
Theorem 14. If a class L is finitely-standardisable then L is explanatorily learnable.
Proof. Assume that F is a finitely standardising function for L. Furthermore, we define thefollowing set: S := {e : e ∈ N, F (e) = e}.
Using the operator recursion theorem (see Case [6]), let g be a recursive function such
that

We0 ,
if F (g(e0 , e)) is undefined or not equal to e0 ;W 0 0 , if F (g(e0 , e)) = e0 in exactly t(e0 , e) steps
e ,t(e ,e)0
Wg(e ,e) =
but We0 ,t(e0 ,e) 6⊆ We ;



We ,
otherwise .
As in the definition of Wg(e0 ,e) , above let t(e0 , e) denote the time needed for F (g(e0 , e)) toconverge. Note that if e, e0 ∈ S, e 6= e0 , and F (g(e0 , e)) = e0 , then either the set We does
not contain We0 ,t(e0 ,e) or We is not in L (as F outputs two different values on the indices eand g(e0 , e) for it).
Assume that T is the input text for a language in L. Let e0 , e1 , . . . , be a 1–1 enumerationof S. On input T [n], the learner outputs ei for the least i ≤ n such that ei is not eliminated.
Here ei is eliminated if there exists a j 6= i, j ≤ n such that F (g(ej , ei )) = ej within n steps
and Wej ,t(ej ,ei ) ⊆ content(T [n]) — note that in this case ei is not the index for input language
as either Wej ,t(ej ,ei ) and thus content(T [n]) is not contained in Wei or F (ei ) 6= F (g(ej , ei ))but Wg(ej ,ei ) = Wei ; if no such i exists, then the output of the learner does not matter andcan be anything.
Assume Wer ∈ L, and T is a text for it. Then, eventually, all ei , i < r will be eliminated (that is not output by the learner above, on input T [n] for large enough n) as (i)24Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

F (g(er , ei )) = er (otherwise, Wg(er ,ei ) = Wer , but F (g(er , ei )) 6= F (er ), contradicting
the finite-standardisability of L by F ), and (ii) Wer ,t(er ,ei ) ⊆ Wer = content(T ). Furthermore, er is never eliminated as for all ei , i 6= r, F (g(ei , er )) 6= ei or Wei ,t(ei ,er ) 6⊆ Wer (asotherwise Wg(ei ,er ) = Wer , and therefore, F (g(ei , er )) = er 6= ei by standardisability).
We conclude that the above learner on T converges to er . Thus, the above learner Ex
learns L.
Theorem 15. There is a class of recursive functions that is finitely (2, 3)-standardisable but
not finitely learnable.
Proof. First note that a finitely (2, 3)-standardisable class via F1 , F2 , F3 has to be inclusionfree; if A, B are two r.e. sets in the class and A ⊂ B then one can define a uniformly recursive
sequence e0 , e1 , . . . of indices such that Wf (ek ) = A in the case that k ∈/ K and Wf (ek ) = B
in the case that k ∈ K; thus the halting problem K becomes reduced onto the standardisingtask and k ∈/ K iff at least two of the outputs of F1 (f (ek )), F2 (f (ek )), F3 (f (ek )) are in agiven finite set of indices of A (as given by the standardisers); this finite set depends on thestandardisers. So the complement of K would be recursively enumerable which is not thecase.
Furthermore, one can show that such a class can be properly (2, 3)-learnable (that is,some learner outputs at most 3 indices on the input text, at least two of which are correct)
without being finitely learnable. For this, consider the following class of all Ak , Bk where
Ak = Bk = {3k} in the case that k ∈/ K and Ak = {3k, 3k + 1} and Bk = {3k, 3k + 2} inthe case that k ∈ K. This is a well-known example for a (2, 3)-learnable class: The learnerconjectures first two indices, one for Ak and one for Bk while it abstains from outputting
the third index. In the case that it happens that two elements are observed, the sets Ak andBk must be different and the learner can see from the data which of these two sets applies.
Similarly for finite (2, 3)-standardisation: Given an index e, the standardiser first searches
for an k such that 3k ∈ We ; when this is found, F1 (e) outputs a fixed index of Ak and F2 (e)outputs a fixed index of Bk . After that, F3 (e) simulates We until either 3k + 1 or 3k + 2
appears in We ; depending on the corresponding case, F3 (e) is either F1 (e) or F2 (e).

5. Conclusions and Open Problems
We introduced learning models, where at least one input is an index, and the second input isa text or another index, resulting in verifiability and comparability, respectively. Hence theselearning models are modifications of standardisability, a learning model which has beenaround for quite some time. And we studied variations of these three models by restricting
the number of shots these models are allowed to make. Furthermore, we studied the learning
capabilities of these learning models and explanatory inference in dependence on the classes
to be learnt; i.e., we distinguished between arbitrary classes of r.e. languages, uniformly r.e.
classes of r.e. languages, 1–1 r.e. classes of r.e. languages, and indexed families.

On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference25

Table 1 at the end of the Introduction summarises many of the results obtained except
the ones for arbitrary classes of r.e. languages. As we see, comparators, standardisers, andverifiers are different with respect to their help for the inductive inference of the respectiveclasses. That is, verifiability always implies explanatory learning, but conservative learning
is out of reach in general. Only 2-shot verifiers can always be used to achieve conservative
learning.
Furthermore, 2-shot standardisability also implies explanatory learning but not conservative learning provided the target classes are indexed families or 1–1 r.e. classes. On the other
hand, for indexed families any 2-shot comparator and any 2-shot verifier can be exploited toobtain a conservative learner, but, in general, a 2-shot standardiser cannot.
In this context, it may be worth to look at a modification which was proposed by
Freivald [11] and called limit standardisability with a recursive estimate. In this modification
the number of shots is also bounded, but the bound depends on the index i received as
input; i.e., there is a recursive function b ∈ R such that, on input i, the standardiser is only
allowed to perform b(i) many shots. The usefulness of this modification was established by
Freivald [11], who used it to characterise the explanatory identification of minimal Gödelnumbers in the setting of function learning. Hence, generalising this approach to verifiers
and comparators may lead to some interesting results.
The investigations performed in the present paper also revealed some topological constraints for 2-comparability and finite standardisability, i.e., the respective classes must be
inclusion-free (cf. Proposition 4). This property was also used in Theorem 15 (among otherplaces). Also, in Example 8 another topological property was exploited. The class F considered there contains an accumulation point, i.e., f0 . This suggests to perform a deeper studyof topological properties that preserve comparability, verifiability, or standardisability (witha certain number of allowed shots). It may be a good starting point to look at Apsı̄tis [2],who used topological properties to obtain separations of explanatory learning with bounded
mind changes, where the bounds are given by constructive ordinals.

Acknowledgments
Sanjay Jain was supported in part by NUS grant C252-000-087-001. Furthermore, Ziyan
Gao, Sanjay Jain and Frank Stephan have been supported in part by the Singapore Ministry of
Education Academic Research Fund Tier 2 grant MOE2016-T2-1-019 / R146-000-234-112.
This research was performed partially while the fourth author was visiting the Instituteof Mathematical Sciences at the National University of Singapore in September 2017. His
visit was partially supported by the Institute. Thomas Zeugmann was also supported in partby the Japan Society for the Promotion of Science, and the Grand-in-Aid for Challenging
Exploratory Research No. 15K12022.

26

Ziyuan Gao, Sanjay Jain, Frank Stephan, and Thomas Zeugmann

References[1] Dana Angluin. Inductive inference of formal languages from positive data. Information
and Control, 45(2):117–135, 1980.
[2] Kalvis Apsı̄tis. Derived sets and inductive inference. In Algorithmic Learning Theory, 4th International Workshop on Analogical and Inductive Inference, AII ’94, 5thInternational Workshop on Algorithmic Learning Theory, ALT ’94, Reinhardsbrunn
Castle, Germany, October 1994, Proceedings, volume 872 of Lecture Notes in Artificial
Intelligence, pages 26–39. Springer-Verlag, 1994.
[3] Ganesh Baliga, John Case, and Sanjay Jain. The synthesis of language learners.
Information and Computation, 152(1):16–43, 1999.
[4] . M. Barzdin~ [Janis M. Bārzdiņs̆]. Dve teoremy o predel~nom sinteze
funkci$i [Two theorems on the limiting synthesis of functions]. In Janis M. Bārzdiņs̆,
editor, Theory of Algorithms and Programs I, volume 210 of Proceedings of the Latvian
State University, pages 82–88. Latvian State University, Riga, 1974. (in Russian).
[5] . M. Barzdin~ [Janis M. Bārzdiņs̆]. Induktivny$
i vyvod avtomatov, funkci$
i i programm [inductive inference of automata, functions and programs]. In
Proceedings of the International Congress of Mathematicians, Vancouver 1974, volume 2, pages 455–460, 1974. English version available in American MathematicalSociety Translations 1977, pp. 107–122.
[6] John Case. Periodicity in generations of automata. Mathematical Systems Theory,8(1):15–32, 1974.
[7] John Case. The power of vacillation in language learning. SIAM Journal on Computing,28(6):1941–1969, 1999.
[8] John Case and Christopher Lynes. Machine inductive inference and language identification. In Automata, Languages and Programming, 9th Colloquium, Proceedings,
volume 140, pages 107–115. Springer-Verlag, 1982.
[9] John Case and Carl Smith. Comparison of identification criteria for machine inductive
inference. Theoret. Comput. Sci., 25(2):193–220, 1983.
[10] Jerome Feldman. Some decidability results on grammatical inference and complexity.
Information and control, 20(3):244–262, 1972.
[11] R. V. Freivald. Minimal Gödel numbers and their identification in the limit. In Jiřı́
Bečvář, editor, Mathematical Foundations of Computer Science 1975, 4th Symposium,
Mariánské Lázně, September 1-5, 1975, volume 32 of Lecture Notes in Computer
Science, pages 219–225, Berlin, 1975. Springer-Verlag.
[12] R. V. Freivald and R. Wiehagen. Inductive inference with additional information.
Elektronische Informationsverarbeitung und Kybernetik, 15(4):179–185, 1979.

On the Help of Bounded Shot Verifiers, Comparers, and Standardisers in Inductive Inference27[13] Rūsiņš Freivalds, Efim B. Kinber, and Rolf Wiehagen. Connections between identifying
functionals, standardizing operations, and computable numberings. Zeitschrift fürmathematische Logik und Grundlagen der Mathematik, 30(9-11):145–164, 1984.
[14] Ziyuan Gao, Frank Stephan, and Sandra Zilles. Partial learning of recursively enumerable languages. Theoretical Computer Science, 620:15–32, 2016.
[15] E Mark Gold. Language identification in the limit. Information and control, 10(5):447–
474, 1967.
[16] Sanjay Jain, Daniel Osherson, James S. Royer, and Arun Sharma. Systems that
Learn: An Introduction to Learning Theory, second edition. MIT Press, Cambridge,
Massachusetts, 1999.
[17] Sanjay Jain and Arun Sharma. Characterizing language identification by standardizing
operations. Journal of Computer and System Sciences, 49(1):96–107, 1994.
[18] E. B. Kinber [Efim B. Kinber]. O sravnenii predel~nogo sinteza i
predel~no$i standartizacii nomerov obwerekursivnyh funkci$
i [Oncomparison of limit identification and standardization of general recursive functions].
In Janis M. Bārzdiņs̆, editor, Theory of Algorithms and Programs II, volume 233 ofProceedings of the Latvian State University, pages 45–56. Latvian State University,
Riga, 1975. (in Russian).
[19] Ming Li and Paul Vitányi. An Introduction to Kolmogorov Complexity and its Applications. Springer, third edition, 2008.
[20] Daniel N Osherson, Michael Stob, and Scott Weinstein. Systems that learn: An
introduction to learning theory for cognitive and computer scientists. The MIT Press,
1986.
[21] Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. MIT
Press, Cambridge, MA, USA, 1987.
[22] Raymond M. Smullyan. Theory of formal systems, volume 47 of Annals of Mathematics
Studies. Princeton University Press, Princeton, New Jersey, USA, 1961.
[23] Thomas Zeugmann, Steffen Lange, and Shyam Kapur. Characterizations of monotonic
and dual monotonic language learning. Information and Computation, 120(2):155–173,
1995.
[24] Thomas Zeugmann and Sandra Zilles. Learning recursive functions: A survey. Theoretical Computer Science, 397(1-3):4–56, 2008.