ON THE INFLUENCE OF TECHNOLOGY ON LEARNINGPROCESSES∗ILJA KUCEVALOVS, OJARS KRASTS, RUSIN FREIVALDS

Institute of Mathematics and Computer Science, University of Latvia, Raina bulvaris 29, Riga,
LV-1459, Latvia
THOMAS ZEUGMANN

Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan
Received (January 6, 2013)
Revised (May 9, 2014)
ABSTRACT
Probabilistic computations and frequency computations were invented for the same purpose, namely, to study possible advantages of technology involving random choices. Recently several authors have discovered close relationships of these generalizations of deterministic computations to computations taking advice. Various forms of computation taking advice were studied by Karp and Lipton [1], Damm and Holzer [2], and Freivalds [3].
In the present paper, we apply the nonconstructive, probabilistic, and frequency methods to an inductive inference paradigm originally due to Gold [4] and investigate theirimpact on the resulting learning models. Several trade-os with respect to the resulting
learnability are shown.

Keywords : probabilistic computations; frequency computations; nonconstructive methods; algorithmic learning; inductive inference

1. Introduction
Probabilistic algorithms and automata were invented to simulate random processes
in living organisms. A fundamental question related to this research is whether
or not this simulation is adequate, i.e., whether or not indeterministic processes inliving beings are probabilistic in the sense described by Pascal and Fermat. Quantum
theory showed that indeterministic processes in the microworld surely need a more
complicated description. This makes the usage of such generalized computations apractical problem in Computer Science.
Frequency algorithms were introduced by Rose [5] with a clear aim to havea completely deterministic mechanism with properties of probabilistic algorithms.
∗ The research was supported by the project ERAF Nr.2DP/2.1.1.1/13/APIA/VIAA/027 and theInvitation Fellowship for Research in Japan S12052 by Japan Society for the Promotion of Science12Frequency computations became popular because of their relation to the notion of
autoreducibility.
In his paper [3], Freivalds examined nonconstructive proofs in computation theory and introduced the notion of nonconstructive computation. The notion was
based on Freivalds' observation of nonconstructive proofs as of a construction ofalgorithms that do not rely exclusively on the natural input data and their own
internal mechanisms, but utilize some additional help from the outside as well.
For instance, consider a version of Barzdin²' lemma [6] that sets an upper bound oflog n on Kolmogorov complexity of characteristic words of recursively enumerable
sets. The proof of this lemma is nonconstructive (which is natural due to the Kolmogorov complexity notion used), but in [3] it is reinterpreted as a construction ofan algorithm that utilizes an amount of log n of additional information.
In [3] a simple denition of nonconstructive computation was introduced, considering language recognition by nite automata using additional information. It waspointed out that other computational models could be utilized in nonconstructive
computation, too. Clearly, Freivalds' [3] denitions should be revised in this case.
As far as inductive inference is concerned, nonconstructive proofs are not uncommon. The formal theory of inductive inference due to Solomono [7, 8] isbased on the notion of algorithmic probability, an uncomputable function closely
related to Kolmogorov complexity [6]. The learning model considered in this paper
is Gold's [4] identication in the limit model. This model is less abstract and moreclosely related to computational models than Solomono's [7, 8] formal theory.
However, nonconstructive proofs can be found here as well.
For example, Case and Smith [9] explicitly mention that the proof of their Theorem 2.3 is nonconstructive. Indeed, it is based on observation of two possible cases
in a certain construction such that there is no way to determine which of the cases
actually holds. A similar proof has, for example, Theorem 22 in [10]. Using theterminology of [3], we may say that the amount of nonconstructivity assumed inthese proofs is 1 bit.
On the other hand, some versions of classical identication criteria utilizing additional information have already been considered (see, for example, [11, 12, 13]).
However, the additional information considered is usually of some specic kind
and/or the objects of identication are limited to a certain class (say, identication of recursive functions). Second, to our knowledge there were no references toformalizing nonconstructive proofs in the existing literature.
In the present paper we study the problem of what impact do probabilistic
computations and frequency computations have on inductive inference paradigms.
The resulting learning models are compared to one another. Additionally, a learningmodel is considered in which the learner receives in addition to the usual graph ofa target function a certain amount of nonconstructive information.

3

2. Notations and Denitions
Unspecied notations follow Rogers [14]. In addition to or in contrast with [14] we
use the following. Let N = {0, 1, 2, . . .} be the set of all natural numbers, and let
furthermore N+ = N \ {0} be the set of all positive natural numbers. We use N∗ todenote the set of all nite sequences of natural numbers. By |S| and ℘(S) we denotethe cardinality and power set of a set S , respectively. Let ∅, ∈, ⊂, ⊆, ⊃, ⊇, and #denote the empty set, element of, proper subset, subset, proper superset, superset,
and incomparability of sets, respectively.
Let n ∈ N be such that n ≥ 2. The set of all partial recursive functions and of all recursive functions of one respectively n variables over N is denoted by P, R, P n , Rn , respectively. Note that the recursive functions are total.
For every f ∈ P we use dom(f ) to denote the domain of the function f , i.e.,dom(f ) = {x | x ∈ N, f (x) is dened}. By Val(f ) we denote the range of f , thatis, Val(f ) = {f (x) | x ∈ dom(f )}.
Any function ψ ∈ P 2 is called a numbering. Let ψ ∈ P 2 , then we write ψi insteadof λx.ψ(i, x) and set Pψ = {ψi | i ∈ N} as well as Rψ = Pψ ∩ R. So if f ∈ Pψ ,then there is a number i ∈ N such that f = ψi . If f ∈ P and i ∈ N are such that
ψi = f , then i is called a ψ program for the function f . Let ψ be any numbering, andlet i, x ∈ N; if ψi (x) is dened (abbr. ψi (x) ↓ ) then we also say that ψi (x) converges.
Otherwise, ψi (x) is said to diverge (abbr. ψi (x) ↑ ). Let ψ ∈ P 2 and f ∈ P ; then weuse minψ f to denote the least number i such that ψi = f .
A numbering ϕ ∈ P 2 is called a Gödel numbering (cf. Rogers [14]) if Pϕ = P ,and for every numbering ψ ∈ P 2 , there is a compiler c ∈ R such that ψi = ϕc(i)for all i ∈ N. We use Göd to denote the set of all Gödel numberings. For further
information concerning Gödel numberings and their properties we refer the reader
to [15, 14].
By NUM = {U | there is a ψ ∈ R2 such that U ⊆ Pψ } we denote the family of
all subsets of all recursively enumerable classes of recursive functions. Furthermore,
we use NUM! = {U | there is a ψ ∈ R2 such that U = Pψ } to denote the family of
all recursively enumerable classes of recursive functions. The elements of NUM! arereferred to as indexed families.
Let h. . .i be any recursive encoding of N∗ onto N (cf. Rogers [14]). We write f n
instead of h(f (0), . . . , f (n))i, for all n ∈ N and all f ∈ R.
A sequence (jn )n∈N of natural numbers is said to converge to the number j
if jn = j for all but nitely many n ∈ N. Moreover, a sequence (jn )n∈N of natural
numbers is said to nitely converge to the number j if it converges to j and for
all n ∈ N, jn = jn+1 implies jk = j for all k ≥ n. Now we are ready to dene thelearning models considered in this paper.

