On the Amount of Nonconstructivity in Learning
Recursive Functions
Rusin² Freivalds1? and Thomas Zeugmann2??
1

Institute of Mathematics and Computer Science, University of Latvia
Raina Bulvaris 29, Riga, LV-1459, Latvia
Rusins.Freivalds@mii.lu.lv
2
Division of Computer Science, Hokkaido University
N-14, W-9, Sapporo 060-0814, Japanthomas@ist.hokudai.ac.jp

Nonconstructive proofs are a powerful mechanism in mathematics. Furthermore, nonconstructive computations by various types ofmachines and automata have been considered by e.g., Karp and Lipton [17] and Freivalds [11]. They allow to regard more complicated algorithms from the viewpoint of much more primitive computational devices. The amount of nonconstructivity is a quantitative characterizationof the distance between types of computational devices with respect tosolving a specic problem.
In the present paper, the amount of nonconstructivity in learning ofrecursive functions is studied. Dierent learning types are compared withrespect to the amount of nonconstructivity needed to learn the wholeclass of general recursive functions. Upper and lower bounds for theamount of nonconstructivity needed are proved.
Abstract.

Keywords:

1

inductive inference, recursive functions, nonconstructivity

Introduction

Nonconstructive methods of proof in mathematics have a rather long and dramatic history. The debate was especially passionate when mathematicians tried
to overcome the crisis concerning the foundations of mathematics.
The situation changed slightly in the forties of the last century, when nonconstructive methods found their way even to discrete mathematics. In particular,Paul Erd®s used nonconstructive proofs masterly, beginning with the paper [7].
Another inuential paper in this regard was Barzdin² [2], who introduced thenotion of advice in the setting of Kolmogorov complexity of recursively enumerable sets. Karp and Lipton [17] introduced the notion of a Turing machine that
This research was performed while this author was visiting the Division of Computer Science at Hokkaido University. The research of the rst author was supported by Grant No. 09.1570 from the Latvian Council of Science and by Project
2009/0216/1DP/1.1.2.1.2/09/IPIA/VIA/004 from the European Social Fund.
??
Supported by MEXT Grant-in-Aid for Scientic Research on Priority Areas underGrant No. 21013001.
?

On the Amount of Nonconstructivity in Learning Recursive Functions

333

takes advice to understand under what circumstances nonuniform upper bounds
can be used to obtain uniform upper bounds. Damm and Holzer [6] adapted thenotion of advice for nite automata.
A further step was taken by Freivalds [11, 12], who introduced a qualitative
approach to measure the amount of nonconstructivity (or advice) in a proof.
Analyzing three examples of nonconstructive proofs led him to a notion of nonconstructive computation which can be easily used for many types of automata
and machines and which essentially coincides with Karp and Lipton's [17] notion
when applied to Turing machines.
As outlined by Freivalds [11, 12], there are several results in the theory of
inductive inference of recursive functions which suggest that the notion of nonconstructivity may be worth a deeper study in this setting, too.
In the present paper we prove several upper and lower bounds for the amountof nonconstructivity in learning classes of recursive functions. When learning recursive functions growing initial segments (f (0), . . . , f (n)) are fed to the learningalgorithm, henceforth called strategy. For each initial segment 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 isa numbering. The interpretation of the hypothesis in is that the strategy conjectures program in in the numbering ψ to compute the target function f . 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 [14].
Many variations of this model have been studied (cf., e.g., [4, 10, 15, 25], andthe references therein).
For many of these variations it was shown that the class R of all recursivefunctions is not learnable. Several attempts have been undertaken to classify thediculty of learning the class R. Adleman and Blum [1] showed the degree of
unsolvability of the problem to learn the class R to be strictly less than the degreeof the halting problem. A further approach was to characterize the diculty oflearning classes of recursive functions by using oracles (cf., e.g., [5, 19]).
We introduce a new measure, i.e., the amount of nonconstructivity needed
to learn the class R. That is, the strategy receives as a second input a bitstringof nite length which we call help-word. If the help-word is correct, the strategy
learns in the desired sense. Since there are innitely many functions to learn, aparameterization is necessary, i.e., we allow for every n a possibly dierent helpword and we require the strategy to learn every recursive function contained in{ψ0 , . . . , ψn } with respect to the numbering ψ (cf. Denition 4). The diculty of
the learning problem is then measured by the length of the help-words needed,
i.e., in terms of the growth rate of a function d bounding this length.
As in previous approaches, the help-word does not just provide an answer
to the learning problem. There is still much work to be done by the strategy.
The usefulness of this approach is nicely reected by our results which show that334

