JMLR: Workshop and Conference Proceedings 1–25, 2018

Algorithmic Learning Theory 2018

On the Help of Bounded Shot Verifiers, Comparators andStandardisers for Learnability in Inductive Inference
Ziyuan Gao

MATGAOZ @ NUS . EDU . SG

Department of Mathematics
National University of Singapore
Singapore 119076, Republic of Singapore

Sanjay JainSANJAY @ COMP. NUS . EDU . SG

School of Computing
National University of Singapore
Singapore 117417, Republic of Singapore

Frank Stephan

FSTEPHAN @ COMP. NUS . EDU . SG

Department of Mathematics
National University of Singapore
Singapore 119076, Republic of Singapore

Thomas Zeugmann

THOMAS @ IST. HOKUDAI . AC . JP

Division of Computer Science
Hokkaido University
N-14, W-9, Sapporo 060-0814, Japan

Editor: Mehryar Mohri and Karthik Sridharan

Abstract
The present paper deals with the inductive inference of recursively enumerable languages frompositive 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 astandardiser 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 every index jfor L to e. Additionally, the common learning models of explanatory learning, conservative
explanatory learning, and behaviourally correct learning are considered. For almost all learningmodels 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 help of an oracle is taken into consideration.
The main goal of this 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, and recursively 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 is allowed, thenthere are differences, i.e., for indexed families, comparability or verifiability imply conservative
explanatory learning, but standardisability does not; still explanatory learning can be achieved.

c 2018 Z. Gao, S. Jain, F. Stephan & T. Zeugmann.

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