2.1. Deterministic Learning of Recursive Functions
When learning recursive functions growing initial segments f n , where n = 0, 1, 2, . . .,are fed to the learning algorithm, henceforth called strategy. For each initial segment

4

the strategy has then to compute a hypothesis in which is a natural number. These
hypotheses are interpreted with respect to a suitably chosen hypothesis space ψwhich is a numbering. The interpretation of the hypothesis in is that the strategy
conjectures program in in the numbering ψ to compute the target function f . Furthermore, one requires the sequence (in )n∈N of all computed hypotheses to converge
to a program i correctly computing the target function f , i.e., ψi = f . A strategy
learns a class of recursive functions provided it can learn every function from it. The
model just explained is basically learning in the limit as introduced by Gold [4].
Many variations of this model have been studied (cf., e.g., [9, 16, 17, 18], and thereferences therein). More formally, we have the following denition.

Denition 2.1 (Gold [19, 4]) Let U ⊆ R and let ψ ∈ P 2 . The class U is said tobe learnable in the limit with respect to ψ if there is a strategy S ∈ P such that foreach function f ∈ U ,(1) for all n ∈ N, S(f n ) is dened,
(2) there is a j ∈ N with ψj = f and the sequence (S(f n ))n∈N converges to j .
If U is learnable in the limit with respect to ψ by S then we write U ∈ LIMψ (S).
Furthermore, let LIMψ = {U | U is learnable in the limit with respect to ψ}, andlet LIM be the collection of all classes learnable in the limit with respect to someShypothesis space, i.e., LIM = ψ∈P 2 LIMψ .
Some remarks are mandatory here. Let us start with the semantics of the hypotheses produced by a strategy S . If S is dened on input f n , then we always
interpret the number S(f n ) as a ψ number. This convention is adopted to all thedenitions below. Furthermore, it is easy to show that LIMϕ = LIM for every Gödel
numbering ϕ (cf. [20, 9]). In the above denition LIM stands for limit. Moreover,in accordance with the denition of convergence, only nitely many data of thegraph of a function f were available to the strategy S up to the unknown pointof convergence. Therefore, some form of learning must have taken place. Thus, theuse of the term learn in the above denition is indeed justied. Note that insteadof LIM sometimes the notation EX is used in the literature, where EX stands forexplain (cf., e.g., [9, 17]).
In general it is not decidable whether or not a strategy has already converged
when successively fed some graph of a function. With the next denition we consider
a special case where it has to be decidable whether or not a strategy has learned its
input function. That is, we replace the requirement that the sequence of all createdhypotheses has to converge by has to converge nitely.

Denition 2.2 (Gold [4], Trakhtenbrot and Barzdin [21]) Let U ⊆ R andlet ψ ∈ P 2 . The class U is said to be nitely learnable with respect to ψ if there isa strategy S ∈ P such that for each function f ∈ U ,(1) for all n ∈ N, S(f n ) is dened,

5(2) there is a j ∈ N such that ψj = f and the sequence (S(f n ))n∈N nitely converges
to j .
If U is nitely learnable with respect to ψ by a strategy S , we write U ∈ FINψ (S).
The learning types FINψ and FIN are dened analogously to the above.
It is easy to prove that FINϕ = FIN for every Gödel numbering ϕ. Moreover, wehave FIN ⊂ LIM (cf., e.g., [18]). Since we are mainly interested in nite learning in
the present paper, we shall consider all variations dened below for nite learning
only.
In the following modication of Denition 2.2 we require the strategy to nitely
converge to minψ f instead of converging nitely to any program for the target function f . This modication goes back to Freivalds [22] and Kinber [23] who considered
it for learning in the limit.

Denition 2.3. Let U ⊆ R and let ψ ∈ P 2 . The class U is said to be nitely
ψ -minimal learnable with respect to ψ if there is a strategy S ∈ P such that for eachfunction f ∈ U ,(1) for all n ∈ N, S(f n ) is dened,
(2) the sequence (S(f n ))n∈N nitely converges to minψ f .
If U is nitely ψ -minimal learnable with respect to ψ by a strategy S then we
write U ∈ MIN-FIN ψ (S). The learning types MIN-FIN ψ and MIN-FIN are denedanalogously to the above.

Denition 2.4. Let U ⊆ R and let ψ ∈ P 2 . The class U is said to be nitely

