TCS -TR-A-11-49

TCS Technical Report

On the Amount of Nonconstructivity in the Inductive
Inference of Recursive Functions

byRūsiņš Freivalds and Thomas Zeugmann

Division of Computer Science
Report Series A
December 17, 2010

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

thomas@ist.hokudai.ac.jp

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

On the Amount of Nonconstructivity in the
Inductive Inference of Recursive Functions
Rūsiņš Freivalds∗

Thomas Zeugmann†

Institute of Mathematics and Computer Science

Division of Computer Science

University of Latvia

Hokkaido University

Raiņa Bulvāris 29

N-14, W-9

Riga, LV-1459, Latvia

Sapporo 060-0814, Japan

Rusins.Freivalds@mii.lu.lv

thomas@ist.hokudai.ac.jp

Abstract
Nonconstructive proofs are a powerful mechanism in mathematics. Furthermore, nonconstructive computations by various types of machines and automata
have been considered by e.g., Karp and Lipton [15] and Freivalds [10]. They
allow to regard more complicated algorithms from the viewpoint of much moreprimitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices
with respect to solving a specific problem.
In the present paper, the amount of nonconstructivity in learning of recursivefunctions is studied. Different learning types are compared with respect to theamount of nonconstructivity needed to learn the whole class of general recursivefunctions. Upper and lower bounds for the amount of nonconstructivity needed
are proved.
Keywords: inductive inference, learning, recursive functions, nonconstructivity, advice

1. 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.
∗

This research was performed while this author was visiting the Division of Computer Science at
Hokkaido University. The research of the first author was supported by Grant No. 09.1570 from theLatvian Council of Science and by Project 2009/0216/1DP/1.1.2.1.2/09/IPIA/VIA/004 from theEuropean Social Fund.
†
Supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas under Grant No.
21013001.

1

2

Rūsiņš Freivalds and Thomas Zeugmann

However, the situation changed slightly in the forties of the last century, whennonconstructive methods found their way even to discrete mathematics. In particular,Paul Erdős used nonconstructive proofs masterly, beginning with the paper [6].
Another influential paper in this regard was Bārzdiņš [2], who introduced thenotion of advice in the setting of Kolmogorov complexity of recursively enumerable
sets. Karp and Lipton [15] introduced the notion of a Turing machine that takes
advice to understand under what circumstances nonuniform upper bounds can beused to obtain uniform upper bounds.
A further step was taken by Freivalds [10], 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 [15] notion when applied to Turing machines.
As outlined by Freivalds [10], 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 amount of
nonconstructivity in learning classes of recursive functions. When learning recursivefunctions growing initial segments (f (0), . . . , f (n)) are fed to the learning algorithm,
henceforth called strategy. For each initial segment the strategy has then to computea hypothesis in which is a natural number. These hypotheses are interpreted withrespect to a suitably chosen hypothesis space ψ which is a numbering. The interpretation of the hypothesis in is that the strategy is conjecturing program in in thenumbering ψ to compute the target function f . One requires the sequence (in )n∈Nof all computed hypotheses to converge to a program correctly computing the targetfunction 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 [12]. Many variations of this model have been studied (cf., e.g.,[4, 9, 23], and the references therein).
On the one hand, for many of these variations it was shown that the class of all
recursive functions is not learnable. Also, several attempts have been undertaken
to classify the difficulty of learning the class of all recursive functions. Adleman
and Blum [1] showed the degree of unsolvability of the problem to learn all recursivefunctions to be strictly less than the degree of the halting problem. A further approach
was to characterize the difficulty of learning classes of recursive functions by using
oracles (cf., e.g., [5, 17]).
Our goal is to introduce a different measure, i.e., the amount of nonconstructivity
needed to learn all recursive functions. That is, the strategy receives as a second
input a bitstring of finite length which we call help-word. If the help-word is correct,
the strategy learns in the desired sense. Since there are infinitely many functions to

On the Amount of Nonconstructivity in the Inductive Inference of Recursive Functions

3