1. Introduction
The process of hypothesising a general rule from “eventually” complete positive data is called
inductive inference. Philosophy of science has studied inductive inference during the last centuries.
Some of the principles developed are very much alive in algorithmic learning theory. Computerscientists widely use their insight into the theory of computability to obtain a better and deeper
understanding of processes performing inductive generalisations.
The present paper mainly deals with formal language learning, a field in which many interestingand sometimes surprising results have been elaborated within the last decades (see Jain et al., 1999;
Zeugmann and Zilles, 2008, and the references therein). Inductive inference of formal languages
may be characterised as the study of systems 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 isformalised syntactically then we obtain explanatory learning (see Case and Smith, 1983), which isalso called learning in the limit (see Gold, 1967). Replacing syntactically by semantically results inbehaviourally correct learning (see Feldman, 1972; Bārzdiņs̆, 1974, 1977; Case and Smith, 1983;
Case, 1999). A further special case is finite learning, where the learner outputs essentially just
one hypothesis which has to be a correct one. In the learning models described so far, evidence isprovided by successively growing initial segments of any infinite sequence of strings that eventuallycontains all strings of the target language L and none of the strings outside of L (such a sequence iscalled 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 alladmissible hypotheses is called the hypothesis space. In the present paper the hypothesis space isany fixed acceptable 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 the learnability of classes L of languages; i.e., we
ask whether or not there is one learner that can 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 the evidence is
any index e and a text of the target language L, and the learner has to verify whether or not theindex 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, westudy standardisability in the sense that evidence is provided by any index j of a target language Lfrom the class L. Then for every L ∈ L there has to exist an index e such that We = L and thestandardiser has to map every index j of L to e. This mapping may be performed in the limit or justby outputting a single guess which then must be e (called finite standardisability). Standardisability
has been considered previously in the literature (see, e.g., Kinber, 1975; Freivald and Wiehagen,1979; Freivalds et al., 1984; Jain and Sharma, 1994).
For almost all the learning models described above it is also meaningful to take a closer lookat the number of times a learner changes its mind. For the technical details we refer the reader toDefinition 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 of recursively
enumerable languages. For example, we are interested in learning whether or not a verifiable

2

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

class is also explanatorily learnable, and if it is, whether or not the number of mind changes ispreserved. Table 1 provides a summary of the results obtained, where the last three columns givethe 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 two columns. (Here n-shot means thatthe comparator/standardiser/verifier makes at most (n − 1)-mind changes — that is it gets n-shots atgetting the correct answer.) In the table, Ex[K] denotes Ex-learning using oracle K, and a ? besidea criterion denotes an open problem at this point. An entry Not I denotes that the corresponding
comparator/standardizer/verifier notion does not imply I-learnability.
Notation

Shots

IndexedFin(Thm 11)

One-One R.E.
Fin
(Thm 11)2

ConsvEx(Thm 21)

Ex (Thm 17),
ConsvEx?

3

Ex (Thm 28),
Not ConsvEx (Thm 32)

1

Comparator

4 and More
1
Standardiser

2
3 and More
1

Verifier2
3 and MoreNot BC(Thm 33)
Fin(Cor 12)
Ex (Thm 15),
Not ConsvEx (Thm 18)
Not BC(Thm 33)
Fin(Prop 10)
ConsvEx(Thm 20)
Ex (Prop 24),
Not ConsvEx(Thm 32)

ConsvEx[K](Thm 29),
Not Ex(Thm 26), BC?
Not BC(Thm 33)
Fin(Cor 12)
Ex (Thm 15),
Not ConsvEx(Thm 18)
Not BC(Thm 33)
Fin(Prop 10)
ConsvEx(Thm 20)
Ex (Prop 24),
Not ConsvEx(Thm 32)

R.E.
Fin(Thm 11)
Not Ex(Thm 19),
ConsvEx[K](Thm 22)
Not BC(Prop 30)
Not BC(Thm 33)
Fin(Cor 12)
Not BC(Prop 30)
Not BC(Thm 33)
Fin(Prop 10)
ConsvEx(Thm 20)
Ex (Prop 24),
Not ConsvEx(Thm 32)

Table 1: Summary of main results

2. Notation
The notation and terminology from recursion theory adopted in this paper follows Rogers (1987).
For background on inductive inference we refer the reader to Jain et al. (1999) and Zeugmann and
Zilles (2008).
We use N = {0, 1, 2, . . .} to denote the set of all natural numbers. The set of all partial recursivefunctions and of all recursive functions of one, and two arguments over N is denoted by P, P 2 , R,
3

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

and R2 , 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 of all partial recursive functions andlet W0 , W1 , W2 , . . . be a acceptable 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 definedthen 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 thenwe write ϕe,s (x) ↓= ϕe(x) ; otherwise ϕe,s (x) ↑. For all e, s ∈ N the set We,s is defined as the domainof ϕe,s . The symbol K denotes the diagonal halting problem, i.e., K = {e : e ∈ N, ϕe (e)↓}. We
use C(x) to denote the plain Kolmogorov complexity of x (see Li and Vitányi, 2008, chap. 2).
Given any set S, we use S ∗ to denote the set of all finite sequences of elements from S. By
D0 , D1 , D2 , . . . we denote any fixed canonical indexing of all finite sets of natural numbers. We
recall that Cantor’s pairing function h · , · i : N × N → N is given by hx, yi = 12 (x + y)(x + y + 1) + y
for all x, y ∈ N. 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 of learnability.
In the following we always assume that # ∈/ N. Furthermore, for σ ∈ (N ∪ {#})∗ and n ∈ N wewrite σ(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 theempty 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 ofconfusion, this is occasionally denoted by στ .

3. Learnability, Standardisability, Comparability and Verifiability
Let L be a class of r.e. languages. Throughout this paper, the mode of data presentation is that ofa text. A text is any infinite sequence of natural numbers and the # symbol, where the symbol #indicates a pause in the data presentation. More formally, a text TL for a language L ∈ L is any total
mapping TL : N → N ∪ {#} such that L = range(TL ) \ {#}. We use content(T ) to denote theset range(T ) \ {#}, i.e., the content of a text T contains only the natural numbers appearing in T .
Furthermore, for every n ∈ N we use T [n] to denote the finite 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 σ.
3.1. Learning Criteria
The main learning criteria studied in this paper are explanatory learning (also called learning in thelimit) introduced by Gold (1967) and behaviourally correct learning, which goes back to Feldman(1972), who called it matching in the limit. The name behaviourally correct learning was coined byCase and Smith (1983). It was also studied by Bārzdiņs̆ (1974, 1977) and Case and Lynes (1982).
Furthermore, we shall also consider finite learning (see Gold, 1967). In the following 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.

4

V ERIFIERS , C OMPARATORS AND S TANDARDISERS(1) An IIM M explanatorily (Ex) learns L if, for every L in L and each text TL for L, there is anumber 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 anumber n for which L = WM (TL [n]) and for every m < n, M (TL [m]) = ? and for every 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 areat 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.
We shall also consider the learning constraint of conservativeness (see Angluin, 1980). 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 a different guess jn+k 6= jn 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 . By ConsvEx and ConsvBC wedenote the learning criteria obtained by combining conservativeness with Ex learnability and BC
learnability, respectively.
In some cases we consider learners using oracles. In this case the learning criterion I, when thelearners are allowed use of oracle A, is denoted by I[A]. For every learning criterion I considered in
the present paper, there exists a recursive enumeration M0 , M1 , . . . of the learning machines suchthat if a class is I-learnable, then some Mi I-learns the class. We fix one such enumeration oflearning machines. A class L is said to be uniformly r.e. (or just r.e.) if there is an r.e. set S ⊆ N suchthat 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 is said to be uniformly
recursive or an indexed family 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 .
Angluin (1980) 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 fora language L ∈ L if S ⊆ L, 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.
Every behaviourally correctly learnable class of languages satisfies the tell-tale property (see Angluin,
1980; Baliga et al., 1999). A characteristic sample (Lange and Zeugmann, 1992; Mukouchi, 1992)
of a language L (with respect to a class L) is a finite subset S of L such that for all L0 ∈ L, L 6= L0
implies S 6⊆ L0 . 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.
3.2. Criteria for Verifiability, Comparability and Standardisability
In this paper, we consider a learning scenario in which the learner may not be required to output acorrect 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 are5

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

indices for the same set. We shall also study classes of r.e. languages that can be finitely standardisedin 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 e with We = L for which f outputs e when fed with any r.e. index for L.
Mutatis mutandis, replacing the function f by a limiting recursive function yields standardisation(in the limit) of languages (see (ii) below). Finite standardisation was introduced by Freivald andWiehagen (1979), while standardisation goes back to Kinber (1975). Their motivation was to study
whether a given index of the object to be learnt is more useful than the graph of a target function or atext of the target language. It was further investigated by Freivalds et al. (1984) for function learning,and by Jain and Sharma (1994) 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 that for
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}, and F (i, j, k) 6=
F (i, j, k + 1).
Intuitively, this means that F “changes its value (or mind)” 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-recursive function
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).
Intuitively, this means that F “changes its value” at most n times.
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 text T forsome perhaps different language in L, M converges to “yes” in the case that e is an index forthe language of the text and “no” if that is not the case; M is called a verifier for L. One cansimilarly define finite verifiability and (n + 1)-shot verifiability.