ψ -nearly minimal learnable with respect to ψ if there is a strategy S ∈ P and aconstant c ≥ 0 such that for each function f ∈ U ,(1) for all n ∈ N, S(f n ) is dened,
(2) the sequence (S(f n ))n∈N nitely converges to a program i such that ϕi = f
and i ≤ minψ f + c.
If U is nitely ψ -nearly minimal learnable with respect to ψ by a strategy S then we
write U ∈ NEARLY-MIN-FINψ (S). The learning types NEARLY-MIN-FINψ and
NEARLY-MIN-FIN are dened analogously to the above.
Note that there is also slightly dierent version of nearly minimal learnability inthe literature, where nearly minimal refers to within a recursive fundge factor h.
That is, one requires the learner to nitely converge to a correct program i suchthat i ≤ h(minψ f , where f is the target function (cf., e.g., Chen [24], and thereferences therein).

2.2. Nonconstructive Learning of Recursive Functions
The next model we shall consider in this paper derives its motivation from thefact that R ∈/ LIM, and thus R ∈/ FIN and R ∈/ MIN-FIN . Freivalds and Zeug-6mann [25] introduced a new measure to classify the diculty of learning the class R
or to learn indexed families of recursive functions under additional constraints suchas nite learning or nite minimal learning. This new measure is the amount of
nonconstructivity needed to achieve the specied learning goal.
The strategies used for nonconstructive inductive inference take as input not
only the encoded graph of a function f ∈ R but also a help-word w. The help-words
are assumed to be encoded in binary. So, for such strategies we write S(f m , w) to
denote the program output by S . Since there are innitely many functions to learn,a parameterization is necessary. That is, we allow for every n a possibly dierent
help-word w and we require the strategy to learn every recursive function containedin {ψ0 , . . . , ψn } with respect to the numbering ψ .

Denition 2.5 (Freivalds and Zeugmann [25]) Let ψ ∈ P 2 , let U ⊆ R, andlet d ∈ R. A strategy S ∈ P 2 nitely infers U with nonconstructivity d(n) withrespect to ψ , if for each n ∈ N there is a help-word w of length at most d(n) suchthat for every f ∈ U ∩ {ψ0 , ψ1 , . . . , ψn }(1) S(f m , w) is dened for all m ∈ N, and(2) the sequence (S(f m , w))m∈N nitely converges to a program i satisfying ψi = f .
It follows from this denition that a help word w for every n that is larger thanthe minimal ψ -program i of the target function f also produces a correct result j but
it is allowed that the produced result is dierent from i. This is quite natural, since
there may be many distinct ψ -programs for f in the numbering ψ . In particular,
if ψ is a Gödel numbering then there are innitely many ψ -programs for f .
Nonconstructive nite minimal inference and nonconstructive nite nearly minimal identication are dened in a way analogous to the above.
To simplify notation, we make the following convention. Whenever we talk about
nonconstructivity log n, we assume that the logarithmic function lg n to the base 2
is replaced by its integer valued counterpart. That is, we set log n =df blg nc + 1
and log 0 =df 1, where bxc denotes the oor function.
As far as the present paper is concerned, the following results obtained in [25] arerelevant. Below we use succ to denote the successor function, i.e., succ(n) =df n + 1
for all n ∈ N.

Theorem 1. Let ϕ ∈ Göd be arbitrarily xed. Then there is a strategy S ∈ P 2

such that the class R can be ϕ-minimal nitely identied with nonconstructivity
succ(n) with respect to ϕ.

Theorem 2. Let U be any indexed family, and let ψ ∈ R2 be any numbering for U .

Then there is a strategy S ∈ P 2 such that the class U can be ψ -minimal nitely
identied with nonconstructivity 2 · log n with respect to ψ .

Theorem 3. There is an indexed family U and a numbering ψ ∈ R2 for it suchthat no strategy S ∈ P 2 can ψ -minimal nitely identify the class U with nonconstructivity c · log n with respect to ψ , where c ∈ (0, 1) is any constant.

7

2.3. Finite Frequency Learning
The notion of frequency computation was introduced by G. Rose [5] as an attempt tohave an absolutely deterministic mechanism with properties similar to probabilistic
algorithms. The denition was as follows. Let N = {0, 1, 2, . . .} denote the set of
all natural numbers. A function f : N → N is said to be (m, n)-computable, where1 ≤ m ≤ n, m, n ∈ N, i there exists a recursive function R: Nn → Nn such that,for all n-tuples (x1 , · · · , xn ) ∈ Nn of mutually distinct natural numbers,|{i | (R(x1 , · · · , xn ))i = f (xi ) , 1 ≤ i ≤ n}| ≥ m ,where (R(x1 , · · · , xn ))i denotes the ith component of R(x1 , · · · , xn ).
McNaughton [26] cites in his survey a problem (posed by Myhill) whether f has
to be recursive if m is close to n. This problem was answered by Trakhtenbrot [27]who showed the following.

Theorem 4. If a function f : N → N is (m, n)-computable, where 2m > n, then fis recursive.

On the other hand, Trakhtenbrot [27] proved that, if 2m = n then nonrecursive functions can be (m, n)-computed. Kinber [28, 29] extended the research by considering
frequency enumeration of sets, and this was further studied by Austinat et al. [30].
The class of (m, n)-computable sets equals the class of recursive sets if and only
if 2m > n. The notion of frequency computation can be extended to other modelsof computation. Frequency computation in polynomial time was discussed in fulldetail by Hinrichs and Wechsung [31]. Frequency computations became increasingly
popular when the relation between frequency computation and computation with asmall number of queries was discovered [32, 33, 34, 35].
So it is only natural to study nite frequency learning, too. The corresponding
learning model was introduced by Kinber et al. [36] and called parallel learning. In(m, n)-nite frequency learning the strategy takes as input an n-tuple (f1x , . . . , fnx )of initial segments of pairwise dierent target functions and outputs an n-tuple(ix1 , . . . , ixn ) of hypotheses. The notion of nite convergence of sequences of numbers
directly carries over to n-tuples of numbers. Therefore, one requires the sequence ofn-tuples (ix1 , . . . , ixn )x∈N to converge nitely. The learner is successful if at least mfunctions have been learned nitely.
However, in the present paper we shall deal only with nite minimal frequency
learnability which is formally dened as follows.

Denition 2.6. Let U ⊆ R, let ψ ∈ P 2 , and let m, n ∈ N+ , where m ≤ n. The

class U is said to be nitely ψ -minimal learnable with frequency (m, n) with respectto ψ if there is a strategy S ∈ P n that takes as input growing initial segments ofpairwise dierent functions f1 , . . . , fn ∈ U and outputs n-tuples of natural numbers
such that(1) S(f1x , . . . , fnx ) is dened for all x ∈ N,

8(2) the sequence (S(f1x , . . . , fnx ))x∈N nitely converges to an n-tuple (i1 , . . . , in ),and(3) |{j | 1 ≤ j ≤ n and ij = minψ fj }| ≥ m.
If U is nitely ψ -minimal learnable with frequency (m, n) with respect to ψ by a
(m,n)
(m,n)
strategy S then we write U ∈ MIN-FIN ψ(S). The learning types MIN-FIN ψ
and MIN-FIN (m,n) are dened analogously to the above.

2.4. Probabilistic Learning of Recursive Functions
Finite identication of classes of recursive functions by probabilistic strategies wasintroduced by Freivalds [37] and has found considerable attention ever since (cf., e.g.,[38, 39, 40] and the references therein).
Intuitively speaking, a probabilistic strategy is allowed to ip a fair coin in eachstep of its computation and then to branch its computation in dependence on theoutcome of its coin-ip. So we can assume that a probabilistic strategy is realized bya three tape Turing machine. On its rst semi-innite and read-only tape the resultsof its coin-ips are written. Once such a sequence s is xed the machine works as adeterministic strategy with the additional information s. On the second semi-inniteand read-only tape all the values f (0), f (1), f (2), . . . of the target function f are
written. The third tape of the machine is write-only. The machine computes thena sequence of natural numbers which is written on its third tape. If this sequence
converges nitely to an index j such that ψj = f then we say that the machine was
successful. The probability that S nitely learns f is then dened by the usual Borel
measure on the set of all innite 0-1-sequences s such that, on input s and f , thestrategy outputs a sequence that nitely converges to a correct ψ -program for f .

Denition 2.7. Let ψ ∈ P 2 be any numbering. We say that a probabilistic strategy S FIN-learns a function f with probability p with respect to ψ if with probability
no less than p there is a computation path such that the strategy S produces a correct result on f , i.e., a number j such that ψj = f , andA probabilistic strategy S FIN-learns a class U ⊆ R with probability p with respectto ψ if it FIN -learns every function f ∈ U with probability p with respect to ψ .
A class U ⊆ R is said to be FIN-learnable with probability p with respect to ψ
if there exists a strategy S ∈ P that FIN-learns U with probability p with respectto ψ .

Denition 2.7 can be directly generalized to probabilistic MIN-FIN -learning andto probabilistic NEARLY-MIN-FIN-learning in the obvious way.

3. Results
After having dened various learning models we are in the position to investigate theimpact of the dierent technological choices on the resulting learning paradigms.

9

We start this section by establishing several trade-os between deterministic inference, probabilistic identication, frequency learning, and learning allowing for acertain amount of nonconstructivity. In order to achieve good trade-os, we also
vary the learning goal to a certain extent. That is, we look just at nite learning,at nite minimal inference, and at nite nearly minimal identication, while varying or not varying between deterministic learning methods, probabilistic inference
methods, nonconstructive learning methods, and frequency learning (cf. Theorem 5
and Theorem 6).

Theorem 5. There is a Gödel numbering ϕ ∈ P 2 and an indexed family U ofrecursive functions such that

(1) U ∈ FIN,
(2) U can be probabilistically MIN-FIN ϕ -identied with probability 12 ,(3) U can be probabilistically NEARLY-MIN-FINϕ -identied with probability 32 ,(4) U cannot be deterministically MIN-FIN ϕ -identied,
1-identied for all m, n ∈ N, m ≤ n, provided m(5) U cannot be MIN-FIN (m,n)ϕ
n > 2,(6) U cannot be deterministically MIN-FIN ϕ -identied with nonconstructivity o(log n).

Proof. Our proof consists of four parts. First, we construct an indexed family V ofrecursive functions such that V cannot be MIN-FIN ϕ -inferred with nonconstructivity o(log n). Second, we dene a subfamily V 0 of V consisting of constant functions
only. Third, we construct a Gödel numbering ϕ and a new indexed family of constants U being a subfamily of V 0 with all the needed properties. Fourth, we provethe existence of the needed probabilistic strategies.
Part I. We consider a specic bijection c: N × N → N which can be traced
back to Pepis [41] and Kalmár [42], i.e., c(u, v) = (2u − 1) + 2u+1 v . In this way,
if w = c(u, v) for any arbitrarily xed u, then the value of w corresponding to (u, v)
is linear in v .
The class V is dened by constructing a numbering τ ∈ R2 and then dening
the class V to be V = Rτ . Let k ∈ N be arbitrarily xed and let u, v ∈ N be theuniquely determined numbers such that k = c(u, v).
First, we dene the values τ3k (0) = τ3k+1 (0) = τ3k+2 (0) = k . Hence, for any
arbitrarily xed k , the minimal τ -program of any function f with a value f (0) = k
can be only 3k, 3k + 1 or 3k + 2.
Furthermore, we interpret every function in P 2 as a strategy and obtain thusan eective enumeration S0 , S1 , S2 , . . . of all possible strategies. We proceed inductively. Below, for ` ∈ N, we use the shortcut k `+1 to denote the encoding of f ` ofthe initial segment of any function f for which f (z) = k for z = 0, . . . , `.
In order to dene τ3k (n), τ3k+1 (n), τ3k+2 (n) for n > 1 we dovetail the following
computations. We successively dene the function valuesτ3k (n − 1) = τ3k+1 (n − 1) = τ3k+2 (n − 1) = k

10for n = 2, 3 . . ., until we nd the least n such that the following Conditions (A)and (B) are satised.
(A) There is an ` < n such that each of the values Su (k, v), . . . , Su (k `+1 , v) turns
out to be computable in at most n steps of computation.
(B) Su (k, v) 6= Su (k 2 , v) 6= · · · 6= Su (k ` , v) = Su (k `+1 , v).
If Conditions (A) and (B) never turn out to be satised then the function valuesτ3k (n), τ3k+1 (n), τ3k+2 (n) are dened for all n ∈ N, and thus τ3k , τ3k+1 , τ3k+2 ∈ R.
On the other hand, if Conditions (A) and (B) turn out to be satised then
Condition (B) indicates the sequence Su (k, v), . . . , Su (k `+1 , v) may have converged
nitely. That is, it either has converged nitely or it cannot converge nitely at all.
Assuming that Conditions (A) and (B) turn out to be satised, we continue
to dene the functions τ3k , τ3k+1 , τ3k+2 as follows. We dene z(k) = Su (k ` , v). Ifz(k) ∈ {3k, 3k + 1, 3k + 2} then we dene τz(k) (x) = k + 1 for all x ≥ n and for theremaining m ∈ {3k, 3k + 1, 3k + 2} \ {z(k)} we set τm (x) = k for all x ≥ n. Thus,by construction we have τ ∈ R2 and so V = Rτ is an indexed family.
Now suppose that Su is an arbitrary strategy that nitely τ -minimal learns V
with a certain amount of nonconstructivity. We wish to estimate the amount of
nonconstructivity needed to achieve this.
To do this, we wish to estimate a number q such that s bits of nonconstructivity
do not suce for Su to learn all functions in {τ0 , τ1 , . . . , τq } in the desired sense. Lett = 2s − 1 be the largest natural number in binary notation which does not exceeds bits. Consider the values k0 = c(u, 0), k1 = c(u, 1), k2 = c(u, 2), . . . kt = c(u, t). By
the choice of the bijection c we know that kt = c(u, t) equals (2u − 1) + 2u+1 t andthus kt does not exceed 2u+2 t.
For each i ∈ {0, 1, . . . , t} either z(ki ) is dened or it is not dened. If z(ki ) isdened then Su does not learn τz(ki ) nitely with respect to τ . If z(ki ) is not denedthen Su does not learn nitely any of the functions τ3ki , τ3ki +1 , τ3ki +2 . Hence there
always is a function in {τ0 , τ1 , . . . , τ3kt +2 } ⊆ {τ0 , τ1 , . . . , τ3·2u+2 kt +2 } which is notlearnable by the strategy Su with at most s bits of nonconstructivity.
So, if q ≥ 3·2u+2 kt +2 = const ·t = const ·2s then the additional help information
fails to produce a correct result by the strategy Su for at least one function in{τ0 , τ1 , . . . , τq }. It follows that Su needs at least log q bits of nonconstructivity tolearn all the functions in {τ0 , τ1 , . . . , τq }.