learn, a parameterization is necessary, i.e., we allow for every n a possibly different
help-word and we require the strategy to learn every recursive function contained in{ψ0 , . . . , ψn } with respect to the numbering ψ (cf. Definition 4). The difficulty of thelearning problem is then measured by the length of the help-words needed, i.e., interms of the growth rate of function d bounding this length.
As in previous approaches, the help-word does not just provide an answer to thelearning problem. There is still much work to be done by the strategy. The usefulnessof this approach is nicely reflected by our results which show that the function d mayvary from arbitrarily slow growing (for learning in the limit) to n + 1 (for minimal
identification).

2. Preliminaries
Any unspecified notations follow Rogers [20]. In addition to or in contrast with
Rogers [20] we use the following. By N = {0, 1, 2, . . . } we denote the set of all natural
numbers. We set N+ = N \ {0}. The set of all finite sequences of natural numbers isdenoted by N∗ .
The cardinality of a set S is denoted by |S|. We write ℘(S) for the power set ofset S. Let ∅, ∈, ⊂, ⊆, ⊃, ⊇, and # denote the empty set, element of, proper subset,
subset, proper superset, superset, and incomparability of sets, respectively.
By P and T we denote the set of all partial and total functions of one variable
over N. The set of all partial recursive and recursive functions of one respectively twovariables over N is denoted by P, R, P 2 , and R2 , respectively.
For any function f ∈ P we use dom(f ) to denote the domain of the function f , i.e.,dom(f ) = {x | x ∈ N, f (x) is defined}. Additionally, by Val(f ) we denote the rangeof f , i.e., Val(f ) = {f (x) | x ∈ dom(f )}. We use R{0,1} to denote the set of all f ∈ Rsatisfying Val(f ) ⊆ {0, 1}. We refer to R{0,1} as to the set of recursive predicates.
A function f ∈ P is said to be strictly monotonic provided for all x, y ∈ N withx < y we have, if both f (x) and f (y) are defined then f (x) < f (y). By Rmon wedenote the set of all strictly monotonic recursive functions.
Any function ψ ∈ P 2 is called a numbering. Moreover, 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 defined (abbr. ψi (x) ↓ ) then we also say that ψi (x) converges. Otherwise,
ψi (x) is said to diverge (abbr. ψi (x) ↑ ). Let ψ ∈ P 2 be any numbering and let f ∈ P;
then we use minψ f to denote the least number i such that ψi = f . We refer to minψ f
as a ψ-minimal program of f .
A numbering ϕ ∈ P 2 is called a Gödel numbering (cf. Rogers [20]) iff Pϕ = P, andfor any numbering ψ ∈ P 2 , there is a compiler c ∈ R such that ψi = ϕc(i) for all i ∈ N.
Göd denotes the set of all Gödel numberings.

4

Rūsiņš Freivalds and Thomas Zeugmann

Furthermore, let N UM = {U | (∃ψ ∈ R2 ) [U ⊆ Pψ ]} denote the family of all
subsets of all recursively enumerable classes of recursive functions and let N UM! ={U | (∃ψ ∈ R2 ) [U = Pψ ]} denote the family of all recursively enumerable classes ofrecursive functions. Note that the elements of N UM! are also often referred to asindexed families.
Following [18] we call any pair (ϕ, Φ) a measure of computational complexity provided ϕ is a Gödel numbering of P and Φ ∈ P 2 satisfies Blum’s [3] axioms. That is,(1) dom(ϕi ) = dom(Φi ) for all i ∈ N and (2) the predicate “Φi (x) = y” is uniformly
recursive for all i, x, y ∈ N.
Furthermore, using a fixed encoding h. . .i of N∗ onto N we write f n instead ofh(f (0), . . . , f (n))i, for any n ∈ N, f ∈ R. A sequence (jn )n∈N of natural numbers is
said to converge to the number j iff all but finitely many numbers of it are equal to j.
A sequence (jn )n∈N of natural numbers is said to finitely converge to the number j iff
it converges in the limit to j and for all n ∈ N, jn = jn+1 implies jk = j for all k ≥ n.
Definition 1 (Gold [11, 12]). 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 such thatfor each function f ∈ U,(1) for all n ∈ N, S(f n ) is defined,(2) there is a j ∈ N such that ψj = f and the sequence (S(f n ))n∈N converges to j.
If U is learnable in the limit with respect to ψ by a strategy S, we write U ∈ LIMψ (S).
We set LIMψ = {U | U is learnable in the limit with respect to ψ}. Finally, letS
LIM = ψ∈P 2 LIMψ .
Freivalds [8] and Kinber [16] introduced the following modification of Definition 1,
where instead of converging to any program for the target function f , the strategy isrequired to converge to minψ f .
Definition 2 (Freivalds [8], Kinber [16]). 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 defined,(2) the sequence (S(f n ))n∈N converges to minψ f .
If U is ψ-minimal learnable in the limit with respect to ψ by a strategy S, we write
U ∈ MIN ψ (S). Furthermore, let MIN ψ = {U | U is ψ-minimal learnable inS
the limit w.r.t. ψ}, and let MIN = ψ∈P 2 MIN ψ .
Note that in general it is not decidable whether or not a strategy has alreadyconverged when successively fed some graph of a function. With the next definition
we consider a special case where it has to be decidable whether or not a strategy