4. Results
In this section all results are presented. They are grouped with respect to the number of shots a
verifier, comparator, and standardiser is allowed to make. We then compare the power of thesemodels to the more standard models of learnability.
1. In order to minimise notation, we shall often omit the third argument in the definition of F and simply write “Fchanges its value at most n times”, where F is a given (n + 1)-shot comparator for a class; the meaning of thisstatement will be clear from the context. A similar remark applies to any (n + 1)-shot standardiser.

6

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

4.1. Comparison of Learnability With 1-Shot Verifiability, 1-Shot Comparability and 1-Shot
Standardisability
We start this section with some 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 thepower of verifiers is incomparable to the power of explanatory learners.
Example 4 The class K consisting of K and all singleton languages {x} with x ∈/ K is finitely
learnable but not finitely verifiable.
Note that the second part of the proof in Example 4 (cf. Section 5.1) also shows that K is a uniformly
r.e. class. We continue with further properties of the r.e. class K, which, as we have shown in
Example 4, is finitely learnable but not finitely verifiable.
Example 5 The uniformly r.e. class K is neither finitely comparable nor finitely standardisable.
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 classesof recursive functions, where every finitely learnable function class is also finitely standardisable(see Freivald and Wiehagen, 1979).
Example 6 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 .
To choose such an Le let Xi = {he, xi : x ∈ Wi }. Now {Xi : i ∈ N} is not behaviourally correctly
learnable by learner Me as otherwise the class of all r.e. sets would be behaviourally correctly
learnable, contradicting Case and Lynes (1982). Thus, one can choose Le to be some nonempty Xi
which is not behaviourally correctly learnable by Me .
The class L is then verifiable by an algorithm which on input of an index d and a text T
enumerates the set Wd and tracks the text until a member (i, s) is enumerated into Wd and a nonpause datum (j, t) is found in the text. Then the index d is for the language of T iff i = j, as theverifier needs only to work on members of the class. However, by choice, L is not behaviourally
correctly learnable.
Example 7 Assume that each language in L contains exactly one even element and that no two
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 notconverge to the right index on the text for the language in L with the even element 2e and similarly one
can also fool the standardiser and thus this class L can be chosen such that it is neither behaviourally
correctly learnable nor standardisable in the limit.
In order to establish a connection between learnability and finite standardisability as well as finite
comparability, we first make a general observation. 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 indicessuch that both Wd and We are in L. Then the algorithm runs two instances of the standardiser inparallel on the two inputs d and e, respectively, and waits until each of them has produced an output.
From then on, if the current outputs of the two instances are equal, then the algorithm outputs “yes”,
7

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

and if the two outputs are different, then it outputs “no”. Note that the two instances must produce atleast one output each, since both Wd and We are in L. Once this is done, every mind change of thecomparator requires that at least one of the standardisers makes another shot and so one can boundthe number of shots of the comparator by 1 + 2 · (n − 1) = 2n − 1. Hence, we have the following
proposition:
Proposition 8 Every n-shot standardisable class is (2n − 1)-shot comparable.
We next show that 2-shot comparable classes and finitely standardisable classes have a rather
restrictive structure.
Proposition 9 Any class which is 2-shot comparable must be inclusion-free. Thus, any class 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 , thenusing the double recursion theorem (see Smullyan, 1961), one can construct two grammars i and jsuch 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 the comparator is wrong on input (i, j).
The next three results show that with respect to uniformly r.e. classes, finite verifiability, finite
standardisability and finite comparability are so restrictive that each of them already implies finite
learnability.
Proposition 10 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 e0 , e1 , e2 , . . . of indices, then 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”.
Theorem 11 Every uniformly r.e. and finitely comparable class L is finitely learnable.
The next corollary follows from Proposition 8 and Theorem 11.
Corollary 12 Every uniformly r.e. and finitely standardisable class L is finitely learnable.
Remark A slight modification of the proof of Theorem 11 (cf. Section 5.3) gives that whenevera uniformly r.e. class L is finitely comparable then L is also finitely standardisable and finitely
verifiable: The verifier just checks whether on input of 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”; the standardiser
outputs for an index d the first index ek in the given recursive enumeration, where F (d, ek ) has thevalue “yes”.
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 that function learning is just a
special case of language learning, since learning functions is in general equivalent to learning theirgraphs as sets from text.
8

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