Part II. We dene the class V 0 ⊆ V to be the subclass of V that consists of all

the constant functions in V . This family is FIN-learnable because the family of all
the constant functions is FIN-learnable with respect to any Gödel numbering ϕ.

Part III. We construct a Gödel numbering ϕ using some standard Gödel numbering ψ of P , e.g., the numbering using all possible Turing machines and ourindexed family V = {τn | n ∈ N} of recursive functions. For all n ∈ N and11

all i ∈ {0, 1, . . . , 14} we dene
ϕ15n+i =df

ψ3n+i ,
τ12n+i−3 ,if i = 0, 1, 2 ;if i ∈ {3, . . . , 14} .

The family U consists of those constants from the family V 0 whose minimal
program in the numbering ϕ is dened to equal some τj but not dened to equal
some ψk (i.e., we demand the minimal program in the numbering ϕ to be congruent to 3, 4, . . . , 14 modulo 15). Notice that the family U is non-empty because, for
arbitrary n, among the ϕ-programs 15n, 15n + 1, . . . , 15n + 14 there are at least 4
distinct programs for constant functions but only 3 programs for functions dened
as ϕ15n = ψ3n , ϕ15n+1 = ψ3n+1 , ϕ15n+2 = ψ3n+2 .

Part IV. For all functions in U the minimal program in the numbering ϕ is tobe congruent to 3, 4, . . . , 14 modulo 15 but the construction of V ensures that nostrategy with an amount of nonconstructivity o(log n) can produce this result.
The probabilistic strategy producing minimal ϕ-programs for the functions in U
reads the value f (0) = k of the target function. Then it computes d =df 3k mod 12
and n =df bk/4c and outputs 15n + 3 + d with probability 1/2, and 15n + 3 + d + 1
with probability 1/2. For every function in U one of these results is the correct
minimal ϕ-program.
The probabilistic strategy producing nearly minimal ϕ-programs for the functions in U reads the value f (0) = k of the target function, computes d =df 3k mod 12
and n =df bk/4c and outputs 15n + 3 + d, 15n + 3 + d + 1, and 15n + 3 + d + 2
each with probability 1/3. For every function in U at least two of these results arecorrect ϕ-programs and all of them are nearly minimal.
It remains to show Assertion (4). Recall that all functions in U are constant. If
we know that the target function is constant, we have all the information about thisfunction merely from f (0). MIN-FIN ϕ -identication of a constant function allows
only one possible correct result for any target function. Hence this learning can be
described by a function g(n) transforming n = f (0) into the minimum index of f
in the numbering ϕ. Suppose to the contrary that U is MIN-FIN (m,n)-identied
ϕ1with m>.
Then
byTheorem4,
thefunctiongisrecursive.
However,
we haven2already proved in Assertion (3) that U cannot be deterministically MIN-FIN ϕ identied. So, we have a contradiction, and thus our supposition must be false.
Assertion (4) is shown.
Theorem 6. There is a Gödel numbering ϕ and a family U of recursive functions
such that(1) U cannot be probabilistically MIN-FIN ϕ -identied with a probability exceeding 12 ,(2) U can be MIN-FIN (n−1,n)-identied for every n ∈ N+ ,ϕ(3) U cannot be deterministically MIN-FIN ϕ -identied.