On the Amount of Nonconstructivity in the Inductive Inference of Recursive Functions

5

has already learned its input function. That is, we replace the requirement that thesequence of all created hypotheses “has to converge” by “has to converge finitely.” This
leads to finite identification which has been investigated intensively in the literature(cf., e.g., Jain, Osherson, Royer, and Sharma [13] and Zilles and Zeugmann [23] andthe references given therein).
Definition 3 (Gold [12], Trakhtenbrot and Barzdin [21]). Let U ⊆ R andlet ψ ∈ P 2 . The class U is said to be finitely 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 defined,(2) there is a j ∈ N such that ψj = f and the sequence (S(f n ))n∈N finitely converges
to j.
If the class U is finitely learnable with respect to ψ by a strategy S then we write
U ∈ FIN ψ (S). Let FIN ψ = {U | U is finitely learnable with respect to ψ}, andS
let FIN = ψ∈P 2 FIN ψ .
Of course, we can also combine ψ-minimal learnability and finite identification.
That is, now the strategy has to converge finitely to a ψ-minimal program of thetarget function. We denote the resulting learning type by MIN -FIN ψ .
The strategies used for nonconstructive inductive inference take as input not only
the encoded graph of a recursive function but also a help-word. The help-words are
assumed to be encoded in binary. So, for such strategies we write S(f n , w) to denotethe program output by S, where w is the help-word. Then, for all the inference
types defined above, we say that S nonconstructively identifies f with the help-word
w provided the sequence (S(f n , w))n∈N (finitely) converges to a number j such thatϕj = f (for LIM and FIN ) and j = minψ f (for MIN ), respectively.
Definition 4. Let ψ ∈ P 2 , let U ⊆ R, and let d ∈ R. A strategy S ∈ P 2 identifies
U with nonconstructivity d(n) in the limit with respect to ψ, if for every n ∈ N there
is a help-word of length at most d(n) such that for every f ∈ U ∩ {ψ0 , ψ1 , . . . , ψn } thesequence (S(f n , w))n∈N converges to a program i satisfying ψi = f .
Nonconstructive finite and minimal identification are defined in analogue to theabove.
Looking at Definition 4 as well as at the definition of nonconstructive finite andminimal identification, 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 }.
In order to simplify notation in several theorems and proofs given below, we makethe following convention. Whenever we talk about nonconstructivity log n, we assume
that the logarithmic function to the base 2 is replaced by its integer valued counterpart
blog nc + 1.

6

Rūsiņš Freivalds and Thomas Zeugmann