R. Freivalds and T. Zeugmann

the function d may vary from arbitrarily slow growing (for learning in the limit)
to n + 1 (for minimal identication).

2

Preliminaries

Unspecied notations follow Rogers [22]. In addition to or in contrast with [22]we use the following. Let N = {0, 1, 2, . . . } be the set of all natural numbers, andlet N+ = N\{0}. We use N∗ for the set of all nite sequences of natural numbers.
By |S| and ℘(S) we denote the 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.
By T we denote the set of all total functions of one variable over N. The setof all partial recursive and recursive functions of one respectively two variables
over N is denoted by P, R, P 2 , R2 , respectively. Let f ∈ P , then we use dom(f )for 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 , i.e., Val(f ) = {f (x) | x ∈ dom(f )}.
A function f ∈ P is said to be strictly monotonic provided for all x, y ∈ Nwith x < y we have, if both f (x) and f (y) are dened then f (x) < f (y). By Rmon
we denote the set of all strictly monotonic recursive functions.
Any function ψ ∈ P 2 is called a numbering. Let ψ ∈ P 2 , then we write ψiinstead of λx.ψ(i, x) and set Pψ = {ψi | i ∈ N} as well as Rψ = Pψ ∩ R.
Consequently, if f ∈ Pψ , then there is a number i such that f = ψi . If f ∈ P
and i ∈ N are such that ψi = f , then i is called a ψ program for f . Let ψ be any
numbering, and 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 we use minψ f to denote the least number i such that ψi = f .
A numbering ϕ ∈ P 2 is called a Gödel numbering (cf. Rogers [22]) i Pϕ = P ,and for any 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.
By N UM = {U | (∃ψ ∈ R2 ) [U ⊆ Pψ ]} we denote the family of all subsets
of all recursively enumerable classes of recursive functions. Let N UM! = {U |(∃ψ ∈ R2 ) [U = Pψ ]} denote the family of all recursively enumerable classes ofrecursive functions. The elements of N UM! are referred to as indexed families.
We call (ϕ, Φ) a measure of computational complexity (cf. [20]) if ϕ ∈ Gödand Φ ∈ P 2 satises Blum's [3] axioms. That is, (1) dom(ϕi ) = dom(Φi ) for alli ∈ N and (2) the predicate  Φi (x) = y  is uniformly recursive for all i, x, y ∈ N.
Let h. . .i be any recursive encoding of N∗ onto N. We write f n instead ofh(f (0), . . . , f (n))i, for all n ∈ N, 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, (jn )n∈N is said to nitely converge to the number j if it converges in
the limit to j and for all n ∈ N, jn = jn+1 implies jk = j for all k ≥ n.

Denition 1 (Gold [13, 14]). Let U ⊆ R and let ψ ∈ P 2 . The class U is said

to be learnable in the limit with respect to ψ if there is a strategy S ∈ P suchthat for each function f ∈ U ,On the Amount of Nonconstructivity in Learning Recursive Functions