Example 13 This example is for function learning, for ease of notation. The example can beeasily modified for language learning by considering graphs of functions rather than the functions
themselves. 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 i such that ϕi = f . Next,
consider the class F := {fn | n ∈ N, n ≤ minϕ fn }. Then F is finitely standardisable but neither
finitely learnable nor finitely verifiable. Note that F is not an r.e. class.
Finite standardisability of F as well as that F is not finitely learnable has been shown by Freivald
and Wiehagen (1979).
In order to see that F is not finitely verifiable let e ∈ N be an index for f0 , and let T be a text
for f0 such that T = ((0, f0 (0)), (1, f0 (1)), (2, f0 (2)) . . .). Then, on input e and T , a finite verifier
would have to eventually output “yes”, since otherwise it could not verify that T is a text for thefunction f0 . Let this happen when the verifier has seen T [m]. Consequently, for every n > m and atext 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 .
Examples 4, 5, 6 and 13 show both that the collection of finitely learnable classes is incomparable tothe collections of finitely standardisable classes and to the collection of finitely verifiable classes.
Next, we ask whether or not finite standardisability is of any help for explanatory learning, when
considering possibly non r.e. classes. This question deserves attention, since it deals with the problem
of information presentation versus the mode of convergence. The affirmative answer is given below.
Theorem 14 If a class L is finitely-standardisable then L is explanatorily learnable.
4.2. Comparing Learnability With 2-Shot Verifiability, 2-Shot Comparability and 2-Shot
Standardisability
We begin by showing that 2-shot standardisability of one-one r.e. classes implies explanatory learnability.
Theorem 15 If a class has a 2-shot standardiser and has a one-one r.e. numbering, then it isexplanatorily learnable.
Example 16 Consider the class of graphs of the functions with only finitely many non-zero values.
This class is 2-shot comparable and 2-shot verifiable and has a one-one enumeration. This holds
as a comparator, on input i and j, can start with “yes”, and then change its mind to “no” whena convergent error is found, that is, there exist x, y, z with y 6= z such that (x, y) ∈ Wi and(x, z) ∈ Wj . Similarly, a 2-shot verifier can be constructed. Furthermore, the class is clearly
one-one enumerable.
However, this class cannot be learnt by any confident learner even if it uses an oracle as thegraph of any finite function has an extension in the class. Thus there is no upper bound on the numberof shots of the learner.
Here a confident learner (see Osherson et al., 1986) 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 15) shows that any 2-shot comparable r.e.
class with a one-one numbering is explanatorily learnable.
9

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

Theorem 17 If a class L has a 2-shot comparator and a one-one r.e. numbering, then L is explanatorily learnable.
Recall that a conservative learner revises its conjecture only if the content of the present text
segment is not contained in the learner’s original conjecture. Intuitively speaking, a conservative
learner performs exclusively justified mind changes. In particular, a conservative learner can neverovergeneralise; i.e., it can never guess a proper superset of the target language (see, e.g., Angluin,
1980; Zeugmann et al., 1995; Jain et al., 1999).
Theorem 18 There exists a 2-shot standardisable indexed family which is not conservatively
learnable.
Although 1-shot comparable uniformly r.e. classes are always finitely learnable (cf. Theorem 11), we
next show that 2-shot comparable r.e. classes may not be learnable in the limit (cf. Theorem 19).
Theorem 19 There is an r.e. 2-shot comparable class which is not explanatorily learnable.
Theorem 20 If a uniformly r.e. class L is 2-shot verifiable, then it is conservative explanatorily
learnable.
As any class which is 2-shot comparable is inclusion-free (cf. Proposition 9), it is easy to show thenext result.
Theorem 21 Every indexed family which is 2-shot comparable is conservative explanatorily 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 22 Every uniformly r.e. class L which is 2-shot comparable is ConsvEx[K]-learnable.
4.3. Comparison of Learnability With 3 Or More Shot Verifiability, 3 Or More Shot
Comparability and 3 Or More Shot Standardisability
In this section, we compare learnability with verifiability, comparability and standardisability whenmore than 2-shots are allowed. We begin with a simple example to show that the power of comparability increases with the number of shots allowed.
Example 23 For each 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.
The following result is due to the learning algorithm, which for a recursive list of indices e0 , e1 , . . .
of a class converges to the first index ek where the verifier is, on the text T , converging to “yes” whilethe verifier converges, for all previous indices e0 , . . . , ek−1 , to “no”.
Proposition 24 If an r.e. class is verifiable in the limit then it is also explanatorily learnable.

10

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

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 to extend Theorem 19(albeit in a weaker form) to 1–1 r.e. families.
Lemma 25 Assume L = {Wf (i) : i ∈ N} is an r.e. class of infinite languages, each of which iscontained in {h1, xi : x ∈ N}, where f ∈ R. Suppose that L is n-shot comparable. Then there isa 1–1 r.e. class L0 of infinite languages such that L ⊆ L0 and L0 is (n + 1)-shot comparable.
We now deduce the following theorem from Lemma 25 and Theorem 19:
Theorem 26 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 19; 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 contained in{h1, zi : z ∈ N}. Note that L, like the uniformly r.e. class in the proof of Theorem 19, is not
explanatorily learnable. Lemma 25 then gives a 1–1 r.e. class L0 such that L0 ⊇ L, L0 is 3-shot
comparable and L0 is not explanatorily learnable.
We have seen that for indexed families, 1-shot comparability implies finite learnability (Theorem 11)
while 2-shot comparability implies conservatively explanatory learnability (Theorem 21). The next
theorem completes this fairly neat hierarchy of learnability notions implied by n-shot comparability
for indexed families: 3-shot comparability, while insufficient for guaranteeing conservative learnability (see Theorem 32), 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 27 Assume L = {U0 , U1 , . . .} is a 1–1 r.e. class with Ui 6= Uj for i, j with i 6= j.
Suppose L is 3-shot comparable. Then one can effectively (in i) enumerate tell-tale sets for Ui withrespect to L.
The following theorem now follows from the characterisation of explanatory learnability using
tell-tale sets by Angluin (1980) (and the fact that every indexed family containing infinitely many
distinct sets has a 1–1 r.e. numbering).
Theorem 28 Any 3-shot comparable indexed family is explanatorily learnable.
When given an oracle for K, a 1–1 r.e. family behaves like an indexed family for the purposes ofthe earlier proof of Proposition 27. Furthermore, using an oracle for K and an analogue of theconstruction of Wg(e,d) , Wh(e,d) in Proposition 27, one can determine for each member L of a 1–1
r.e. family L = {U0 , U1 , U2 , . . .} a finite tell-tale set for L w.r.t. L: first, test whether or not there
exists a j 0 for which Xi,j 0 (as constructed in the proof of Proposition 27) 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 learner equipped 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:
11

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