3. Results
Already Gold [11] showed that R ∈/ LIM. So, we start our investigations by
asking for the amount of nonconstructivity needed to identify the set R of all recursivefunctions in the limit with respect to any Gödel numbering ϕ.
Using an idea from Freivald and Wiehagen [7], we prove that the needed amountof nonconstructivity is surprisingly small. To show this result, for every functionf ∈ Rmon we define 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 all f ∈ Rmon we canconclude that finv (n) ∈ R.
Theorem 1. Let ϕ ∈ Göd be arbitrarily fixed, and let d ∈ Rmon be any function. Then there is a strategy S ∈ P 2 such that the class R can be identified with
nonconstructivity log dinv (n) in the limit with respect to ϕ.
Proof. Let ϕ ∈ Göd be arbitrarily fixed. 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 suffices tohave an upper bound for minϕ f . So, assuming any help-word w of length 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 the help word. This bitstring is interpreted in theusual way as a natural number k. By construction, we then have k ≥ dinv (n). Furthermore, since d ∈ Rmon , we directly 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
S. Then, the strategy 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 i and x thatpassed this test successfully, the strategy then 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.
Finally, the strategy uses the amalgamation technique (cf. Wiehagen [22], Caseand Smith [4]). That is, let amal be a recursive function mapping any finite set Iof ϕ-programs to a ϕ-program such that for any x ∈ N, ϕamal(I) (x) is defined byrunning ϕi (x) for every i ∈ I in parallel and taking the first value obtained, if any.
So, the output of S(f m , w) is amal(Im ).
It remains 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 .
Clearly, this program and any other ϕ-program computing a subfunction of f cannever be 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

On the Amount of Nonconstructivity in the Inductive Inference of Recursive Functions

7

as m ≥ max{x, Φj (x)}, the program j is removed from Iinit . Since Iinit is finite,
there must exists an m∗ such that Im∗ contains only ϕ-programs computing f or asubfunction of f . We conclude that amal(Im∗ ) is a ϕ-programs for f . Furthermore,I` = Im∗ for all ` ≥ m∗ , and thus the strategy S learns f in the limit.
As we have seen, there is no smallest amount of nonconstructivity needed to learn
R in the limit. On the other hand, the amount of nonconstructivity cannot be zero,
since then we would have R ∈ LIM. But one can define a total function t ∈ T suchthat t(n) ≥ d(n) for all d ∈ Rmon and all but finitely many n. Consequently, log tinv
is then a lower bound for the amount of nonconstructivity needed to learn R in thelimit.
We continue by asking what amount of nonconstructivity is needed to obtain ϕminimal identification in the limit of the class R. Now, the situation is intuitively
more complex, since LIMϕ \ MIN ϕ 6= ∅ for every ϕ ∈ Göd. Interestingly, there areeven Gödel numberings ϕ such that MIN ϕ contains only classes of finite cardinality(cf. Freivalds [9]). On the other hand, the sufficient amount of nonconstructivity given
in Theorem 2 does not depend on the Gödel numbering. Theorem 2 below is not thebest possible and we shall improve it below, but it shows an easy way to achieve
ϕ-minimal learning of of the class R in the limit.
Theorem 2. Let ϕ ∈ Göd be arbitrarily fixed. Then there is a strategy S ∈ P 2
such that the class R can be ϕ-minimal identified with nonconstructivity n + 1 in thelimit with respect to ϕ.
Proof. Let ϕ ∈ Göd be arbitrarily fixed, and let n ∈ N. The help-word w is a
bitstring b of length n + 1 defined as follows. If ϕi ∈ R, then the ith entry of b
is 1, and 0 otherwise. So, the length of the help-word directly allows the strategy tocompute n.
Next, 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. Since all these remaining functions are total, the strategymsearches for the least index j among these functions for which ϕm
j = f . That is, itessentially uses the identification by enumeration principle (cf. Gold [12]).
The proof of Theorem 2 looks quite simple which may be an indication that asmaller amount of nonconstructivity may suffice. Unfortunately, so far we could notshow a lower bound for the amount of nonconstructivity needed to achieve ϕ-minimallearning in the limit of the class R. On the other hand, as Theorem 4 below shows, we
can achieve a much better result when allowing nonconstructivity n + 1. This again
indicates that we have used a too great amount of nonconstructivity in Theorem 2.
And indeed, we can do exponentially better.
Theorem 3. Let ϕ ∈ Göd be arbitrarily fixed. Then there is a strategy S ∈ P 2
such that the class R can be ϕ-minimal identified with nonconstructivity 2 · log n in
the limit with respect to ϕ.

8Rūsiņš Freivalds and Thomas Zeugmann