335(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 w.r.t. ψ by S , we write U ∈ LIM
S ψ (S). Let LIMψ ={U | U is learnable in the limit w.r.t. ψ}, and let LIM = ψ∈P 2 LIMψ .
In the following modication of Denition 1 we require the strategy to converge to minψ f instead of converging to any program for the target function f .

Denition 2 (Freivalds [9], Kinber [18]). Let U ⊆ R and let ψ ∈ P 2 . The

class U is said to be ψ -minimal learnable in the limit with respect to ψ if there
is a strategy S ∈ P 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 converges to minψ f .

If U is ψ -minimal learnable in the limit w.r.t. ψ by a strategy S , we write
U ∈ MIN ψ (S). Furthermore, let MIN
S ψ = {U | U is ψ -minimal learnable in
the limit w.r.t. ψ}, and let MIN = ψ∈P 2 MIN ψ .
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 haslearned its input function. That is, we replace the requirement that the sequenceof all created hypotheses has to converge by has to converge nitely.

Denition 3 (Gold [14], Trakhtenbrot and Barzdin [23]). Let U ⊆ R andlet ψ ∈ P 2 . The class U is said to be nitely learnable with respect to ψ if there
is a strategy S ∈ P such that for any function f ∈ U ,(1) for all n ∈ N, S(f n ) is dened,
(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 w.r.t. ψ by a strategy S , we write U ∈ FIN ψ (S). The
learning types FIN ψ and FIN are dened analogously to the above.
Of course, we can also combine ψ -minimal learnability and nite identication resulting in the learning types MIN -FIN ψ and MIN -FIN .
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 helpwords are assumed to be encoded in binary. So, for such strategies we writeS(f n , w) to denote the program output by S . Then, for all the inference types
dened above, we say that S nonconstructively identies f with the help-word w
provided the sequence (S(f n , w))n∈N (nitely) converges to a number j such thatϕj = f (for LIM and FIN ) and j = minψ f (for MIN ), respectively.

Denition 4. Let ψ ∈ P 2 , let U ⊆ R, and d ∈ R. A strategy S ∈ P 2 infers U

with nonconstructivity d(n) in the limit with respect to ψ , if for each n ∈ N there
is a help-word of length at most d(n) such that for every f ∈ U ∩{ψ0 , ψ1 , . . . , ψn }the sequence (S(f n , w))n∈N converges to a program i satisfying ψi = f .

336

R. Freivalds and T. Zeugmann

Nonconstructive nite and minimal inference is dened in analogue to the above.
Looking at Denition 4 as well as at the denition of nonconstructive niteand minimal inference, it should be noted that the strategy may need to know
either an appropriate upper bound for n or even the precise value of n in order
to exploit the fact that the target function is from f ∈ U ∩ {ψ0 , ψ1 , . . . , ψn }.
To simplify notation in several theorems and proofs given below, we makethe convention that logarithmic function is to the base 2 and that it is replacedby its integer valued counterpart blog nc + 1.

3

Results

Already Gold [13] showed that R ∈/ LIM. So, we start our investigations by
asking for the amount of nonconstructivity needed to identify the set R of all
recursive functions in the limit with respect to any Gödel numbering ϕ.
Using an idea from Freivald and Wiehagen [8], we prove that the neededamount of nonconstructivity is surprisingly small. To show this result, for every
function f ∈ Rmon we dene its inverse finv as follows: finv (n) = µy[f (y) ≥ n]
for all n ∈ N. Recall that Val(f ) is recursive for all f ∈ Rmon . Thus, for allf ∈ Rmon we can conclude that finv (n) ∈ R.

Theorem 1. Let ϕ ∈ Göd be arbitrarily xed, and let d ∈ Rmon be any function.
Then there is a strategy S ∈ P 2 such that the class R can be identied with
nonconstructivity log dinv (n) in the limit with respect to ϕ.

Proof. Let ϕ ∈ Göd be arbitrarily xed. Without loss of generality, we can also
assume any complexity function Φ ∈ P 2 such that (ϕ, Φ) is a complexity measure.
The key idea of the proof is that, in order to learn any function from R,
it suces to have an upper bound for minϕ f . So, assuming any help-word wof length precisely log dinv (n), the strategy S uses the length of the help-word
w to create a bitstring that contains only 1s and has the same length as thehelp word. This bitstring is interpreted in the usual way as a natural number k .
By construction, we then have k ≥ dinv (n). Furthermore, since d ∈ Rmon , wedirectly obtain that d(k) ≥ d(dinv (n)) ≥ n. Consequently, the strategy S uses k
to computeu∗ =df d(k) ,and by construction, we have u∗ ≥ n.
Assume any function f ∈ R∩{ϕ0 , ϕ1 , . . . , ϕn }, and let f m and w be the input
to the strategy S . Then, S initializes the index set Iinit to be Iinit = {0, . . . , u∗ }and checks whether or not Φi (x) ≤ m for every i ∈ Iinit and 0 ≤ x ≤ m. For all iand x that passed this test successfully, S checks whether or not ϕi (x) = f (x).
If this is not the case, i is removed from Iinit . Let Im be the resulting index set.
The strategy uses the amalgamation technique (cf. [4, 24]). That is, let amal
be a recursive function mapping any nite set I of ϕ-programs to a ϕ-program
such that for any x ∈ N, ϕamal(I) (x) is dened by running ϕi (x) for every i ∈ I
in parallel and taking the rst value obtained, if any.

On the Amount of Nonconstructivity in Learning Recursive Functions

337

So, the output of S(f m , w) is amal(Im ).
We have to show that the sequence (amal(Im ))m∈N converges to a ϕ-programfor f . By construction we know that Iinit contains at least one ϕ-program for f .
This program and any other ϕ-program computing a subfunction of f can neverbe removed from Iinit . But if a ϕ-program j from Iinit does not compute a subfunction of f , then there must be an x such that ϕj (x) ↓ =6 f (x). So, as soon asm ≥ max{x, Φj (x)}, the program j is removed from Iinit . Since Iinit is nite,
there must be an m∗ such that Im∗ contains only ϕ-programs for f or a subfunction of f . We conclude that amal(Im∗ ) is a ϕ-programs for f . Furthermore,tuI` = Im∗ for all ` ≥ m∗ , and thus the strategy S learns f in the limit.
So there is no smallest amount of nonconstructivity needed to learn R in thelimit. But the amount of nonconstructivity cannot be zero, since then we would
have R ∈ LIM. One can dene a total function t ∈ T such that t(n) ≥ d(n) forall d ∈ Rmon and all but nitely many n. Consequently, log tinv is then a lower
bound for the amount of nonconstructivity needed to learn R in the limit whenusing the algorithm from the proof of Theorem 1.
We continue by asking what amount of nonconstructivity is needed to obtain ϕ-minimal identication in the limit of the class R. Now, the situation is
intuitively more complex, since LIMϕ \ MIN ϕ 6= ∅ for every ϕ ∈ Göd. Interestingly, there are even Gödel numberings ϕ such that MIN ϕ contains onlyclasses of nite cardinality (cf. Freivalds [10]). On the other hand, the sucientamount of nonconstructivity given in Theorem 2 does not depend on the Gödel
numbering. Theorem 2 below is not the best possible and we shall improve it
below, but it shows an easy way to achieve ϕ-minimal learning of R in the limit.

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

such that the class R can be ϕ-minimal identied with nonconstructivity n + 1
in the limit with respect to ϕ.
Proof. Let ϕ ∈ Göd be arbitrarily xed, and let n ∈ N. The help-word w is a
bitstring b of length n + 1 dened as follows. If ϕi ∈ R, then the ith entry of b
is 1, and 0 otherwise. So, the length of w allows the strategy to compute n.
Assume any function f ∈ R∩{ϕ0 , ϕ1 , . . . , ϕn }, and let f m and w be the input
to S . Then S only considers those functions ϕi , 0 ≤ i ≤ n, for which the ith entry
in the help-word is 1. Since all these remaining functions are total, the strategymsearches for the least index j among these functions for which ϕm
j = f . That is,it essentially uses the identication by enumeration principle (cf. Gold [14]). ut
The proof of Theorem 2 was easy which may be an indication that a smaller
amount of nonconstructivity may suce. So far we could not show a lower boundfor the amount of nonconstructivity needed to achieve ϕ-minimal inference in thelimit of R. As Theorem 4 shows, we can achieve a much better result when using
nonconstructivity n + 1, again an indication that we used a too great amount of
nonconstructivity in Theorem 2. And indeed, we can do exponentially better.

338

R. Freivalds and T. Zeugmann

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

such that the class R can be ϕ-minimal identied with nonconstructivity 2 · log nin the limit with respect to ϕ.
Proof. The key observation for the proof is that it suces to know the number ofrecursive functions in the set {ϕ0 , . . . , ϕn }. To use this information appropriately,the rst half of the help-word w is the binary encoding of n and the second halfof w provides the number, say k , of recursive functions in the set {ϕ0 , . . . , ϕn }.
This number is written in binary but leading zeros are added to ensure that bothparts of w have the same length. Thus 2 · log n many bits suce to represent w.
Assume any function f ∈ R∩{ϕ0 , ϕ1 , . . . , ϕn }, and let f m and w be the input
to the strategy S . Then S , by dovetailing its computations, rst tries to compute
ϕi (0), . . . , ϕi (m) for all 0 ≤ i ≤ n until it nds the rst k programs i1 , . . . , ik suchthat ϕi (0), . . . , ϕi (m) turn out to be dened for every i ∈ {i1 , . . . , ik }. Once S
has found these programs i1 , . . . , ik , it outputs the least program i ∈ {i1 , . . . , ik }mfor which it veries ϕmprovided there is such a program, and m otherwise.
i =f
By construction, there are n + 1 − k many programs j ∈ {0, . . . , n} such thatϕj ∈ P \ R. For each of these programs j there is a least yj such that ϕj (yj ) ↑ .
Let ymax be the maximum of all these yj . Hence, as soon as m ≥ ymax , thestrategy S must nd precisely the programs i1 , . . . , ik such that ϕi ∈ R for alli ∈ {i1 , . . . , ik }. By assumption, the target function f possesses a program i with0 ≤ i ≤ n, and so for all m ≥ ymax , the strategy must output minϕ f .
tu
Next we provide the theorem already mentioned above which shows that with
nonconstructivity n + 1 a much stronger result is possible.

Theorem 4. 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 nonconstructivityn + 1 with respect to ϕ.
Proof. Let ϕ ∈ Göd, and let n ∈ N. The help-word w is a bitstring b of lengthn + 1 dened as follows. If ϕi ∈ R and ϕi 6= ϕj for all 0 ≤ j < i, then the ith
entry of b is 1, and 0 otherwise. So, the length of the help-word directly allows
the strategy to compute n. Note that now the help-word allows for implicitly
having a one-to-one enumeration for the functions f ∈ R ∩ {ϕ0 , . . . , ϕn }.
Assume any function f ∈ R ∩ {ϕ0 , ϕ1 , . . . , ϕn }, and let f m and w be theinput to S . Then S only considers those functions ϕi , 0 ≤ i ≤ n, for which
the ith entry in the help-word is 1. For all these i, the strategy computes ϕmiand checks whether or not they are pairwise dierent. As long as this is not thecase, the strategy outputs m. If all these ϕm
i are pairwise dierent, then thestrategy outputs the i for which it could verify f m = ϕmi .
By construction, it is obvious that S nitely converges to minϕ f .
tu
So far we could not prove the amount of nonconstructivity given in Theorem 4
to be the best possible. We thus look at the case, where we have to learn anindexed family U of recursive functions. Note that for every indexed family U
and any of its numberings ψ ∈ R2 we have U ∈ MIN ψ (cf. Gold [14]). InOn the Amount of Nonconstructivity in Learning Recursive Functions

339

contrast, N UM # FIN (see e.g., [25] and the references therein). So, it is only
natural to ask for the amount of nonconstructivity needed to nitely learn ψ minimal programs. The answer is provided by our theorems below.

Theorem 5. Let U be any indexed family, and let ψ ∈ R2 be any numberingfor 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 ψ .

Proof. The key observation is that it suces to know the number k of distinct
functions in {ψ0 , . . . , ψn }. The help-word w is divided in two halves, where therst half is the binary encoding of n and the second half encodes k in binary(again including leading zeros). So 2 · log n many bits suce for representing w.
On input f m and w the strategy S computes, by dovetailing its computations,ψi (x) for all i ∈ {0, . . . , n} and x = 0, 1, 2, . . . until it has veried that there areexactly k dierent functions. Let i1 , . . . , ik be the least indices of these k dierent
functions. Next, it checks whether or not there is precisely one i ∈ {i1 , . . . , ik }such that f m = ψim . If this is the case, S outputs this i. Otherwise, it outputs m.
tu
By construction, it is obvious that S nitely converges to minψ f .
Next we show that the amount of nonconstructivity given in Theorem 5
cannot be substantially reduced.

Theorem 6. There is an indexed family U and a numbering ψ ∈ R2 for itsuch that 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.
Proof. We construct the indexed family U by dening the numbering ψ ∈ R2
for it. For this purpose, we use the following pairing function c : N × N → N,
where c(x, y) = 2x (2y + 1) − 1. Note that this pairing function is a bijection. It
may be traced back to Pepis [21] and Kalmár [16]. Furthermore, we interpret
every function in P 2 as a strategy and obtain thus an eective enumeration
S0 , S1 , S2 , . . . of all possible strategies. Below, for ` ∈ N, we use the shortcut i`+1
to denote the encoding f ` of the initial segment of the function f for whichf (z) = i for all i = 0, . . . , `.
For every i ∈ N we dene two functions ψ2i and ψ2i+1 as follows. Let x and y
be the uniquely determined numbers such that i = c(x, y). Now, we successively
dene for k = 1, 2, 3, . . . the functions values ψ2i (k − 1) = ψ2i+1 (k − 1) = i
and input ik and y to the strategy Sx until we nd the smallest k such that thefollowing Conditions (A) and (B) are satised.
(A) There is an ` < k such that each of the values Sx (i, y), . . . , Sx (i`+1 , y) turns
out to be computable in at most k steps.
(B) Sx (i, y) 6= Sx (i2 , y) 6= · · · 6= Sx (i` , y) = Sx (i`+1 , y).
If Conditions (A) and (B) never turn out to be satised then the function valuesψ2i (k) and ψ2i+1 (k) are dened for all k ∈ N, and thus ψ2i , ψ2i+1 ∈ R.
On the other hand, if Conditions (A) and (B) turn out to be satised then
Condition (B) implies that the sequence Sx (i, y), . . . , Sx (i`+1 , y) tends to converge nitely. That is, it either converges nitely or it cannot converge nitely
at all. Now, we continue to dene the functions ψ2i and ψ2i+1 as follows.

340

R. Freivalds and T. Zeugmann(C) If Sx (i` , y) = 2i, then we dene ψ2i (z) = i + k + z for all z ≥ k .
Furthermore, we set ψ2i+1 (z) = i for all z ≥ k .
(D) If Sx (i` , y) = 2i + 1, then we dene ψ2i+1 (z) = i + k + z for all z ≥ k .
Furthermore, we set ψ2i (z) = i for all z ≥ k .
(E) If Sx (i` , y) ∈/ {2i, 2i + 1}, then we dene ψ2i (z) = ψ2i+1 (z) = z for all z ≥ k .
So we have ψ2i , ψ2i+1 ∈ R, and thus, ψ ∈ R2 . Finally, we set U = Rψ .
We show that there is no strategy S ∈ P 2 that ψ -minimal nitely infers U
with nonconstructivity c·log n with respect to ψ , where c ∈ (0, 1) is any constant.
Suppose the converse, i.e., there is a strategy S ∈ P 2 that ψ -minimal nitely
infers U with nonconstructivity c · log n with respect to ψ . Then there must bea v ∈ N such that S = Sv in our enumeration S0 , S1 , S2 , . . . of all possible strategies. Let d be the function from Denition 4. Furthermore, for every n ∈ N andevery f ∈ {ψ0 , . . . , ψn } there has to be a help-word w of length at most d(n) anddepending only on n such that the sequence (Sv (f m , w))m∈N nitely converges
to the minimal ψ -program of f .
By assumption, there is a c ∈ (0, 1) such that d(n) ≤ c · log n. We x this cand conclude that for n large enough we haved(n) > 1 and

1−c
2 + (v + 1)
>
.
2
log n

(1)

Now, we obtain successivelyc+1
2
2c + 1 − c
1 >2c · log n 1 − c
+
1 >
log n
2
d(n)
2 + (v + 1)
1 >+,since c · log n ≥ d(n) and by (1)
log n
log n
log n > d(n) + 2 + (v + 1)
log n − log 2v+1 > d(n) + 2
nlog v+1 > d(n) + 22n> 2d(n)+2
2v+1
n+2> 2 · 2d(n) + 1
2v+1
n+2> 2w + 1 , since 2d(n) ≥ w
2v+1n> 2v (2w + 1) − 12n> c(v, w) .
2
Now, let i = c(v, w) and consider the functions ψ2i and ψ2i+1 . By our choiceof n, these functions must be among the functions {ψ0 , . . . , ψn }.
1 >On the Amount of Nonconstructivity in Learning Recursive Functions

341

Let ` ∈ N+ be the least number such that Sv on two successive inputs outputs
the same hypothesis, i.e., Sv (i, w) 6= · · · 6= Sv (i` , w) = Sv (i`+1 , w). Such an ` has
to exist, since otherwise Sv can neither nitely identify ψ2i nor ψ2i+1 .
If Sv (i` , w) ∈/ {2i, 2i + 1} we are already done, since ψ2i and ψ2i+1 are theonly functions from U having an initial segment where all values are equal to i.
Finally, if Sv (i` , w) ∈ {2i, 2i+1} then by construction (cf. Condition (C) and (D),respectively), we have ψ2i (z) = ψ2i+1 (z) for all z = 0, . . . , ` but ψ2i 6= ψ2i+1 . So
the strategy Sv fails to nitely learn either function ψ2i or ψ2i+1 .
tu
As the proof of Theorem 6 shows, the failure to ψ -minimal nitely identify
the indexed family U with respect to the numbering ψ with nonconstructivity
c · log n, for c ∈ (0, 1), is caused by the requirement to nitely identify thefunctions from U . Thus, we directly obtain the following corollary.

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

4

Conclusions and Open Problems

We have presented a model for the inductive inference of recursive functions thatincorporates a certain amount of nonconstructivity. In our model, the amountof nonconstructivity needed to solve the learning problems considered has beenused as a quantitative characterization of their diculty.
We studied the problem of learning the whole class R under various postulates. These postulates range from learning in the limit to nite and minimal
identication. As far as learning in the limit is concerned, the amount of nonconstructivity needed to learn R can be very small and there is no smallest amountthat can be described in a computable way (cf. Theorem 1).
This result is nicely contrasted by the fact that we needed nonconstructivity
2·log n to ϕ-minimal identify the class R in the limit and nonconstructivity n+1
to ϕ-minimal nitely identify R (cf. Theorems 3 and 4, respectively). That is,each additional postulate exponentially increased the amount of nonconstructivity needed. It remains, however, open whether or not these results can be
improved.
Furthermore, we investigated the amount of nonconstructivity needed to ϕminimal nitely identify any indexed family of recursive functions. In this setting we obtained an upper bound of 2 · log n for the amount of nonconstructivity
needed and showed that this amount cannot be substantially improved (cf. Theorems 5 and 6).
Unfortunately, so far we could only show the lower bound presented in Theorem 6. Proving lower bounds for the other cases studied in this paper remains
open and should be addressed in the future.

Acknowledgments We would like to thank the anonymous referees for theircareful reading and their valuable comments.

342

R. Freivalds and T. Zeugmann

References[1] Adleman, L.M., Blum, M.: Inductive inference and unsolvability. The Journal of
Symbolic Logic 56(3), 891900 (1991)[2] Barzdin², J.M.: Complexity of programs to determine whether natural numbers
not greater than n belong to a recursively enumerable set. Soviet Mathematics
Doklady 9, 12511254 (1968)[3] Blum, M.: A machine independent theory of the complexity of recursive functions.
Journal of the ACM 14(2), 322336 (1967)[4] Case, J., Smith, C.: Comparison of identication criteria for machine inductive
inference. Theoretical Computer Science 25(2), 193220 (1983)[5] Cholak, P., Downey, R., Fortnow, L., Gasarch, W., Kinber, E., Kummer, M.,
Kurtz, S., Slaman, T.A.: Degrees of inferability. In: Proc. 5th Annual ACM Workshop on Computational Learning Theory. pp. 180192. ACM Press, New York
(1992)[6] Damm, C., Holzer, M.: Automata that take advice. In: Mathematical Foundationsof Computer Science 1995, 20th International Symposium, MFCS '95, Prague,
Czech Republic, August 28 - September 1, 1995, Proceedings. Lecture Notes in
Computer Science, vol. 969, pp. 149158. Springer, Berlin (1995)[7] Erd®s, P.: Some remarks on the theory of graphs. Bulletin of the American Mathematical Society 53(4), 292294 (1947)[8] Freivald, R.V., Wiehagen, R.: Inductive inference with additional information.
Elektronische Informationsverarbeitung und Kybernetik 15(4), 179185 (1979)[9] Freivald, R.: Minimal gödel numbers and their identication in the limit. In:
Be£vá°, J. (ed.) Mathematical Foundations of Computer Science 1975, 4th Symposium, Mariánské Lázn¥, September 1-5, 1975. Lecture Notes in Computer Science,
vol. 32, pp. 219225. Springer-Verlag, Berlin (1975)[10] Freivalds, R.: Inductive inference of recursive functions: Qualitative theory. In:
Barzdin², J., Bjørner, D. (eds.) Baltic Computer Science, Lecture Notes in Computer Science, vol. 502, pp. 77110. Springer, Berlin (1991)[11] Freivalds, R.: Amount of nonconstructivity in nite automata. In: Maneth, S.
(ed.) Implementation and Application of Automata, 14th International Conference, CIAA 2009, Sydney, Australia, July 14-17, 2009. Proceedings. Lecture Notes
in Computer Science, vol. 5642, pp. 227236. Springer, Berlin (2009)[12] Freivalds, R.: Amount of nonconstructivity in deterministic nite automata. Theoretical Computer Science 411(38-39), 34363443 (2010)[13] Gold, E.M.: Limiting recursion. The Journal of Symbolic Logic 30, 2848 (1965)[14] Gold, E.M.: Language identication in the limit. Inform. Control 10(5), 447474(1967)[15] Jain, S., Osherson, D., Royer, J.S., Sharma, A.: Systems that Learn: An Introduction to Learning Theory, second edition. MIT Press, Cambridge, Massachusetts(1999)[16] Kalmár, L.: On the reduction of the decision problem. First Paper. Ackermannprex, a single binary predicate. The Journal of Symbolic Logic 4(1), 19 (1939)[17] Karp, R.M., Lipton, R.J.: Turing machines that take advice. L' Enseignement
Mathématique 28, 191209 (1982)[18] Kinber, E.B.: O predel~nom sinteze poqti minimal~nyh gedelevskih nomerov. In: Barzdin², J. (ed.) Teori Algoritmov i Programm, vol. I, pp. 212223. Latvian State University (1974)

On the Amount of Nonconstructivity in Learning Recursive Functions

343[19] Kummer, M., Stephan, F.: On the structure of the degrees of inferability. Journalof Computer and System Sciences 52(2), 214238 (1996)[20] Landweber, L.H., Robertson, E.L.: Recursive properties of abstract complexity
classes. Journal of the ACM 19(2), 296308 (1972)[21] Pepis, J.: Ein Verfahren der mathematischen Logik. The Journal of Symbolic
Logic 3(2), 6176 (1938)[22] Rogers, Jr., H.: Theory of Recursive Functions and Eective Computability.
McGraw-Hill (1967), reprinted, MIT Press 1987.
[23] Trakhtenbrot, B.A., Barzdin, Y.M.: Finite Automata, Behavior and Synthesis.
North Holland, Amsterdam (1973)[24] Wiehagen, R.: Zur Theorie der Algorithmischen Erkennung. Dissertation B,
Humboldt-Universität zu Berlin (1978)[25] Zeugmann, T., Zilles, S.: Learning recursive functions: A survey. Theoretical Computer Science 397(1-3), 456 (2008)