Theorem 29 Any 3-shot comparable 1–1 r.e. family is ConsvEx[K] learnable.
In order to show further results we need the following:
Proposition 30 The r.e. class L consisting of N and all sets N \ {x} with C(x) ≥ log(x) has thefollowing 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.
Proposition 31 If a class is n-shot learnable then it has a 2n-shot comparator.
Next we show that Theorem 20 and Theorem 21 do not generalise to 3-shot verification/comparable
classes.
Theorem 32 For indexed families 3-shot comparability or 3-shot verifiability do not imply conservative learnability.
At this point it is only natural to ask what holds for 4-shot comparators. The answer is provided
by the following theorem, where U denotes a fixed universal Turing machine used to define theKolmogorov complexity.
Theorem 33 There is an indexed family L which is 4-shot comparable and 3-shot standardisable
but not behaviourally correct learnable.
Consequently, we have shown all results presented at the end of the Introduction in Table 1.

Acknowledgments
Sanjay Jain was supported in part by NUS grant C252-000-087-001. Furthermore, Ziyuan 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 Institute of Mathematical Sciences at
the National University of Singapore in September 2017. His visit was partially supported by theInstitute. Thomas Zeugmann was also supported in part by the Japan Society for the Promotion of
Science, and the Grand-in-Aid for Challenging Exploratory Research No. 15K12022.
We thank the anonymous referees of the conference for several useful comments.

12

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

References
Dana Angluin. Inductive inference of formal languages from positive data. Information and Control,
45(2):117–135, 1980.
Ganesh Baliga, John Case, and Sanjay Jain. The synthesis of language learners. Information andComputation, 152(1):16–43, 1999.
Janis M. Bārzdiņs̆. 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).
Janis M. Bārzdiņs̆. Inductive inference of automata, functions and programs. In American Mathematical Society Translations, pages 107–122, 1977. Appeared originally in the Proc. of the 20-th
International Congress of Mathematicians 1974, Volume 2, pp. 455–460, (in Russian).
John Case. Periodicity in generations of automata. Mathematical Systems Theory, 8(1):15–32, 1974.
John Case. The power of vacillation in language learning. SIAM Journal on Computing, 28(6):1941–1969, 1999.
John Case and Christopher Lynes. Machine inductive inference and language identification. In
Mogens Nielsen and Erik Meineche Schmidt, editors, Automata, Languages and Programming,
Ninth Colloquium, Aarhus, Denmark, July 12-16, 1982, Proceedings, volume 140 of Lecture Notes
in Computer Science, pages 107–115. Springer-Verlag, 1982.
John Case and Carl Smith. Comparison of identification criteria for machine inductive inference.
Theoretical Computer Science, 25(2):193–220, 1983.
Jerome Feldman. Some decidability results on grammatical inference and complexity. Information
and Control, 20(3):244–262, 1972.
R. V. Freivald and R. Wiehagen. Inductive inference with additional information. Elektronische
Informationsverarbeitung und Kybernetik, 15(4):179–185, 1979.
Rūsiņš Freivalds, Efim B. Kinber, and Rolf Wiehagen. Connections between identifying functionals,
standardizing operations, and computable numberings. Zeitschrift für mathematische Logik undGrundlagen der Mathematik, 30(9-11):145–164, 1984.
Ziyuan Gao, Frank Stephan, and Sandra Zilles. Partial learning of recursively enumerable languages.
Theoretical Computer Science, 620:15–32, 2016.
E. Mark Gold. Language identification in the limit. Information and Control, 10(5):447–474, 1967.
Sanjay Jain and Arun Sharma. Characterizing language identification by standardizing operations.
Journal of Computer and System Sciences, 49(1):96–107, 1994.
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.

13

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

Efim B. Kinber. On comparison of limit identification and standardization of general recursivefunctions. 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).
Steffen Lange and Thomas Zeugmann. Types of monotonic language learning and their characterization. In David Haussler, editor, Proceedings of the Fifth Annual ACM Workshop on Computational
Learning Theory, July 27-29, 1992, Pittsburgh, Pennsylvania, pages 377–390, New York, NY,
1992. ACM Press.
Ming Li and Paul Vitányi. An Introduction to Kolmogorov Complexity and its Applications. Springer,
third edition, 2008.
Yasuhito Mukouchi. Characterization of finite identification. In K.P. Jantke, editor, Analogical andInductive Inference, International Workshop AII ’92, Dagstuhl Castle, Germany, October 1992,
Proceedings, volume 642 of Lecture Notes in Artificial Intelligence, pages 260–267, 1992.
Daniel N. Osherson, Michael Stob, and Scott Weinstein. Systems That Learn: An Introduction
to Learning Theory for Cognitive and Computer Scientists. The MIT Press, Cambridge, Massachusetts, 1986.
Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. The MIT Press,
Cambridge, Massachusetts, 1987.
Raymond M. Smullyan. Theory of Formal Systems, volume 47 of Annals of Mathematics Studies.
Princeton University Press, Princeton, New Jersey, USA, 1961.
Thomas Zeugmann and Sandra Zilles. Learning recursive functions: A survey. Theoretical Computer
Science, 397(1-3):4–56, 2008.
Thomas Zeugmann, Steffen Lange, and Shyam Kapur. Characterizations of monotonic and dual
monotonic language learning. Information and Computation, 120(2):155–173, 1995.