Proof. The key observation to show the theorem is that it suffices to know thenumber of recursive functions in the set {ϕ0 , . . . , ϕn }. In order to use this information
appropriately, the first half of the help-word is the binary encoding of n and the second
half of the help-word w is just providing the number, say k, of recursive functions inthe set {ϕ0 , . . . , ϕn }. This number is also written in binary but leading zeros areadded in order to ensure that both parts of the help-word have the same length. Thus
2 · log n many bits suffice to represent the help-word.
Next, assume any function f ∈ R ∩ {ψ0 , ψ1 , . . . , ψn }, and let f m and w be theinput to S. Then the strategy S, by dovetailing its computations, first tries to compute
ϕi (0), . . . , ϕi (m) for all 0 ≤ i ≤ n until it finds the first k programs i1 , . . . , ik such thatϕi (0), . . . , ϕi (m) turn out to be defined for every i ∈ {i1 , . . . , ik }. Once the strategy S
has found these programs i1 , . . . , ik , it outputs the least program i ∈ {i1 , . . . , ik } formwhich it verifies ϕmprovided there is such a program, and m otherwise.
i = fTaking into account that there must be n + 1 − k many programs j among the
programs 0, . . . , n such that ϕj ∈ P \ R, for each of these programs j there must bea smallest yj such that ϕj (yj ) ↑ . Let ymax be the maximum of all these yj . Hence,as soon as m ≥ ymax , the strategy S must find precisely the programs i1 , . . . , ik suchthat ϕi ∈ R for all i ∈ {i1 , . . . , ik }. By assumption, the target function f possesses
a program i with 0 ≤ i ≤ n, and thus for all m ≥ ymax , the strategy must output
minϕ f .
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 fixed. Then there is a strategy S ∈ P 2
such that the class R can be ϕ-minimal finitely identified with nonconstructivity n + 1
with respect to ϕ.
Proof. Let ϕ ∈ Göd be arbitrarily fixed, and let n ∈ N. The help-word w is a
bitstring b of length n + 1 defined 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 }.
Next, 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 ϕmi and checks whether or not they are
pairwise different. As long as this is not the case, the strategy outputs m. If all theseϕm
i are pairwise different, then the strategy outputs the i for which it could verifymf = ϕmi .
By construction, it is obvious that S finitely converges to minϕ f .

On the Amount of Nonconstructivity in the Inductive Inference of Recursive Functions

9

Again, we still could not prove the amount of nonconstructivity given in Theorem 4
to be the best possible.
We therefore continue to look at the case, where we have to learn an indexedfamily U of recursive functions. Note that for every indexed family U and any of its
numberings ψ ∈ R2 we have U ∈ MIN ψ (cf. Gold [12]). In contrast, N UM # FIN(see e.g., [23] and the references therein). So, it is only natural to ask for the amountof nonconstructivity needed to finitely learn ψ-minimal programs. The answer isprovided 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 finitely
identified with nonconstructivity 2 · log n with respect to ψ.
Proof. The key observation for the proof is that it suffices to know the number kof distinct functions in {ψ0 , . . . , ψn }. Thus, the help-word w is again divided in two
halves, where the first half is the binary representation of n and the second half
provides the number k (again including leading zeros). Thus 2 · log n many bits suffice
for representing the help-word.
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 verified that there areexactly k different functions. Let i1 , . . . , ik be the least indices of these k different
functions. Next, it checks whether or not there is precisely one i ∈ {i1 , . . . , ik } suchthat f m = ψim . If this is the case, the strategy outputs this i. Otherwise, it outputs m.
By construction, it is obvious that S finitely 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 it suchthat no strategy S ∈ P 2 can ψ-minimal finitely 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 defining the numbering ψ ∈ R2
for it. For this purpose, we use the following pairing function c : N × N → N, wherec(x, y) = 2x (2y +1)−1. Note that this pairing function is a bijection. It may be traced
back to Pepis [19] and Kalmár [14]. Furthermore, we interpret every function in P 2
as a strategy and obtain thus an effective enumeration S0 , S1 , S2 , . . . of all possible
strategies. Below, for ` ∈ N, we use the shortcut i`+1 to denote the encoding f ` of theinitial segment of the function f for which f (z) = i for all i = 0, . . . , `.
For every i ∈ N we define two functions ψ2i and ψ2i+1 as follows. Let x and y be theuniquely determined numbers such that i = c(x, y). Now, we successively define fork = 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 find the smallest k such that the following Conditions (A)and (B) are satisfied.