12

Proof. Let ϕ0 ∈ P 2 be any arbitrarily xed Gödel numbering of P . Without lossof generality we can assume that ϕ00 is the nowhere dened function.
We interprete every ϕ0i , i ∈ N, as a probabilistic strategy and thus obtain aneective enumeration (Si )i∈N of all probabilistic strategies. Note that S0 is then the
nowhere dened probabilistic strategy. Therefore, S0 does not MIN-FIN -identify
any class of recursive functions. Now, our goal is to construct gradually a class U byeliminating all strategies Si as the strategy which could MIN-FIN -identify U witha probability exceeding 21 . The class U will be dened non-algorithmically but thefunctions in U will be recursive. In order to do so, we start with the denition of
the desired Gödel numbering ϕ. We set ϕ0 = ϕ00 andϕ(2v)! = ϕ0v

for all v ∈ N .

(1)

So, we have already dened ϕ0 , ϕ1 , ϕ2 , ϕ24 , ϕ720 , . . ., and it remains to dene theall the functions ϕu , where u is not of the form (2v)! for some v ∈ N. In order todo so we consider the remaining indices of functions in the numbering ϕ divided infragments

H(v) = [(2v)! + 1, (2(v + 1))! − 1 for all v ∈ N+ .

(2)

For example, we have H(1) = [3, 23] and H(2) = [25, 719]. When all these functionsin the numbering ϕ are dened then the denition given in (1) ensures that the
numbering ϕ is a Gödel numbering of P . The denition of the desired class U andof the remaining functions in the numbering ϕ is done simultaneously.
The functions f ∈ U may have only one value x such that f (x) = 0. This valueof x separates the head and the tail of the function f . Each function f ∈ U isconstructed to eliminate some strategy Si .
The head of any function f ∈ U is such that the values f (0), f (1), · · · , f (x − 1)contain full information about the minimum ϕ-programs of all functions f ∈ U
included to eliminate the strategies S0 , S1 , S2 , . . . , Si−1 but not about the function
included to eliminate the strategy Si . All the values f (0), f (1), · · · , f (x − 1) equalor exceed 1. All the values f (x + 1), f (x + 2), · · · in the tail of the function f ∈ U
exceed 1.
The construction of ϕ is divided in time-steps t = 1, 2, 3, . . .. In each of thesetime-steps we deal with one fragment H(v) during a nite number of steps of computation. During this time-step we try to eliminate the strategy Sv .
By G(v, t) we denote a current conjecture G(v, t) ⊆ H(v) which functions f fromthe fragment H(v) are likely to enter the class U . For any v ∈ N+ and t1 , t2 ∈ N+
we have(t2 > t1 ) implies G(v, t2 ) ⊆ G(v, t1 ) .
A current conjecture G(v, t) may be changed during the subsequent time-steps,
but only a nite number of times.

13

We consider these fragments H(v) during t steps of computation in the following
order:(v = 1, t = 1)(v = 1, t = 2), (v = 2, t = 3)(v = 1, t = 4), (v = 2, t = 5), (v = 3, t = 6)...
Hence we return to every fragment H(v) innitely many times. When considering
the fragment H(v) during t steps of computation we distinguish whether or not the
fragment has been considered earlier. If not, then we take the current conjectures

G(1, t), G(2, t), . . . , G(v − 1, t)
which functions from preceding fragments are likely to enter U . We start v + 1
distinct new functions in this fragment. We dene every such new function ϕu containing in its head ϕu (0), ϕu (1), ϕu (t − 1) all the information about all the functionsin the fragments

H(1), . . . , H(v − 1)(3)that have not yet been in construction. (There would be no diculty to incorporate
all this information into ϕu (0) alone.) We add the value ϕu (t) = 0.
We start constructing the tails of these v + 1 functions by using distinct
constants c > 0. Since only v functions ϕ2! , ϕ4! , . . . , ϕ(2v)! precede the fragment
H(v) = [(2v)! + 1, (2(v + 1))! − 1], at least one of these new functions is not among
ϕ2! , ϕ4! , . . . , ϕ(2v)! .
If yes then for every function ϕu in this fragment whose construction is not yet
stopped, we perform the strategy Sv on this function during t steps of computation.
(By saying we perform the strategy Sv on this function we mean that if thestrategy asks for values of the target function already dened, we give the correct
value. However, if the strategy asks for values of the target function not yet dened,
we use values c for the tail of the function and we add values ϕu (y) = c to thedenition of this function for all y ≥ t.) Since Sv is a probabilistic strategy, we
compute all possible computation paths during t steps of computation and obtain
the probabilities of all possible results.
We dene G(v, t + 1) consisting of all these v + 1 newly added functions ϕu .
Additionally we dene G(a, t + 1) = G(a, t) for all nonempty G(a, t) dened earlier.
If Sv has produced the result u with a probability exceeding 21 then we stop theconstruction of ϕu leaving innitely many values not dened. We remove u fromG(v, t + 1). Simultaneously, we start a new function ϕw in the same fragment H(v)using the same values where ϕu was dened and giving this function a dierent ϕindex w ∈ H(v) taking a constant c not used in earlier stages of our construction and14dening ϕw (y) = c for all y ≥ t. In this way, the strategy Sv has produced a wrong
result u with a probability exceeding 21 for this function. We add the function ϕw
to the class U and remove all remaining numbers but w from G(v, t + 1).
If Sv has produced the result dierent from u with a probability exceeding 21
then we dene ϕu (y) = ϕt for all y ≥ t, add the function ϕu to the class U andremove all remaining numbers but u from G(v, t + 1). The strategy Sv has produced
a wrong result with a probability exceeding 12 for this function.
In all three cases we end the consideration of the fragment H(v) during t stepsof computation by going to the next time-step.
If a strategy Sv fails to MIN-FIN -identify some function from the class U by
producing a wrong result then we see this after a nite number of time-steps. However, it is possible that for some v the strategy Sv never produces any result witha probability exceeding 12 for a function in H(v). Then our construction returns
to the fragment H(v) innitely many times and several functions in this fragment
become total. In this case we non-algorithmically choose one of these total functions
to enter the class U . The strategy Sv fails on this function because it produces noresult. Hence, Assertion (1) is shown.
Clearly, Assertion (1) directly implies Assertion (3).
Assertion (2) is implied by the sentence containing the specication (3) of thefragments to be considered when starting the denition of ϕu in our proof. Since
the indices of the strategies S0 , S1 , S2 , . . . , Si are well-ordered, and all the targetfunctions in the n-tuple are in the class U , one of the target functions contains thisinformation for all the other functions but not for itself. Hence we can output thecorrect minimal programs for all the other functions but not for this one. This gives
us the frequency (n − 1, n).

4. Conclusions and Open Problems
In the present paper we considered four dierent models of nite learning of classes ofrecursive functions, i.e., deterministic nite learning algorithms, probabilistic nitelearning strategies, inference algorithms that learn nitely with a certain frequency,
and nite learners that are allowed to use a certain amount of nonconstructive
information during the learning process. The resulting learning models have been
compared to one another, and several trade-o have been shown. Basically, the results obtained showed that probabilistic learners, frequency inference algorithms,
and nite learners using a certain amount of nonconstructivity all extend the learning power of deterministic nite learning, but in dierent directions.
It remained open to characterize these learning models in terms of computable
numberings and/or complexity theoretic properties. Such characterizations havebeen undertaken for various learning models and turned out to be extremely usefulfor a deeper understanding of what properties allow a class of recursive functions
to be learnable in one model or another (cf. Zeugmann and Zilles [18] and thereferences therein for more information).

15

It would also be desirable to extend nite learning to quantum nite learning and
to investigate the problem whether or not nite learning quantum strategies again
extend deterministic nite learning in a direction dierent from the ones consideredin this paper.
Furthermore, recently Freivalds [43] and his students have introduced ultrametric algorithms using p-adic numbers instead of real numbers to describe transition
probabilities. This model has been developed further in [44] to nite query learning. That is, instead of receiving the graph of a target function as input, the learneris allowed to ask value queries, where the input is any argument x and the teacher
has then to return f (x). It has been shown that ultrametric algorithms have advantages even over nondeterministic algorithms for certain learning problems in thisnite query learning setting. So, it would be interesting to know whether or notsimilar results could be obtained in the setting considered in this paper.

Acknowledgments. We would like to express our gratitude to the anonymous
reviewers for their careful reading and the helpful suggestions made.

References[1] R. M. Karp and R. J. Lipton, Turing machines that take advice, L' Enseignement
Mathématique, vol. 28, pp. 191209, 1982.
[2] C. Damm and M. Holzer, Automata that take advice, in Mathematical Foundationsof Computer Science 1995, 20th International Symposium, MFCS '95, Prague, Czech
Republic, August 28 - September 1, 1995, Proceedings, vol. 969 of Lecture Notes in
Computer Science, (Berlin), pp. 149158, Springer, 1995.
[3] R. Freivalds, Amount of nonconstructivity in deterministic nite automata, Theoret.
Comput. Sci., vol. 411, no. 38-39, pp. 34363443, 2010.
[4] E. M. Gold, Language identication in the limit, Inform. Control, vol. 10, no. 5,

pp. 447474, 1967.
[5] G. F. Rose, An extended notion of computability, in International Congress for

Logic, Methodology and Philosophy of Science, Stanford University, Stanford, California, August 24 - September 2, 1960, Abstracts of contributed papers, 1960.
[6] M. Li and P. Vitányi, An Introduction to Kolmogorov Complexity and its Applications.

Springer, 3rd ed., 2008.
[7] R. J. Solomono, A formal theory of inductive inference: Part 1, Inform. Control,
vol. 7, no. 1, pp. 122, 1964.
[8] R. J. Solomono, A formal theory of inductive inference: Part 2, Inform. Control,
vol. 7, no. 2, pp. 224254, 1964.
[9] J. Case and C. Smith, Comparison of identication criteria for machine inductive
inference, Theoret. Comput. Sci., vol. 25, no. 2, pp. 193220, 1983.
[10] G. Baliga, J. Case, and S. Jain, Language learning with some negative information,
J. of Comput. Syst. Sci., vol. 51, no. 2, pp. 273285, 1995.
[11] R. Freivald and R. Wiehagen, Inductive inference with additional information, Elektronische Informationsverarbeitung und Kybernetik, vol. 15, no. 4, pp. 179185, 1979.
[12] S. Jain and A. Sharma, Learning in the presence of partial explanations, Inform.
Comput., vol. 95, no. 2, pp. 162191, 1991.
[13] S. Jain and A. Sharma, Learning with the knowledge of an upper bound on program
size, Inform. Comput., vol. 102, no. 1, pp. 118166, 1993.

16[14] H. Rogers, Jr., Theory of Recursive Functions and Eective Computability. McGrawHill, 1967. Reprinted, MIT Press 1987.
[15] Y. L. Ershov, Theory of numberings, in Handbook of Computability Theory (E. R.
Grior, ed.), vol. 140 of Studies in Logic and the Foundations of Mathematics, pp. 473
503, Elsevier, 1999.
[16] R. Freivalds, Inductive inference of recursive functions: Qualitative theory, in Baltic
Computer Science (J. Barzdin² and D. Bjørner, eds.), vol. 502 of Lecture Notes in
Computer Science, pp. 77110, Berlin: Springer, 1991.
[17] S. Jain, D. Osherson, J. S. Royer, and A. Sharma, Systems that Learn: An Introduction
to Learning Theory, second edition. Cambridge, Massachusetts: MIT Press, 1999.
[18] T. Zeugmann and S. Zilles, Learning recursive functions: A survey, Theoret. Comput.
Sci., vol. 397, no. 1-3, pp. 456, 2008. Special issue Forty Years of Inductive Inference:
Dedicated to the 60th Birthday of Rolf Wiehagen.
[19] E. M. Gold, Limiting recursion, J. Symbolic Logic, vol. 30, pp. 2848, 1965.
[20] R. V. Freivalds and E. B. Kinber, Identication in the limit of minimal gödel numbers, in Teoriya Algoritmov i Programm (Y. M. Barzdin, ed.), vol. III, pp. 334,
Latvian State University, 1977. (in Russian).
[21] B. Trakhtenbrot and Y. Barzdin, Finite Automata, Behavior and Synthesis. Amsterdam: North Holland, 1973.
[22] R. V. Freivald, Minimal Gödel numbers and their identication in the limit, inMathematical Foundations of Computer Science 1975, 4th Symposium, Mariánské
Lázn¥, September 1-5, 1975 (J. Be£vá°, ed.), vol. 32 of Lecture Notes in Computer
Science, (Berlin), pp. 219225, Springer-Verlag, 1975.

[23] E.B.. Kinber,  O predel~nom sinteze poqti minimal~nyh gedelevskih nomerov,
in Teori Algoritmov i Programm (J. Barzdin², ed.), vol. I, pp. 212223, Latvian
State University, 1974.
[24] K.-J. Chen, Tradeos in the inductive inference of nearly minimal size programs,
Inform. Control, vol. 52, no. 1, pp. 6886, 1982.
[25] R. Freivalds and T. Zeugmann, On the amount of nonconstructivity in learning recursive functions, in Theory and Applications of Models of Computation, 8th Annual
Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011, Proceedings (M. Ogihara
and J. Tarui, eds.), vol. 6648 of Lecture Notes in Computer Science, pp. 332343,
Springer, 2011.
[26] R. McNaughton, The theory of automata, a survey, Advances in Computers, vol. 2,
pp. 379421, 1961.
[27] B. A. Trakhtenbrot, On the frequency computation of functions, Algebra i Logika,
vol. 2, no. 1, pp. 2532, 1964. (in Russian).
[28] E. B. Kinber, Frequency calculations of general recursive predicates and frequency
enumerations of sets, Soviet Mathematics, vol. 13, pp. 873876, 1972.
[29] E. B. Kinber, Frequency computations in nite automata, Cybernetics and Systems
Analysis, vol. 12, no. 2, pp. 179187, 1976.
[30] H. Austinat, V. Diekert, U. Hertrampf, and H. Petersen, Regular frequency computations, Theoret. Comput. Sci., vol. 330, no. 1, pp. 1521, 2005.
[31] M. Hinrichs and G. Wechsung, Time bounded frequency computations, Inform.
Comput., vol. 139, no. 2, pp. 234257, 1997.
[32] M. Kummer, A proof of Beigel's cardinality conjecture, J. Symbolic Logic, vol. 57,
no. 2, pp. 677681, 1992.
[33] V. Harizanov, M. Kummer, and J. Owings, Frequency computations and the cardinality theorem, J. Symbolic Logic, vol. 57, no. 2, 1992.
[34] R. Beigel, W. Gasarch, and E. Kinber, Frequency computation and bounded queries,17

Theoret. Comput. Sci., vol. 163, no. 1-2, pp. 177192, 1996.
[35] J. Case, S. Kaufmann, E. B. Kinber, and M. Kummer, Learning recursive functions
from approximations, J. Comput. Syst. Sci., vol. 55, no. 1, pp. 183196, 1997.
[36] E. Kinber, C. H. Smith, M. Velauthapillai, and R. Wiehagen, On learning multiple
concepts in parallel, J. of Comput. Syst. Sci., vol. 50, no. 1, pp. 4152, 1995.
[37] R. Freivalds, Finite identication of general recursive functions by probabilistic
strategies, in Fundamentals of computation theory: FCT '79, Proceedings of the Conference on Algebraic, Arithmetic, and Categorial Methods in Computation Theory
held in Berlin/Wendisch-Rietz (GDR), Sept. 17-21, 1979 (L. Budach, ed.), (Berlin),

pp. 138145, Akademie-Verlag, 1979.
[38] A. Ambainis, Probabilistic inductive inference: a survey, Theoret. Comput. Sci.,
vol. 264, no. 1, pp. 155167, 2001.
[39] A. Ambainis, K. Apstis, R. Freivalds, and C. H. Smith, Hierarchies of probabilistic
and team FIN-learning, Theoret. Comput. Sci., vol. 261, no. 1, pp. 91117, 2001.
[40] L. Pitt, Probabilistic inductive inference, J. ACM, vol. 36, no. 2, pp. 383433, 1989.
[41] J. Pepis, Ein Verfahren der mathematischen Logik, J. Symbolic Logic, vol. 3, no. 2,
pp. 6176, 1938.
[42] L. Kalmár, On the reduction of the decision problem. First Paper. Ackermann prex,
a single binary predicate, J. Symbolic Logic, vol. 4, no. 1, pp. 19, 1939.
[43] R. Freivalds, Ultrametric automata and Turing machines, in Turing-100(A. Voronkov, ed.), vol. 10 of EPiC Series, pp. 98112, EasyChair, 2012.
[44] R. Freivalds and T. Zeugmann, Active learning of recursive functions by ultrametricalgorithms, in SOFSEM 2014: Theory and Practice of Computer Science, 40th Inter-national Conference on Current Trends in Theory and Practice of Computer Science,Nový Smokovec, Slovakia, January 26-29, 2014, Proceedings (V. Geert, B. Preneel,
B. Rovan, J. tuller, and A. M. Tjoa, eds.), vol. 8327 of Lecture Notes in Computer
Science, (Cham, Heidelberg, New York, Dordrecht, London), pp. 246257, Springer
International Publishing Switzerland, 2014.