14

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

5. Appendix
This appendix contains the proofs not presented in the main part.
5.1. Proof of Example 4
Proof A finite verification algorithm on an index e for K and a text x, x, x, x, . . . would have toeventually output “no” iff x ∈/ K and that would, combined with the enumeration procedure of K,
lead to a decision procedure of K.
Let ψ(x, y) = 0, if y = x; ψ(x, y) = ϕx (x) ∗ ϕy (y), otherwise. Now, if x ∈/ K, then ψ(x, y)
diverges for all y 6= x, and thus domain(ψ(x, · )) = {x}. If x ∈ K, then for all y 6= x, ψ(x, y)converges iff y ∈ K, and thus domain(ψ(x, · )) = {x} ∪ K = K.
Now, the finite learner outputs the canonical index of domain of ψ(x, · ) in the acceptable
numbering W0 , W1 , W2 , . . . on input of any text T , if the first non-# symbol in the text T is x (thatis, for some i, T (i) = x, and T (i0 ) = # for all i0 < i). It is easy to verify that the above learner
finitely learns the class K.

5.2. Proof of Example 5
Proof The proof is in both cases indirect. Suppose the converse, and let k ∈ N be any fixed index
of K, i.e., Wk = K. Then one can design an algorithm deciding K. This algorithm uses thenumbering ψ constructed in the second part of the proof of Example 4. Since the numbering of thesets W0 , W1 , W2 , . . . is acceptable, there is a recursive function c ∈ R such that ψx = ϕc(x) for
all x ∈ N. Hence 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. Note that byconstruction, Wk , Wc(x) ∈ K for all x ∈ N, and thus the finite comparator must be defined on allthese inputs. Also, it must return “yes” iff Wc(x) = K and “no” otherwise; a contradiction to theundecidability of the set K.
For the finite standardiser the algorithm works mutatis mutandis. First, we run it on input k tofind out to which index k is finitely standardised, say to s. In order to decide K one executes thefinite standardiser on input c(x) for any given x ∈ N. If it returns s, then x ∈ K and otherwisex∈/ K.

5.3. Proof of Theorem 11
Proof Suppose L is a finitely comparable class as witnessed by comparator F . First, by Proposition 9,
the class L must be inclusion-free.
Second if L is a uniformly r.e. class with an r.e. list e0 , e1 , e2 , . . . of indices covering the classand if L is inclusion-free and finitely comparable, then one constructs for each k a set Wh(k) whichis 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) denotethe 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) .
15

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

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 for the same set in theclass 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; when F (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 Dh0 (k) ,although there might be several indices for Wek in the r.e. enumeration e0 , e1 , . . . of the indices.
From the above it is easy to see that the learning algorithm is correct.

5.4. Proof of Theorem 14
Proof Assume that F is a finitely standardising function for L, and let S = {e : e ∈ N, F (e) = e}.
Using the operator recursion theorem (see Case, 1974), 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)Wg(e0 ,e) =
but We0 ,t(e0 ,e) 6⊆ We ;