10

Rūsiņš Freivalds and Thomas Zeugmann(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 satisfied then the function valuesψ2i (k) and ψ2i+1 (k) are defined for all k ∈ N, and thus ψ2i , ψ2i+1 ∈ R.
On the other hand, if Conditions (A) and (B) turn out to be satisfied then Condition (B) implies that the sequence Sx (i, y), . . . , Sx (i`+1 , y) tends to converge finitely.
That is, it either converges finitely or it cannot converge finitely at all. Now, we
continue to define the functions ψ2i and ψ2i+1 as follows.
(C) If Sx (i` , y) = 2i, then we define ψ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 define ψ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 define ψ2i (z) = ψ2i+1 (z) = z for all z ≥ k.
So again we obtain that ψ2i , ψ2i+1 ∈ R, and consequently, ψ ∈ R2 . Finally, we set
the desired class U = Rψ .
It remains to show that there is no strategy S ∈ P 2 that ψ-minimal finitely identifies 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 finitely
identifies U with nonconstructivity c · log n with respect to ψ. Then there must be av ∈ N such that S = Sv in our enumeration S0 , S1 , S2 , . . . of all possible strategies.
Let d be the function from Definition 4. Furthermore, for every n ∈ N and everyf ∈ {ψ0 , . . . , ψn } there has to be a help-word w of length at most d(n) and depending
only on n such that the sequence (Sv (f m , w))m∈N finitely converges to the minimal
ψ-program of f .
By assumption, we know that there is a c ∈ (0, 1) such that d(n) ≤ c · log n. Hence,On the Amount of Nonconstructivity in the Inductive Inference of Recursive Functions

11

for n large enough we conclude that d(n) > 1 and (1 − c)/2 > (2 + (v + 1))/ log n.
1

>

log n

>

d(n) 2 + (v + 1)
+
log n
log n
d(n) + 2 + (v + 1)v+1>d(n) + 2>

2d(n)+2>

2 · 2d(n) + 1>

2w + 1 ,>

2v (2w + 1) − 1>c(v, w) .

log n − log 2

n
2v+1
n+2
2v+1
n+2
2v+1
n
2
n
2

since w ≤ 2d(n)Now, let i = c(v, w) and we consider the functions ψ2i and ψ2i+1 . By our choiceof n, these functions must be among the functions {ψ0 , . . . , ψn }.
Let ` ∈ N+ be the least number such that Sv on two successive inputs outputs thesame 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 finitely identify ψ2i nor ψ2i+1 .
If Sv (i` , w) ∈/ {2i, 2i + 1} we are already done, since ψ2i and ψ2i+1 are the only
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, above) we know that ψ2i (z) = ψ2i+1 (z) for all z = 0, . . . , ` but clearlyψ2i 6= ψ2i+1 . Thus, the strategy Sv fails to identify finitely either function ψ2i orfunction ψ2i+1 .
As the proof of Theorem 6 shows, the failure to ψ-minimal finitely identify theindexed family U with respect to the numbering ψ with nonconstructivity c · log n,
for c ∈ (0, 1), is caused by the requirement to finitely identify the functions from U.
Thus, we directly obtain the following corollary.
Corollary 7. There is an indexed family U and a numbering ψ ∈ R2 for it suchthat no strategy S ∈ P 2 can finitely identify the class U with nonconstructivity c · log nwith respect to ψ, where c ∈ (0, 1) is any constant.

4. Conclusions
We have presented a model for the inductive inference of recursive functions thatincorporates a certain amount of nonconstructivity. In our model, the amount of
nonconstructivity needed to solve the learning problems considered has been used asa quantitative characterization of their difficulty.
We studied the problem of learning the whole class R under various postulates.
These postulates range from learning in the limit to finite and minimal identification.

12

Rūsiņš Freivalds and Thomas Zeugmann

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 amount that can be describedin a computable way (cf. Theorem 1).
This result is nicely contrasted by the fact that we needed nonconstructivity 2·log nto ϕ-minimal identify the class R in the limit and nonconstructivity n+1 to ϕ-minimal
finitely 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
finitely 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 showedthat this amount cannot be substantially improved (cf. Theorems 5 and 6).

References[1] Leonard M. Adleman and M. Blum. Inductive inference and unsolvability. The
Journal of Symbolic Logic, 56(3):891–900, 1991.
[2] Jānis M. Bārzdiņš. 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] Manuel Blum. A machine independent theory of the complexity of recursivefunctions. Journal of the ACM, 14(2):322–336, 1967.
[4] John Case and Carl Smith. Comparison of identification criteria for machine
inductive inference. Theoret. Comput. Sci., 25(2):193–220, 1983.
[5] Peter Cholak, Rod Downey, Lance Fortnow, William Gasarch, Efim Kinber, Martin Kummer, Stuart Kurtz, and Theodore A. Slaman. Degrees of inferability. In
Proc. 5th Annual ACM Workshop on Comput. Learning Theory, pages 180–192,
New York, 1992. ACM Press.
[6] Paul Erdős. Some remarks on the theory of graphs. Bulletin of the American
Mathematical Society, 53(4):292–294, 1947.
[7] R. V. Freivald and R. Wiehagen. Inductive inference with additional information.
Elektronische Informationsverarbeitung und Kybernetik, 15(4):179–185, 1979.
[8] R.V. Freivald. Minimal gödel numbers and their identification in the limit. In
Jiřı́ Bečvář, editor, Mathematical Foundations of Computer Science 1975, 4th
Symposium, Mariánské Lázně, September 1-5, 1975, volume 32 of Lecture Notes
in Computer Science, pages 219–225, Berlin, 1975. Springer-Verlag.

On the Amount of Nonconstructivity in the Inductive Inference of Recursive Functions

13[9] Rūsiņš Freivalds. Inductive inference of recursive functions: Qualitative theory.
In J. Bārzdiņš and D. Bjørner, editors, Baltic Computer Science, volume 502 of
Lecture Notes in Computer Science, pages 77–110. Springer, Berlin, 1991.
[10] Rūsiņš Freivalds. Amount of nonconstructivity in finite automata. In Sebastian
Maneth, editor, Implementation and Application of Automata, 14th International
Conference, CIAA 2009, Sydney, Australia, July 14-17, 2009. Proceedings, volume 5642 of Lecture Notes in Computer Science, pages 227–236, Berlin, 2009.
Springer.
[11] E. Mark Gold. Limiting recursion. Journal of Symbolic Logic, 30:28–48, 1965.
[12] E. Mark Gold. Language identification in the limit. Inform. Control, 10(5):447–
474, 1967.
[13] 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.
[14] László Kalmár. On the reduction of the decision problem. First Paper. Ackermann
prefix, a single binary predicate. The Journal of Symbolic Logic, 4(1):1–9, 1939.
[15] Richard M. Karp and Richard J. Lipton. Turing machines that take advice. L’
Enseignement Mathématique, 28:191–209, 1982.
[16] E.B Kinber. O predel~nom sinteze poqti minimal~nyh gedelevskih
nomerov. In Jānis Bārzdiņš, editor, Teori Algoritmov i Programm, volume I, pages 212–223. Latvian State University, 1974.
[17] Martin Kummer and Frank Stephan. On the structure of the degrees of inferability. J. of Comput. Syst. Sci., 52(2):214–238, 1996.
[18] L. H. Landweber and E. L. Robertson. Recursive properties of abstract complexity classes. Journal of the ACM, 19(2):296–308, 1972.
[19] Joséf Pepis. Ein Verfahren der mathematischen Logik. The Journal of Symbolic
Logic, 3(2):61–76, 1938.
[20] Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability.
McGraw-Hill, 1967. Reprinted, MIT Press 1987.
[21] B. A. Trakhtenbrot and Ya. M. Barzdin. Finite Automata, Behavior and Synthesis. North Holland, Amsterdam, 1973.
[22] Rolf Wiehagen. Zur Theorie der Algorithmischen Erkennung. Dissertation B,
Humboldt-Universität zu Berlin, 1978.
[23] Thomas Zeugmann and Sandra Zilles. Learning recursive functions: A survey.
Theoret. Comput. Sci., 397(1-3):4–56, 2008.