W ,
otherwise .
e
As in the definition of Wg(e0 ,e) , above let t(e0 , e) denote the time needed for F (g(e0 , e)) to converge.
Note that if e, e0 ∈ S, e 6= e0 , and F (g(e0 , e)) = e0 , then either We does not contain We0 ,t(e0 ,e) or We
is not in L (as F outputs two different values on the indices e and 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 and can beanything.
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) F (g(er , ei )) = er(otherwise, Wg(er ,ei ) = Wer , but F (g(er , ei )) 6= F (er ), contradicting the finite-standardisabilityof 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 (as otherwise Wg(ei ,er ) = Wer , andtherefore, F (g(ei , er )) = er 6= ei by standardisability).
It follows that the above learner on T converges to er . Thus, the above learner Ex-learns L.
5.5. Proof of Theorem 15
Proof Suppose F is a 2-shot standardiser for L = {Wh(0) , Wh(1) , . . .}, where h is a recursivefunction such that Wh(i) 6= Wh(j) for i, j with i 6= j.
16

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

Below, we shall have that grammars h(j) would be either in group 1 or group 2. They are ingroup 1, if F (h(j)) outputs at most one distinct grammar, and in group 2, if F (h(j)) outputs two
distinct grammars. Let F 1 (h(j)) denote the first and F 2 (h(j)) denote the second grammar (if any)
output by F on h(j).
Algorithm 1: The construction of Wg1 (i,j) and Wg2 (i,j) , for i, j with i 6= j,along with the definitions of S1,i,j , R1,i,j , S2,i,j , R2,i,ji. Wg1 (i,j) starts enumerating Wh(i) until it observes that the current values of F (g1 (i, j)) andof F (h(i)) are the same and not in {F 1 (h(j)), ?}.
Then, suppose that Wg1 (i,j) enumerated up to now is S1,i,j .
For defining g2 , correspondingly, we use F 2 (h(j)) and S2,i,j .
ii. Wait until Wh(j) contains S1,i,j .
iii. Enumerate 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 a 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 defining g2 , correspondingly, we use F 2 (h(j)), S2,i,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 it switches toenumerating Wh(k) . Similarly, Wg2 (i,j) searches for a k 6= j such that Wh(k) contains R2,i,j ,and then it switches to enumerating Wh(k) .
Note that the 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 recursive functions defined using the operator recursion
theorem (see Case, 1974) such that Wg1 (i,j) and Wg2 (i,j) are as in Algorithm 1. Note that g1 (i, j)
and g2 (i, j) (for i, j with i 6= j) are similar, except that they work 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. Intuitively, g1 (i, j) and g2 (i, j) simulate F and along the way define
sets S1,i,j , R1,i,j , S2,i,j , R2,i,j . These are the sets which the learner looks for in the input language to
output its conjectures. It will be argued below that this allows for explanatory learning.
A grammar h(j) starts in group 1 and then later may move to group 2. Within each group, 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 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= j suchthat 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.

17

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

The learner outputs the least grammar which is not in cancelled list (irrespective of which groupit 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 , incase F (h(i)) outputs two grammars) would get defined, and thus h(i) would go to cancelled list ofthat 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, (that is S1,i,jor 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 wasin the input text and thus in Wh(j) .
Thus, eventually h(j) is the grammar which is output by the learner.

5.6. Proof of Theorem 17
Proof We follow the notation in the proof of Theorem 15. Let {Wh(0) , Wh(1) , . . .} be a one-one
r.e. numbering of a class L and let F be a 2-shot comparator for L. Given any i, j ∈ N with i 6= j,define a recursive function g using the operator recursion theorem (see Case, 1974) so that Wg(i,j) is
as in Algorithm 2.
Algorithm 2: Construction of Wg(i,j) , for i, j with i 6= j, along with definition of Si,j and Ri,ji. Enumerate Wh(i) into Wg(i,j) until F (g(i, j), h(j)) = no. Let Si,j be the set of elements
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” andthen to “no” again.)

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” ifthere 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 contained in 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 atall). At each stage, M outputs the least index j such that j is not in a “cancelled” state (note that inparticular, j may not have been assigned any state up to the current stage).
Suppose that M is fed a text T for Wh(j) . As argued in the proof of Theorem 15, if the index j
is assigned the state “cancelled” at any stage, then it will eventually be assigned the state “correct”
and its state will henceforth never change. On the other hand, for every i < j, i will eventually be
18

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

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 in the 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.

5.7. Proof of Theorem 18
Proof For each e, let ye be the first y > 3 found, if any, in some standard search, such that forsome σ with content(σ) = {e} ⊕ {x : x ≤ y} ⊕ ∅, WMe (σ) ⊃ {e} ⊕ {x : x ≤ 4y } ⊕ ∅.
Consider the class L consisting of(i) Le = {e} ⊕ N ⊕ ∅ ;(ii) if ye is defined then, for z with ye < z < 4ye , the sets
• Xe,z , if C(z) ≥ ye ,• Ye,z , if C(z) < ye ,also belong to L, 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 andthat C(z) < ye .
Note that L is an indexed family. Moreover, it is not conservatively learnable as if a learner Me
conservatively learns Le , then using a locking sequence argument, ye is defined. Furthermore, forsome 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 isdefined, 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 ) is smaller than theconstant 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 andnever 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,zand 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.

19

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

5.8. Proof of Theorem 19
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 is monotonically non-decreasing in s) and converges to a limit value te ∈ N ∪ {∞};
(iii) if 2x + 1 ≤ te or C(x) < log(x) then Le,x contains besides 2e all odd numbers below te andall odd numbers 2y + 1 with C(y) < log(y); and(iv) if 2x + 1 > 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 = ∞, forall 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 is just 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, such that Me makes amind change somewhere on the way from Me (σs ) towards Me (σs (2x + 1)s ). If this x is foundthen one sets te,s+1 = s2 and σs+1 to be the extension of σs (2x + 1)s 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 2x + 1 > te andC(x) ≥ log(x), as on each of the texts σte (2x + 1)∞ for these Le,x the learner converges to thesame index Me (σte ). Thus the class does not have any learner which learns it in the limit. The classis 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 . As 2x + 1 > te ≥ s2 , log(te ) ≤ C(x) + 2 ≤ 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 eachindex e0 with We0 containing a number 2e, an upper bound f (e, e0 ) such that whenever te > f (e, e0 )then either We0 = Le,z or We0 is not in the class.
To see that the class is 2-shot comparable, consider any indices e0 , e00 of languages in the class; 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 and be unique. If these even numbers aredifferent, the comparator just guesses “no” and does not change 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 sets are 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 is either te,sor larger than f (e, e0 ) + f (e, e00 ), so that whenever te,s becomes updated to a larger number, this isimmediately above f (e, e0 ) + f (e, e00 ).

20

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

5.9. Proof of Theorem 20
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. (2016, Observation 35), it suffices to showthat L has an Ex learner N such that for every L ∈ L, N does not conjecture a superset of L on any
segment of any given text for L.
Given a text T , define a learner M as follows: on input T [n], M outputs f (i) for the least i ≤ nsuch that h outputs “yes” on (f (i), T [n]); if no such i exists, then M just outputs its prior conjecture(or an r.e. index for the empty set if n = 0). Suppose T is a text for some Wf (e) ∈ L. Let ` be theleast 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 classis also 2-shot comparable and thus inclusion-free by Proposition 9, M will never output a proper
superset on input of languages from the class.

5.10. Proof of Theorem 22
Proof By Proposition 9 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, the algorithm, which hasaccess to the K-oracle always takes the enumeration e0 , e1 , . . . of the indices of the class L andconjectures 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 eachwrong hypothesis en the learner will eventually see a counterexample, that is, an element outside Wenand drop it eventually.

5.11. Proof of Example 23
Proof A (2n + 1)-shot comparator F works as follows: on input (i, j), F outputs “yes” at the sthcomputational step if Wi,s = Wj,s and “no” otherwise. Then if |Wi | ≤ n and |Wj | ≤ n, F changes
its value at most 2n times and its last value is correct, i.e., F is a (2n + 1)-shot comparator.
To see that FINSn is not 2n-shot comparable, by way of a contradiction let us assume thatsuch a 2n-shot comparator G does exist. In particular, the comparator G on any input (i, j) suchthat |Wi | ≤ n and |Wj | ≤ n changes its value at most 2n − 1 times. By the recursion theorem (seeRogers, 1987, 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 a least 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 aleast 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 .

5.12. Proof of Lemma 25
Proof Let L be as given in the lemma. Let h(i, t) be a recursive function such that limt→∞ h(i, t) = 1
iff for all j < i, Wf (j) 6= Wf (i) . Note that such a recursive h can be easily constructed. Also notethat 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, Ui,t = {h1, xi : x < hi, t, zi} ∪21

V ERIFIERS , C OMPARATORS AND S TANDARDISERS{h0, hi, t, zii} ∪ {h2, xi : x ∈ N}, where z is the least t0 ≥ t such that h(i, t0 ) = 0 (the element
h0, hi, t, zii ensures that Ui,t 6= Uj,s whenever 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
the correct comparison as “yes” iff h0, y 0 i appears in the other language with y 0 = y.
5.13. Proof of Proposition 27
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, 1974),
such that Wg(e,d) and Wh(e,d) are defined as follows for e 6= d:
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 and 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 , forsome k 6= e. Then, Wg(e,d) starts following Uk . Note that the above search should neversucceed, as otherwise, F (h(e, d), g(e, d)) needs to output “no” in the limit, but it has no moremind 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) are following Ud . Since wehave Se,d ⊆ Ud ⊆ Ue , Step 2 will eventually succeed in finding this, and thus Wh(e,d) would startfollowing Ue . Hence eventually F (g(e, d), h(e, d)) needs to output “no” and the procedure willreach Step 3. Here again Re,d ⊆ Ud ⊆ Ue , and thus 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, the tell-tale set
enumerator initially just enumerates ∅, and searches for a d such that Xe,d is defined by the above
process. It then enumerates Xe,d .

22

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

5.14. Proof of Example 30
Proof The non-learnability follows from the fact that the set N does not have any tell-tale set withrespect to this class (see Angluin, 1980; Baliga et al., 1999). This also implies that the class is
not verifiable. The positive results are obtained by the following fact: From an index 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 have very 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 f such that whenever We is of theform 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 for the set 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 the general implicationthat every 2-shot standardisable class is 3-shot comparable.

5.15. Proof of Proposition 31
Proof Suppose L has an n-shot learner M . Without loss of 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 σ1 gets 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, the comparator 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 , then clearly 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.

5.16. Proof of Theorem 32
Proof This can be seen as follows: For all e, s ∈ N, we define Le,0 := {e} ⊕ N, and for s > 0 {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 and WMe,t (σ) ⊃ content(σ) ;Le,s :=
{e} ⊕ N , otherwise.
Here, we assume without loss of generality that at any step, at most one σ is found in the firstclause 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 a conservative behaviourally correct learner.
23

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

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 an even element. If thefirst 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 F outputs “yes” until it
finds an s such that for some finite 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 eachenumerates some odd number not belonging to {2x + 1 : x ∈ D}; F (i, j) will now output “yes”.
Note that 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.
Similar proof as above also shows that L is 3-shot verifiable.

5.17. Proof of Theorem 33
Proof Let L = {L0 , L1 , L2 , . . . , } be a class of r.e. sets such that
L0 := {2y : y ∈ N} and for all x ∈ N ,
({2y : y ∈ N ∧ y ≤ t} \ {2x}) ∪ {2t + 1} ,Lx+1 :=
{2y : y ∈ N ∧ y 6= x} ,if t is the first step at which somep < log(x) is found such that
U (p, ε) = 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 Proposition 30, let f be a recursive function such that 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 all evennumbers but one (say 2x) below 2y + 1 appear in Wd . Simulate We until the first of thefollowing 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 one of 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 thefollowing case distinction:
24

V ERIFIERS , C OMPARATORS AND S TANDARDISERS

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} forsome 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 other contains 2x or some
odd number different from 2y + 1 or an even number larger than 2y, so that F will output “no”
in the limit.
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 the limit;
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 equalto {2z : z ∈ N}. If both Wd and We are equal to {2z : z ∈ N}, then Case 2 will almost
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 ifthere are distinct i, j with j < i such that F performs the instructions in Case i at Step t01 and thenperforms 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 Fchanges 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 thefirst 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 those in theearlier 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., 1999, Corollary 3): for every set D of even numbers, there is some x > max(D)with C(x) ≥ log(x), so that D ⊂ Lx+1 ⊂ L0 .

25