TCS -TR-A-13-68

TCS Technical Report

Active Learning of Classes of Recursive Functions by
Ultrametric Algorithms
byRūsiņš Freivalds and Thomas Zeugmann

Division of Computer Science
Report Series A
October 24, 2013

Hokkaido University
Graduate School ofInformation Science and Technology

Email: thomas@ist.hokudai.ac.jp

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

Active Learning of Classes of Recursive Functions
by Ultrametric Algorithms∗
Rusin² Freivalds

Thomas Zeugmann

Institute of Mathematics and Computer Science

Division of Computer Science

University of Latvia

Hokkaido University

Raina Bulvaris 29

N-14, W-9

Riga, LV-1459, Latvia

Sapporo 060-0814, Japan

Rusins.Freivalds@mii.lu.lv

thomas@ist.hokudai.ac.jp

Abstract
We study active learning of classes of recursive functions by asking value
queries about the target function f , where f is from the target class. That is, thequery is a natural number x, and the answer to the query is f (x). The complexity
measure in this paper is the worst-case number of queries asked. We prove thatfor some classes of recursive functions ultrametric active learning algorithms canachieve the learning goal by asking signicantly fewer queries than deterministic,
probabilistic, and even nondeterministic active learning algorithms. This is therst ever example of a problem, where ultrametric algorithms have advantages
over nondeterministic algorithms.

1. Introduction

In traditional studies of learning of recursive functions [10, 13, 42, 43], concepts aremodeled as a set of stimulus and response pairs. Assuming that any concept associates
only one response with each possible stimulus, it can be viewed as a function fromstimuli to responses. Every string of ASCII symbols can be encoded in the natural
numbers. These strings include arbitrarily long nite texts and are certainly sucient
to express both stimuli and responses. So for a mathematical treatment of learning, itsuces to consider only the functions from natural numbers to natural numbers. Via
suitable encodings, these functions can represent a wide range of phenomena. Since
we shall be concerned only with eective learning procedures, the recursive functions
are used to model concepts.
∗

The research was supported by Grant No. 09.1570 from the Latvian Council of Science and theInvitation Fellowship for Research in Japan S12052 by Japan Society for the Promotion of Science1

2

Rūsiņš Freivalds and Thomas Zeugmann

Inductive inference, the abstract study of generalization, has been studied intensively. In Gold's [18] model of identication in the limit, the learner is a deterministic algorithm called inductive inference machine (abbr. IIM), and the objects tobe learned are recursive functions. The source of information are growing initial
segments (x0 , f (x0 )), (x1 , f (x1 )), . . . , (xn , f (xn )) of ordered pairs of the graph of thetarget function f , where it is assumed that every pair (x, f (x)) appears eventually. Asa hypothesis space one can choose any Gödel numbering ϕ0 , ϕ1 , ϕ2 , . . . of the set of allpartial recursive functions over the natural numbers (cf. Rogers [38]). If a number i issuch that ϕi = f then we call i a ϕ-program of f . An IIM, on input an initial segment(x0 , f (x0 )), (x1 , f (x1 )), . . . , (xn , f (xn )), has to output a natural number in which isinterpreted as ϕ-program. An IIM identies f if the sequence (in )n∈N of all computed
ϕ-programs converges to a program i such that ϕi = f . Here N = {0, 1, 2, . . .} denotes
the set of all natural numbers. If an IIM identies some function f , then some form oflearning must have taken place, since, by the properties of convergence, only a nitepart of the graph of f was known by the IIM at the (unknown) point of convergence.
The terms infer and learn will be used as synonyms for identify.
Every IIM M learns some set of recursive functions which we denote by EX(M ).
The family of all such sets, over the universe of eective algorithms viewed as IIMs,
serves as a characterization of the learning power inherent in the Gold model. This
family is symbolically denoted by EX (short for explanatory) and it is dened rigorously by EX = {U | ∃M (U ⊆ EX(M )}. In many studies of inductive inference thefamily EX is set-theoretically compared with the families that arise from consideringother models. In this way, one parameter of the learning process can be examinedin isolation (cf., e.g., [43] and the references therein). There are several well studied
derivatives of the Gold [18] model. One such derivative is nite learning, where theIIM either requests a new input and outputs nothing, or it outputs a program i, andstops. Again we require that program i is correct for f , i.e., ϕi = f .
The models described so far are models of passive learning, since the IIM has noinuence on the order in which examples are presented. In contrast, the learningmodel considered in the present paper is an active one. This model goes back to
Angluin [3] and is called query learning. In the query learning model the learner hasaccess to a teacher that truthfully answers queries of a prespecied type. In this paper
we only consider value queries. That is, the query is a natural number x, and theanswer to the query is f (x). A query learner is an algorithmic device that, dependingon the answers already received, either computes a new value query or it returns ahypothesis i and stops. As above, the hypothesis is interpreted with respect to a xedGödel numbering ϕ and it is required that the hypothesis returned satises ϕi = f .
So active learning is nite learning.
As in the Gold [18] model, we are interested in active learners that can infer wholeclasses of recursive functions. The complexity measure is then the worst-case numberof queries asked to identify all the functions from the target class U . We refer to any
query learner as query inference machine (abbr. QIM).

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

3

Note that value queries are just the simplest type of query. Various authors studied
many dierent query languages extending this simplest type of query (cf., e.g., [15,17, 16, 26]).
Automata theory and complexity theory have considered several natural generalizations of deterministic algorithms, namely, nondeterministic and probabilistic algorithms. In many cases these generalized algorithms allow for computations having
a complexity that is strictly less than their deterministic counterpart. Such generalized algorithms attracted considerable attention in learning theory, too. Many papers
studied learnability by nondeterministic algorithms [1, 8, 14, 41] and probabilistic
algorithms [20, 25, 31, 32, 33, 36, 37].
In the following we use P , R and P 2 , R2 to denote the set of all partial recursive functions and of all recursive functions of one respectively two variables over N,
respectively. Furthermore, we formally dene what a Gödel numbering is. Any function ψ ∈ P 2 is called a numbering. Moreover, let ψ ∈ P 2 , then we write ψi instead ofλx.ψ(i, x) and set Pψ = {ψi | i ∈ N} as well as Rψ = Pψ ∩ R. A numbering ϕ ∈ P 2 iscalled a Gödel numbering (cf. Rogers [38]) i Pϕ = P , and for any numbering ψ ∈ P 2 ,there is a compiler c ∈ R such that ψi = ϕc(i) for all i ∈ N.

Denition 1. We say that a nondeterministic QIM learns a function f if
(1) there is at least one computation path such that the QIM produces a correct result
on f , i.e., program j such that ϕj = f ;(2) at no computation path the QIM produces an incorrect result on f .
Probabilistic algorithms can be represented by rooted trees (cf. Hromkovi£ [21]).
The leaves of the tree are the output nodes and the probability to reach a leaf iscomputed in the usual way.

Denition 2. We say that a probabilistic QIM produces a result m with a probability
p if the sum of the probabilities of all leaves which correctly produce the result m is noless than p.
Denition 3. We say that a probabilistic QIM learns a function f with a probability p
if(1) the sum of all probabilities of all leaves which produce a correct result on f , i.e.,a number j such that ϕj = f , is no less than p.
(2) at no computation path the QIM produces an incorrect result on f .
Recently, Freivalds [11] introduced a new type of indeterministic algorithms called
ultrametric algorithms. An extensive research on ultrametric algorithms of various
kinds is currently performed by him and his co-authors (cf. [4, 23]). So, ultrametricalgorithms are a very new concept and their potential still has to be explored. This is4Rūsiņš Freivalds and Thomas Zeugmannthe rst paper showing a problem, where ultrametric algorithms have advantages overnondeterministic algorithms. Ultrametric algorithms are very similar to probabilistic
algorithms but while probabilistic algorithms use real numbers r with 0 ≤ r ≤ 1
as parameters, ultrametric algorithms use p-adic numbers as the parameters. As
it turns out the usage of p-adic numbers as amplitudes and the ability to performmeasurements to transform amplitudes into real numbers are inspired by quantum
computations and allow for algorithms not possible in classical computations. Slightly
simplifying the description of the denitions, one can say that ultrametric algorithms
are the same as probabilistic algorithms, only the interpretation of the probabilities
is dierent.
The choice of p-adic numbers instead of real numbers is not quite arbitrary. Ostrowski [35] proved that any non-trivial absolute value on the rational numbers Q is
equivalent to either the usual real absolute value or a p-adic absolute value. This
result shows that using p-adic numbers was not merely one of many possibilities togeneralize the denition of deterministic algorithms but rather the only remaining
possibility not yet explored.
The notion of p-adic numbers is widely used in science. String theory [40], chemistry [28] and molecular biology [9, 24] have introduced p-adic numbers to describe
measures of indeterminism. Indeed, research on indeterminism in nature has a long
history. Pascal and Fermat believed that every event of indeterminism can be described by a real number between 0 and 1 called probability. Quantum physics introduced a description in terms of complex numbers called amplitude of probabilities andlater in terms of probabilistic combinations of amplitudes most conveniently describedby density matrices. Using p-adic numbers to describe indeterminism allows to explore some aspects of indeterminism but, of course, does not exhaust all the aspectsof it.
There are many distinct p-adic absolute values corresponding to the many prime
numbers p. These absolute values are traditionally called ultrametric. Absolute values are needed to consider distances among objects. We are used to rational andirrational numbers as measures for distances, and there is a psychological diculty toimagine that something else can be used instead of rational and irrational numbers,
respectively. However, there is an important feature that distinguishes p-adic numbers
from real numbers. Real numbers (both rational and irrational) are linearly ordered,
while p-adic numbers cannot be linearly ordered. This is why valuations and normsof p-adic numbers are considered.
The situation is similar in Quantum Computation (see [34]). Quantum amplitudes
are complex numbers which also cannot be linearly ordered. The counterpart ofvaluation for quantum algorithms is measurement translating a complex number a+bi
into a real number a2 + b2 . Norms of p-adic numbers are rational numbers. To makethe paper as self-contained as possible, we continue with a short description of p-adic
numbers.

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

5

2. p-adic Numbers and Ultrametric Algorithms

Let p be an arbitrary prime number. A number a ∈ N with 0 ≤ a ≤ p − 1 is calleda p-adic digit. A p-adic integer is by denition a sequence (ai )i∈N of p-adic digits. We
write this conventionally as · · · ai · · · a2 a1 a0 , i.e., the ai are written from left to right.
If n is a natural number, and n = ak−1 ak−2 · · · a1 a0 is its p-adic representation,Pii.e., n = k−1
i=0 ai p , where each ai is a p-adic digit, then we identify n with the p-adic
integer (ai ), where ai = 0 for all i ≥ k . This means that the natural numbers can be
identied with the p-adic integers (ai )i∈N for which all but nitely many digits are 0.
In particular, the number 0 is the p-adic integer all of whose digits are 0, and 1 is thep-adic integer all of whose digits are 0 except the right-most digit a0 which is 1.
To obtain p-adic representations of all rational numbers, p1 is represented as · · · 00.1,
the number p12 as · · · 00.01, and so on. For any p-adic number it is allowed to haveinnitely many (!) digits to the left of the  p-adic point but only a nite number ofdigits to the right of it.
However, p-adic numbers are not merely a generalization of rational numbers. They
are related to the notion of absolute value of numbers.
If X is a nonempty set, a distance, or metric, on X is a function d from X × X to
the nonnegative real numbers such that for all (x, y) ∈ X × X the following conditions
are satised.
(1) d(x, y) ≥ 0, and d(x, y) = 0 if and only if x = y ,(2) d(x, y) = d(y, x),(3) d(x, y) ≤ d(x, z) + d(z, y) for all z ∈ X .
A set X together with a metric d is called a metric space. The same set X cangive rise to many dierent metric spaces. If X is a linear space over the real numbersthen the norm of an element x ∈ X is its distance from 0, i.e., for all x, y ∈ X and α
any real number we have:(1) kxk ≥ 0, and kxk = 0 if and only if x = 0,(2) kα · yk = |α| · kyk,
(3) kx + yk ≤ kxk + kyk.
Note that every norm induces a metric d, i.e., d(x, y) = kx − yk. A well-known
example is the metric over Q induced by the ordinary absolute value. However, there
are other norms as well.
A norm is called ultrametric if Requirement (3) can be replaced by the stronger
statement: kx + yk ≤ max{kxk, kyk}. Otherwise, the norm is called Archimedean.

6

Rūsiņš Freivalds and Thomas ZeugmannDenition 4. Let p ∈ {2, 3, 5, 7, 11, 13, . . .} be any prime number. For any nonzero
integer a, let the p-adic ordinal (or valuation) of a, denoted ordp a, be the highest
power of p which divides a, i.e., the greatest number m ∈ N such that a ≡ 0 (mod pm ).
For any rational number x = a/b we dene ordp x =df ordp a − ordp b. Additionally,
ordp x =df ∞ if and only if x = 0.
For example, let x = 63/550 = 2−1 · 32 · 5−2 · 71 · 11−1 . Thus, we haveord2 x = −1
ord3 x = +2
ord5 x = −2

ord7 x = +1
ord11 x = −1
ordp x = 0 for every prime p ∈/ {2, 3, 5, 7, 11} .

Denition 5. Let p ∈ {2, 3, 5, 7, 11, 13, . . .} be any prime number. For any rational
number x, we dene its p-norm as p−ordp x , and we set k0kp =df 0.
For example, with x = 63/550 = 2−1 32 5−2 71 11−1 we obtain:

kxk2 = 2
kxk3 = 1/9
kxk5 = 25

kxk7 = 1/7
kxk11 = 11
kxkp = 1 for every prime p ∈/ {2, 3, 5, 7, 11} .

Rational numbers are p-adic integers for all prime numbers p. Since the denitions
given above are all we need, we nish our exposition of p-adic numbers here. For a
more detailed description of p-adic numbers we refer to [19, 27].
We continue with ultrametric algorithms. In the following, p always denotes aprime number. Ultrametric algorithms are described by nite directed acyclic graphs(abbr. DAG), where exactly one node is marked as root. As usual, the root does nothave any incoming edge. Furthermore, every node having outdegree zero is said to bea leaf. The leaves are the output nodes of the DAG.
Let v be a node in such a graph. Then each outgoing edge is labeled by a p-adic
number which we call amplitude. We require that the sum of all amplitudes that
correspond to v sums up to 1. In order to determine the total amplitude along a
computation path, we need the following denition.

Denition 6. The total amplitude of the root is dened to be 1. Furthermore, let v
be a node at depth d in the DAG, let α be its total amplitude, and let β1 , β2 , · · · , βkbe the amplitudes corresponding to the outgoing edges e1 , . . . , ek of v . Let v1 , . . . , vk
be the nodes where the edges e1 , . . . , ek point to. Then the total amplitude of v` ,` ∈ {1, . . . , k}, is dened as follows.
(1) If the indegree of v` is one, then its total amplitude is αβ` .
(2) If the indegree of v` is bigger than one, i.e., if two or more computation paths arejoined, say m paths, then let α, γ2 , . . . , γm be the corresponding total amplitudesof the predecessors of v` and let β` , δ2 , . . . , δm be the amplitudes of the incomingedges The total amplitude of the node v` is then dened to be αβ` + γ2 δ2 + · · · +δm γm .

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

7

Note that the total amplitude is a p-adic integer.
We refer the reader to the proof of Theorem 9 for an example.
It remains to dene what is meant by saying that a p-ultrametric algorithm produces a result with a certain probability. This is specied by performing a so-calledmeasurement at the leaves of the corresponding DAG. Here by measurement we meanthat we transform the total amplitude β of each leaf to kβkp . We refer to kβkp as the
p-probability of the corresponding computation path.

Denition 7. We say that a p-ultrametric algorithm produces a result m with aprobability q if the sum of the p-probabilities of all leaves which correctly produce theresult m is no less than q .
Denition 8. We say that a p-ultrametric QIM learns a function f with a probability q if(1) the sum of the p-probabilities of all leaves which produce a correct result on f ,i.e., a number j such that ϕj = f is no less than q ,(2) at no computation path the QIM produces an incorrect result on f .

3. Results

As explained in the Introduction we are interested in the number of queries a QIM
has to ask in the worst-case in order to infer all recursive functions from a prespeciedclass U . In order to study this problem we shall always assume the hypothesis space
to be a Gödel numbering ϕ (cf. [38]). This is no restriction of generality since all
natural programming languages provide Gödel numberings of recursive functions.
The complexity of learning recursive functions has been an important topic forseveral decades [2, 12, 13, 29, 42, 43]. Furthermore, the problem to learn functions
from value queries has been intensively studied in various domains. We refer thereader to Bshouty [7] for an overview. In the present paper we compare the querycomplexity of deterministic, nondeterministic, probabilistic, and ultrametric QIMs to
one another.
Our results are somewhat unexpected. Usually, for various classes of problems,
nondeterministic algorithms provide the smallest complexity, deterministic algorithms
provide the largest complexity and probabilistic algorithms provide some medium
complexity. In [4, 11, 23] ultrametric algorithms also gave medium complexity sometimes better and sometimes worse than probabilistic algorithms. Our results in thispaper show that, for learning recursive functions from value queries, there are classes U
of recursive functions such that ultrametric QIMs have a smaller query complexity
than even nondeterministic QIMs. This is the rst ever example of a problem, whereultrametric algorithms have advantages over nondeterministic algorithms.

8

Rūsiņš Freivalds and Thomas Zeugmann
0

1

5
2

3

4
6

Figure 1: The Fano Plane
To show these results we use a combinatorial structure called the Fano plane. It is
one of nite geometries (cf. Meserve [30]). The Fano plane consists of seven points
0, 1, 2, 3, 4, 5, 6 and seven lines (0, 1, 3), (1, 2, 4), (2, 3, 5), (3, 4, 6), (4, 5, 0), (5, 6, 1),(6, 0, 2). For any two points i, j with i 6= j , in this geometry there is exactly one
line that contains these points (cf. Figure 1). For any two dierent lines in thisgeometry there is exactly one point contained in these two lines. In our construction
the points 0, 1, 2, 3, 4, 5, 6 are interpreted as colored in two dierent colors RED andBLUE, respectively.

Lemma 1 (Meserve [30]). For an arbitrary coloring of the Fano plane there is at least
one line the 3 points of which are colored by the same color.
Lemma 2 (Meserve [30]). For any coloring of the Fano plane there cannot exist twodierent lines colored in opposite colors.
Proof. As explained above, for any two dierent lines in the Fano plane there is exactly
one point contained in these two lines. So it is impossible to have two dierent lines
colored in opposite colors.

Let ϕ be a Gödel numbering of P . We consider the following class U7 of recursivefunctions. Each function f ∈ U7 is such that f ∈ R and:(1) every f (x) where 0 ≤ x ≤ 6 equals either 2s or 3t , where s, t ∈ N, s, t ≥ 1,(2) if 0 ≤ x1 < x2 ≤ 6, f (x1 ) = 2s and f (x2 ) = 2t , then f (x1 ) = f (x2 ),(3) if 0 ≤ x1 < x2 ≤ 6, f (x1 ) = 3s and f (x2 ) = 3t , then f (x1 ) = f (x2 ),(4) if f (0) = 2s and f (1) = 2s and f (3) = 2s , then s is a correct ϕ-program for f ,(5) if f (1) = 2s and f (2) = 2s and f (4) = 2s , then s is a correct ϕ-program for f ,(6) if f (2) = 2s and f (3) = 2s and f (5) = 2s , then s is a correct ϕ-program for f ,(7) if f (3) = 2s and f (4) = 2s and f (6) = 2s , then s is a correct ϕ-program for f ,(8) if f (4) = 2s and f (5) = 2s and f (0) = 2s , then s is a correct ϕ-program for f ,Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

9(9) if f (5) = 2s and f (6) = 2s and f (1) = 2s , then s is a correct ϕ-program for f ,(10) if f (6) = 2s and f (0) = 2s and f (2) = 2s , then s is a correct ϕ-program for f ,(11) if f (0) = 3t and f (1) = 3t and f (3) = 3t , then s is a correct ϕ-program for f ,(12) if f (1) = 3t and f (2) = 3t and f (4) = 3t , then t is a correct ϕ-program for f ,(13) if f (2) = 3t and f (3) = 3t and f (5) = 3t , then t is a correct ϕ-program for f ,(14) if f (3) = 3t and f (4) = 3t and f (6) = 3t , then t is a correct ϕ-program for f ,(15) if f (4) = 3t and f (5) = 3t and f (0) = 3t , then t is a correct ϕ-program for f ,(16) if f (5) = 3t and f (6) = 3t and f (1) = 3t , then t is a correct ϕ-program for f ,(17) if f (6) = 3t and f (0) = 3t and f (2) = 3t , then t is a correct ϕ-program for f .

Comment. In our construction of the class U7 the points 0, 1, 2, 3, 4, 5, 6 can beinterpreted as colored in two colors. Some points f (i) are such that f (i) = 2s (thesepoints are described below as RED) while some other points j are such that f (j) = 3t(these points are described below as BLUE). The properties of the Fano plane ensurethat for every such coloring in two colors there exists a line such that the three points
on this line are colored in the same color, and there cannot exist two lines colored in
opposite colors.

Denition 9. A partial coloring C of a Fano plane is an assignment of colors RED,
BLUE, NONE to the points of the Fano plane.
A partial coloring C2 is an extension of a partial coloring C1 if every point colored
RED or BLUE in C1 is colored in the same color in C2 .
A partial coloring C of a Fano plane is called complete if every point is colored
RED or BLUE.
Lemma 3. Given any partial coloring C of the points in the Fano plane assigningcolors RED and BLUE to some but not all points such that no line contains threepoints in the same color, there exists(1) a complete extension of the given coloring C such that it contains a line withthree RED points, and(2) a complete extension of the given coloring C such that it contains a line withthree BLUE points.

Proof. Color all the not colored points RED for the rst function, and BLUE for thesecond function.

10

Rūsiņš Freivalds and Thomas Zeugmann

Lemma 4. Given any partial coloring C of points in the Fano plane assigning colors
RED and BLUE to some but not all points such that no line contains three points inthe same color, there exist numbers k∗ , `∗ ∈ N and(1) a function fRED ∈ U7 dened as f (x) = 2`∗ for all x colored RED in C such that
fRED contains a line with three RED points, and all the points 0, 1, 2, 3, 4, 5, 6

are colored RED or BLUE,(2) a function fBLUE ∈ U7 dened as f (x) = 3k∗ for all x colored BLUE in C
such that fBLUE contains a line with three BLUE points, and all the points
0, 1, 2, 3, 4, 5, 6 are colored RED or BLUE.
Proof. Let red and blue be the subset of {0, 1, 2, 3, 4, 5, 6} which are colored RED andBLUE, respectively. By the assumptions of the lemma we then have red ∩ blue = ∅and red ∪ blue ⊂ {0, 1, 2, 3, 4, 5, 6}. Furthermore, so far there is no line in the Fano
plane that has all points colored in the same color.
To show Assertion (1), let a function h ∈ R be chosen such that for all `, x ∈ N `3 ,if x ∈ blue ;ϕh(`) (x) =2` ,otherwise .
The construction directly implies that ϕh(`) ∈ R for all ` ∈ N. By the xed point
theorem (cf. Rogers [38]) there is a number `∗ ∈ N such that the equality ϕ`∗ = ϕh(`∗ )is satised. Now, by Lemma 3 we know that the Fano plane has a line colored in RED,say (i, j, k) (cf. the comment made after the denition of the class U7 ). In accordancewith our construction we conclude thatϕ`∗ (i) = ϕ`∗ (j) = ϕ`∗ (k) = 2`∗ .
Consequently, ϕ`∗ ∈ U7 and Assertion (1) is shown by setting fRED =df ϕ`∗ .
Assertion (2) can be shown mutatis mutandis.

Theorem 1. There is a deterministic QIM M that learns the class U7 with 7 queries.
Proof. The desired QIM M queries the points 0, 1, . . . , 6. After having received

f (0), f (1), f (2), . . . , f (6), it checks at which line all points have the same color, andoutputs the ϕ-program corresponding to this line. Note that by Lemmata 1 and 2
there is at least one such line and there cannot be two lines colored in dierent colors.
By the denition of the class U7 one can directly output a correct ϕ-program for thetarget function f .

In order to show Theorem 3 below we need Smullyan's double xed point theorem(cf. [38, 39]). So let us recall it here.

Theorem 2 (Smullyan [39]). Let ϕ be any Gödel numbering of P , and let h, s ∈ R2 .
Then there are k∗ , `∗ ∈ N such that simultaneously the equations ϕk∗ = ϕh(k∗ ,`∗ ) andϕ`∗ = ϕs(k∗ ,`∗ ) are satised.

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

11

Theorem 3. There exists no deterministic QIM learning U7 with 6 queries.
Proof. The proof is by contradiction. Using Smullyan's double xed point theorem [38]one can construct two functions f and f˜ such that both are in U7 but at least one ofthem is not correctly learned by the QIM M . This is done as follows.

Suppose that such a QIM M exists. Of course, in order to learn functions from theclass U7 the QIM M should ask value queries for values in {0, 1, . . . , 6}. If any othervalue query is made we dene the corresponding function values to be 0. Furthermore,
we assume without loss of generality that every query is made only one time.
By symmetry we can assume without loss of generality that the rst value queryof M is 0. To answer it, let functions h, s ∈ R2 be chosen such that for all k, ` ∈ N

ϕh(k,`) (0) = 2k

and ϕs(k,`) (0) = 2k .

We return 2k to the QIM M and set Q1 = {0}.
Next, let the second query of M be x2 for some x2 ∈ {0, 1, . . . , 6} \ Q1 . Now we deneϕh(k,`) (x2 ) = 2kand

ϕs(k,`) (x2 ) = 2k ,return 2k to the QIM M and set Q2 = {0, x2 }.
If the third query of the QIM M is x3 , where x3 ∈ {0, 1, 2, 3, 4, 5, 6} \ Q2 is suchthat (0, x2 , x3 ) form a line in the Fano plane then we deneϕh(k,`) (x3 ) = 3`and

ϕs(k,`) (x3 ) = 3`

to avoid that this line gets three equally colored points. In this case we return 3` .
Otherwise, we deneϕh(k,`) (x3 ) = 2kand

ϕs(k,`) (x3 ) = 2k ,return 2k and set in both cases Q3 = {0, x2 , x3 }.
The remaining three queries of the QIM M are answered in the following way(cf. Figure 1). If the next queried point x is such that no new line gets 3 equallycolored points, we deneϕh(k,`) (x) = 2kand

ϕs(k,`) (x) = 2k ,return 2k to the QIM M , and add x to the set of queried points.
If the queried point is such that some line can get 3 equally colored points, wedene the value of the functions as

ϕh(k,`) (x) = 2kor

ϕh(k,`) (x) = 3`

ϕs(k,`) (x) = 2kor

ϕs(k,`) (x) = 3`

as well as12Rūsiņš Freivalds and Thomas Zeugmann

to avoid this. Then we return the dened value and add the queried point to the setof all already queried points.
Note that after these 6 queries the functions ϕh(k,`) and ϕs(k,`) are dened in thesame way for all `, k ∈ N and all 6 queried points in Q6 .
To complete the proof we dene the functions ϕh(k,`) and ϕs(k,`) for the remaining
point x ∈ {0, 1, 2, 3, 4, 5, 6} \ Q6 to beϕh(k,`) (x) = 2k

and ϕs(k,`) (x) = 3`

and set ϕh(k,`) (y) = ϕs(k,`) (y) = 0 for all `, k ∈ N and all y ∈ N, where y > 6.
By construction, ϕh(k,`) , ϕs(k,`) ∈ R for all `, k ∈ N. Now we apply Theorem 2.
Hence there are k∗ , `∗ ∈ N such that simultaneously the equations ϕk∗ = ϕh(k∗ ,`∗ ) andϕ`∗ = ϕs(k∗ ,`∗ ) are satised. So we haveϕk∗ (0) = ϕh(k∗ ,`∗ ) (0) = 2k∗ϕ`∗ (0) = ϕs(k∗ ,`∗ ) (0) = 2k∗
ϕk∗ (x1 ) = ϕh(k∗ ,`∗ ) (x1 ) = 2k∗ϕ`∗ (x1 ) = ϕs(k∗ ,`∗ ) (x1 ) = 2k∗ ,and so on. But by construction the function ϕk∗ must have a line (xi1 , xi2 , xi3 ) in theFano plane such thatϕk∗ (xij ) = ϕh(k∗ ,`∗ ) (xij ) = 2k∗

for j = 1, 2, 3 .

Consequently, we know that ϕk∗ ∈ U7 .
Analogously, the function ϕ`∗ has a line (zi1 , zi2 , zi3 ) in the Fano plane such thatϕ`∗ (zij ) = ϕs(k∗ ,`∗ ) (zij ) = 3`∗

for j = 1, 2, 3 .

Therefore, we conclude that ϕ`∗ ∈ U7 . So, we set f =df ϕk∗ and f˜ =df ϕ`∗ . As shown
above, the functions f and f˜ belong to U7 and coincide in their values on all points
queried by the QIM M . Hence, M must fail to learn f or f˜, a contradiction.

Theorem 4. There is a nondeterministic QIM M learning U7 with 3 queries.
Proof. The QIM M starts with a nondeterministic branching of the computation into 7

possibilities corresponding to the 7 lines in the Fano plane. In each case, all 3 points
i, j, k are queried. If f (i), f (j), f (k) are not of the same color then the computation
path is aborted. If they are of the same color, e.g., f (i) = 2si , f (j) = 2sj , f (k) = 2sk ,then the denition of the class U7 ensures that si = sj = sk and the QIM M outputs si
which is a correct program computing the function f .

Theorem 5. There is no nondeterministic QIM learning U7 with 2 queries.
Proof. By Lemma 4, there are two distinct functions in the class U7 with the samevalues queried by the nondeterministic algorithm. The output is not correct for atleast one of them.

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

13

In contrast to Theorem 3 we can show that 6 queries are already enough for aprobabilistic QIM to achieve successful learning via value queries with a probability
bigger than 1/2.

Theorem 6. There is a probabilistic QIM M learning U7 with probability 47 with 6
queries.
Proof. There are 7 possibilities to choose a subset of 6 points from the 7 points of

the Fano plane. So the desired probabilistic QIM M branches its computation in 7
branches corresponding to the 7 dierent subset of size 6 of the points of the Fano
plane. In each branch all 6 points are queried. If the QIM M nds a line (i, j, j) in theFano plane such that all points of it have the same color, e.g., f (i) = f (j) = f (k) = 3s ,it outputs s. By denition of the class U7 the result is a correct program computing
the function f . Otherwise, the QIM M aborts the computation path.
It remains to analyze the probability of success. In the worst-case there is only asingle monochromatic line (i, j, j) in the Fano plane. So, there are 4 subsets of size 6
containing the points of this line and there are 3 subsets of size 6 which miss at least
one point of this line. Hence, the probability of success is 4/7.
Next, we deal with the minimum number of queries needed by a probabilistic
QIM M to achieve a probability greater than 0.

Theorem 7. There is a probabilistic QIM M learning U7 with probability 17 with 3
queries.
Proof. The algorithm starts with branching its computation into 7 possibilities cor-

responding to the 7 lines in Fano plane. Each branch is reached with probability
1/7. In each branch, all 3 points i, j, k are queried. If f (i), f (j), f (k) are not of thesame color then the computation path is aborted. If they are of the same color, e.g.,f (i) = f (j) = f (k) = 2s , then s is output. By denition of the class U7 the result isa correct program computing the function f .
However, the situation for the remaining number of queries is not yet completely
analyzed. We may be interested to know what probability of success can be achievedby asking 4 or 5 queries. So far, we have only the following theorem.

Theorem 8. There is a probabilistic QIM M learning U7 with probability 27 with 5
queries.
Proof. The desired QIM M will use its 5 queries to query in each branch two lines of

the Fano plane. Since any two lines of the Fano plane share one point, it is clear that
5 queries are sucient to query two lines. As above, if a line (i, j, k) of the Fano plane
is found such that all points of it have the same color, e.g., f (i) = f (j) = f (k) = 2s ,then s is output. Otherwise the branch is aborted.

14

Rūsiņš Freivalds and Thomas Zeugmann

There are 21 possibilities to choose any two lines of the Fano plane. Again, in theworst-case there is only one line in the Fano plane such that all its points have thesame color. So we may choose this line and any other line of the remaining 6 lines.
This gives 6 successful branches, while the remaining 15 branches are aborted. Hence,the probability of success is 6/21 = 2/7.

Theorem 9. For every prime number p, there is a p-ultrametric QIM M learning U7
with p-probability 1 with 2 queries.
Proof. The desired QIM M branches its computation path into 7 branches at theroot, where each branch corresponds to exactly one line of the Fano plane. The
corresponding nodes are denoted by `1 , . . . , `7 , respectively, in Figure 2 below.
We assign to each edge the amplitude 1/7. At the second level, each of thesebranches is branched into 3 subbranches each of which is assigned the amplitude 1/3.
So far we have at level three 21 nodes denoted by v1 , . . . , v21 (cf. Figure 2).

1/7

1/7

`1
1/3

`2
1/3

1/3

v3

v4

1/3
v1

v2

1/7

`3
1/3

1/3

v6

v7

1/3
v5

1/7
`4
1/3

1/3

v9

v10

1/3
v8

1/7
`5

1/3

1/3

v12

v13

1/3
v11

1/7
`6
1/3

1/3

v15

v16

1/3
v14

1/7
`7
1/3

1/3

v18

v19

1/3
v17

1/3
1/3
v20

v21

Figure 2: The rst three levels of the DAG representing the computation of the QIM

For each of these nodes we formulate two queries. Let v be such that its father
node corresponds to the line containing the point i, j, k of the Fano plane, where weorder these points such that i < j < k . If v is the leftmost node then we query (i, j), if
v is the middle node then we query (j, k) and if v is the rightmost node then we query(i, k). Every triple of nodes having the same father share a register, say rijk . Initially,
the register contains the value ↑ which stands for no output. The node activatedwhen reached in the computation path sends the following value to rijk . After having
received the answer to its queries, e.g., f (i) = 2s and f (j) = 3t then it writes 0 in
rijk , and if the values coincide, e.g., f (i) = 3t and f (j) = 3t , then it writes t in rijk .
Looking at any triple of nodes having a common father at the third level, then wenote that the following 8 cases may occur as answer. We use again the correspondingcolors, where R and B are used as shortcuts for RED and BLUE, respectively.
Thus, we need for each node at the third level 8 outgoing edges as the table aboveshows. If the edge corresponds to a pair (R, R) or (B, B) then we assign the amplitude
1/2 and otherwise the amplitude −1/4. Note that sum of these amplitudes is again 1.
Finally, we join each triple as shown in table above into one node, e.g., the edges
corresponding to (B, B), (B, R), and (B, R) are joined. If the total amplitude of such

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms(i, j)(j, k)(i, k)(B, B) (B, R) (B, R)(B, B) (B, B) (B, B)(B, R) (R, R) (B, R)(B, R) (R, B) (B, B)

15(i, j)(j, k)(i, k)(R, R) (R, B) (R, B)(R, R) (R, R) (R, R)(R, B) (B, B) (R, B)(R, B) (B, R) (R, R)

Figure 3: The 8 cases of possible answers for any triple of nodes having a common
father at the third level.

a node at the third level is dierent from zero, then the node produces as output
the value stored in register rijk . Figure 4 shows the part of the DAG for the queries
performed for the rst line of the Fano plane, i.e., for the line (0, 1, 3). So this partstarts at the nodes v1 , v2 and v3 shown in Figure 2. For the sake of readability, weshow the queries asked at each node, i.e., (0, 1) at node v1 , (1, 3) at node v2 , and (0, 3)
at node v3 . A blue edge denotes the case that both answers to the queries asked at
the corresponding vertex returned a value of f indicating that the related nodes ofthe rst line of the Fano plane are blue. This result is then propagated along the blueedges. Analogously, a red edge indicates that both answers corresponded to a red nodeof the rst line of the Fano plane. If the answers returned function values indicatingthat the colors of the queried nodes of the rst line of the Fano plane have dierent
colors then the edge is drawn in black. Blue and red edges have the amplitude 1/2
and the black edges have the the amplitude −1/4.
(0, 1)(1, 3)(0, 3)

Figure 4: The part of the DAG representing the computation of the QIM M for theline (0, 1, 3) starting at the nodes of the third level

It remains to show that the QIM M has the desired properties. By construction,
at every computation path exactly two queries are asked.
Next, by Denition 6 it is obvious that the total amplitude of each node at thesecond level is 1/21. Next, we consider any node at the third level. If a triple (B, B),(B, B), and (B, B) is joined then the total amplitude is

1 1
1 1
1
1 1
· +
· +
· =
.
21 2 21 2 21 2
2·7
The same holds for (R, R), (R, R), and (R, R) (cf. Denition 6). Figure 4 shows thecorresponding leaves in blue and red, respectively.

16

Rūsiņš Freivalds and Thomas Zeugmann

If a triple has a dierent form than considered above, e.g., (B, B), (B, R), and(B, R) then, again by Denition 6, we have for the total amplitude

1 1
1 1
1 1
· −
· −
· =0.
21 2 21 4 21 4
One easily veries that all remaining total amplitudes are also 0. The corresponding
leaves are drawn in black in Figure 4. Finally, we perform the measurement. Clearly,
for each leaf which has a total amplitude 0 the measurement results in k0kp = 0. For1
the remaining nodes we obtain k 2·7
kp which is 1 for every prime p such that p ∈/ {2, 7}.
1
1
If p = 2 then we have k 2·7 k2 = 2 and for p = 7 we directly get k 2·7 k7 = 7.
By Lemma 1 there must be at least one line such that all nodes have the samecolor, and by Lemma 2 it is not possible to have a line colored in RED and a line
colored in BLUE simultaneously. So at least one node has p-probability at least 1,
and the result output is correct in accordance with the denition of the class U7 .
If there are several lines colored in the same color then distinct but correct results
may be produced, since any two lines share exactly one point. Thus, the resulting
p-probability is always no less than 1.
The idea of this paper can be extended to obtain even more spectacular advantagesof ultrametric algorithms over nondeterministic ones. In order to show this let us recall
the general denition of a nite projective plane.

Denition 10. A nite projective plane of order n, where n ∈ N, n > 0, is acollection of n2 + n + 1 lines and n2 + n + 1 points such that(1) every line contains n + 1 points,(2) every point is on n + 1 lines,(3) any two distinct lines intersect at exactly one point, and(4) any two distinct points lie on exactly one line.
So, the interesting question is whether or not there are innitely many numbers nsuch that there is a projective plane of order n. It is known that for every prime
power q there exists a projective plane of order q (cf. [6]).
This allows us to construct a class Um of recursive functions similar to the class U7
above. The counterpart of Lemma 1 does not hold (cf. Figure 5) but this demands
only an additional requirement for the function in the class to have a line colored in
one color but not simultaneously two lines colored in opposite colors. Formally wedene the class Um as follows. Let q be a prime power, let m =df q 2 + q + 1, let Pm bethe nite projective plane of order q obtained from the proof given in [6], and let ϕ
be any xed Gödel numbering of P .
The class Um is the set of all functions f ∈ R satisfying the following properties:

17

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms(1) for every x ∈ {0, 1, . . . , m − 1} the value f (x) equals either 2s or 3t , wheres, t ∈ N and s, t ≥ 1,(2) if 0 ≤ x1 < x2 ≤ m − 1, f (x1 ) = 2s and f (x2 ) = 2t then f (x1 ) = f (x2 ),(3) if 0 ≤ x1 < x2 ≤ m − 1, f (x1 ) = 3s and f (x2 ) = 3t then f (x1 ) = f (x2 ),(4) either there is a line (x1 , . . . , xq+1 ) in the projective plane Pm such that f (x1 ) =f (x2 ) = · · · = f (xq+1 ) = 2k and ϕk = f or there is a line (x1 , . . . , xq+1 ) in the
projective plane Pm such that f (x1 ) = f (x2 ) = · · · = f (xq+1 ) = 3k and ϕk = f .
Next, let us provide an example showing that Lemma 1 does not generalize to allprime powers q and the corresponding nite projective planes Pm , where m = q 2 +q+1.
Instead of drawing a geometrical gure, we shall represent the nite projective planeby an (m × m)-incidence matrix A. The rows of this matrix represent the points andthe columns represent the points. Let A = (aij ) i=1,...,m ; then entry aij = 1 if point i
j=1,...,mis at line j and aij = 0 otherwise.

P1
P2
P3
P4
P5
P6
P7
P8
P9
P10
P11
P12
P13

L1
1
1
1
1
0
0
0
0
0
0
0
0
0

L2
1
0
0
0
1
1
1
0
0
0
0
0
0

L3
1
0
0
0
0
0
0
1
1
1
0
0
0

L4
1
0
0
0
0
0
0
0
0
0
1
1
1

L5
0
1
0
0
1
0
0
1
0
0
1
0
0

L6
0
1
0
0
0
1
0
0
1
0
0
1
0

L7
0
1
0
0
0
0
1
0
0
1
0
0
1

L8
0
0
1
0
1
0
0
0
0
1
0
1
0

L9
0
0
1
0
0
1
0
1
0
0
0
0
1

L10
0
0
1
0
0
0
1
0
1
0
1
0
0

L11
0
0
0
1
1
0
0
0
1
0
0
0
1

L12
0
0
0
1
0
1
0
0
0
1
1
0
0

L13
0
0
0
1
0
0
1
1
0
0
0
1
0

Figure 5: A coloring of a nite projective plane of order 3 which does not have amonochromatic line
Using an incidence matrix A the conditions of Denition 10 directly translate into:(1) A has constant row sum q ,(2) A has constant column sum q ,(3) the scalar product of any two distinct row vectors of A is 1,(4) the scalar product of any two distinct column vectors of A is 1.

18

Rūsiņš Freivalds and Thomas Zeugmann

So the additional problem arising for all prime powers q > 2 is to nd a suitable
coloring on which the denition of the corresponding functions from Um can be based.
It is straightforward to generalize Theorem 1 and Theorem 4.

Theorem 10. Let q be any prime power, let m = q2 + q + 1, and let Um ⊆ R be thecorresponding class of recursive functions. Then there is a deterministic QIM M thatlearns the class Um with m queries.
Proof. The desired QIM M queries the points 0, 1, . . . , m − 1. After having received

f (0), f (1), f (2), . . . , f (m − 1), it checks at which line all points have the same color,and outputs the ϕ-program corresponding to this line. Note that by the denition of
the class Um there is at least one such line and there cannot be two lines colored indierent colors. If there is more than one line at which all points have the same color
then the function values for the points on these monochromatic lines must coincide(cf. Conditions (2) and (3) of the denition of the class Um ). So, by the denition of
the class Um one can directly output a correct ϕ-program for the target function f .

Unfortunately, so far we cannot show that every deterministic QIM M needs mqueries to learn the class Um . However, we conjecture that there is no deterministic
QIM M that learns the class Um with m − 1 queries.

Theorem 11. Let q be any prime power, let m = q2 + q + 1, and let Um ⊆ R be thecorresponding class of recursive functions. Then there is a nondeterministic QIM M
learning Um with q + 1 queries.
Proof. The QIM M starts with a nondeterministic branching of the computation
into m possibilities corresponding to the m lines in the nite projective plane Pm .
In each case, all q + 1 points i1 , . . . , iq+1 of the line corresponding to the branch are
queried. If f (i1 ), . . . , f (iq+1 ) are not of the same color then the computation path isaborted. If they are of the same color, e.g., f (i1 ) = 2k1 , . . . , f (iq+1 ) = 2kq+1 , then thedenition of the class Um ensures that ki1 = · · · = kq+1 and the QIM M outputs ki1
which is a correct program computing the target function f .
Note that the nondeterministic QIM M learning Um needs q 2 less queries than thedeterministic QIM from Theorem 10.

Theorem 12. Let q be any prime power, let m = q2 + q + 1, and let Um ⊆ R be thecorresponding class of recursive functions. Then there is no nondeterministic QIM M
learning Um with q queries.
Proof. We show the theorem indirectly. Suppose to the contrary that there is a

nondeterministic QIM M learning Um with q queries. For the sake of presentation,
we illustrate the construction for the case that q = 3.

19

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

First, we construct a suitable coloring of Pm . Here we use an idea from Jepsen [22].
We x the point P1 and color it RED. Let L1 , . . . , Lq+1 be the lines containing P1 .
Now we color all points contained in L2 , . . . , Lq+1 except P1 by BLUE, and the points
contained in L1 with RED. The denition of a nite projective plane of order q ensuresthat L1 and L2 have exactly one point in common. By our construction this is P1 .
Thus L2 must contain q points not contained in L1 . The same holds for L2 and L3 ,i.e., L3 must have q points neither contained in L1 nor contained in L2 . Iterating
this argument shows that Lq+1 must contain q points not contained in any of the lines
L1 , . . . , Lq . Thus gives a total of q +1 points (contained in L1 ) and q times q points for
L2 , . . . , Lq+1 , i.e., q + 1 + q 2 points. Hence, we must have colored all points. Figure 6
shows the constructed coloring for the case q = 3. By construction, this coloring has

P1
P2
P3
P4
P5
P6
P7
P8
P9
P10
P11
P12
P13

L1
1
1
1
1
0
0
0
0
0
0
0
0
0

L2
1
0
0
0
1
1
1
0
0
0
0
0
0

L3
1
0
0
0
0
0
0
1
1
1
0
0
0

L4
1
0
0
0
0
0
0
0
0
0
1
1
1

L5
0
1
0
0
1
0
0
1
0
0
1
0
0

L6
0
1
0
0
0
1
0
0
1
0
0
1
0

L7
0
1
0
0
0
0
1
0
0
1
0
0
1

L8
0
0
1
0
1
0
0
0
0
1
0
1
0

L9
0
0
1
0
0
1
0
1
0
0
0
0
1

L10
0
0
1
0
0
0
1
0
1
0
1
0
0

L11
0
0
0
1
1
0
0
0
1
0
0
0
1

L12
0
0
0
1
0
1
0
0
0
1
1
0
0

L13
0
0
0
1
0
0
1
1
0
0
0
1
0

Figure 6: The constructed coloring of a nite projective plane of order 3
exactly one monochromatic line, i.e., all points of line L1 are colored RED.
Since the QIM M is supposed to learn Um with q queries there must be at least one
branch in its computation where some subset of {0, 1, . . . , q} (corresponding to thepoints P1 , . . . , Pq+1 ) of size at most q is queried and where the QIM M then makes
the corresponding correct program as output. If the QIM M does not have such a
branch then we are already done.
Let i be a point from {0, 1, . . . , q} which is not queried. Now, we change thecolor of point Pi+1 from RED to BLUE. Then we obtain a new coloring which has q
many lines colored BLUE. This follows again directly from the denition of a nite
projective plane. But the values returned to the QIM M at the branch considered
before remain unchanged and so it must output the same program as before which is,
however, for the current coloring no longer correct. Hence, it violates Condition (2)of Denition 1, a contradiction.
Next, we turn our attention to probabilistic QIM.

20

Rūsiņš Freivalds and Thomas Zeugmann

Theorem 13. Let q be any prime power, let m = q2 + q + 1, and let Um ⊆ R be
the corresponding class of recursive functions. Then there is a probabilistic QIM M
q2
with m − 1 queries.
learning Um with probability q2 +q+1m
Proof. Since m−1= m, there are m possibilities to choose a subset of m − 1 points

from the m points of a nite projective plane Pm . So the desired probabilistic QIM M
branches its computation into m branches corresponding to the m dierent subset ofsize m − 1 of the points of the plane Pm . In each branch all m − 1 points are queried.
If the QIM M nds a line (i1 , . . . , iq+1 ) in the plane Pm such that all points of it havethe same color, e.g., f (i1 ) = · · · = f (iq+1 ) = 3k , it outputs k . By denition of theclass Um the result is a correct program computing the function f . Otherwise, the
QIM M aborts the computation path.
So, it remains to analyze the probability of success. In the worst-case there is only
single monochromatic line (i1 , . . . , iq+1 ) in the plane Pm . There are q 2 subsets of sizem − 1 containing the points of this monochromatic line and there are m − q 2 = q + 1
subsets of size m − 1 which miss at least one point of this line. Hence, the probabilityof success is q 2 /(q 2 + q + 1).
It should be noted that the probability established in Theorem 13 tends to 1 if mtends to innity.
Next it is easy to see that Theorem 7 generalizes as follows. The proof is mutatis
mutandis the same.

Theorem 14. Let q be any prime power, let m = q2 + q + 1, and let Um ⊆ R be
the corresponding class of recursive functions. Then there is a probabilistic QIM M
learning Um with probability m1 with q + 1 queries.
Unfortunately, so far we could not determine the minimum number of queries
needed to achieve a probability exceeding 1/2.
So, it remains to nd out whether or not p-ultrametric QIMs do also achieve an
advantage over nondeterministic QIM in the general case. Though so far we could notcompletely solve this problem, we succeeded to achieve partial results. Let us startby looking at the case that q = 3. Then we obtain the class U13 which is dened byusing the projective plane P13 . We have 13 lines and each line consists of precisely
four points. However, as the following theorem shows, there is a p-ultrametric QIM
that learns U13 two queries.

Theorem 15. For every prime number p, there is a p-ultrametric QIM M learning
the class U13 with p-probability 1 with 2 queries.
Proof. The desired QIM M branches its computation path into 13 branches at theroot, where each branch corresponds to exactly one line of the projective plane P13 . We
assign to each edge the amplitude 1/13. Now, the idea to reduce the number of queries

21

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

necessary is as follows. First, instead of asking 4 queries as the nondeterministic QIM
did, we could ask the leftmost three points and the rightmost three points of thecorresponding line, respectively. Therefore, we branch the computation at the second
level into two subbranches each of which is assigned the amplitude 1/2. In the left
branch the leftmost three points are considered and in the right branch the rightmost
three points of the corresponding line are considered. Thus, at the second level wehave a total of 26 nodes.
Since we already know how to replace 3 queries by 2 queries, at the third level eachbranch is branched into three subbranches. That is, the sub-DAG shown in Figure 4
is plugged in here. The amplitudes assigned to the edges in the sub-DAGs are thesame as before. So for each line we have two branches which consist of the plugged
in sub-DAGs. Each of these sub-DAGs has 8 leaves. However, only two leaves has atotal amplitude which is not zero, i.e., the blue leave and the red leave.
Now, we join the two corresponding blue leaves and the two corresponding red
leaves. Here each outgoing edge has the amplitude 1. Finally, the new leave outputs
the value stored in register ri` j` k` , where the subindex ` indicates the always the left
register is used. Figure 7 shows the corresponding sub-DAG for the rst line. As
shown in Figure 5, the rst line contains the points P1 , P2 , P3 , P4 . For the sake ofpresentation, these points are denoted by 1, 2, 3, 4 for short in Figure 7.
`1
1/2

1/3

1/2

1/3

1/3

1/3

1/3
(1, 2)(2, 3)

1

1/3(1, 3)

1(2, 3)

1(3, 4)(2, 4)

1

Figure 7: The part of the DAG representing the computation of the QIM M for theline (0, 1, 3, 4) starting at the node of the second level
The labels at the new edges show the new amplitudes.
It remains to show that the QIM M has the desired properties. By construction,
at every computation path exactly two queries are asked.
In accordance with Denition 6 we directly see that each node at the second levelhas the total amplitude 1/13 and the total amplitude of each node at the third level22

Rūsiņš Freivalds and Thomas Zeugmann

is1/26. Therefore, each node at the fourth level has the total amplitude 1/78. By
Denition 6 we thus obtain for the blue nodes and the red nodes at the fth level thefollowing total amplitude

1 1
1 1
1
1 1
· +
· +
· =
.
78 2 78 2 78 2
4 · 13All the black nodes at the fth level have the total amplitude 0, since for every black
node there are always two black edges pointing to it and either one blue edge or one
red edge entering it. Thus, we have

1 1
1 1
1 1
· −
· −
· =0.
78 2 78 4 78 4
1
Finally, the blue node and the red node at level six have the total amplitude 2·13
. Finally, we perform the measurement. Clearly, for each leaf which has a total amplitude
1
0 the measurement results in k0kp = 0. For the remaining leaves we obtain k 2·13kp
1which is 1 for every prime p such that p ∈/ {2, 13}. If p = 2 then we have k 2·13 k2 = 2
1
and for p = 13 we obtain k 2·13 k7 = 13.

By construction there must be at least one line such that all nodes have the samecolor, and there is exactly one monochromatic line in the projective plane P13 used
to dene the class U13 (cf. Property (4) of the Denition of Um ). So at least one
node has p-probability at least 1. Furthermore, since two points are queried twice,
it cannot happen that the leftmost three points are blue (or red) and the rightmost
three points are red (or blue). Therefore, the result output is correct by the denitionof the class U13 .
We note that Theorem 15 directly generalizes to the class U21 , i.e., for the casethat q = 22 . In this case the projective plane P21 has 21 lines and 21 points andeach line contains exactly 5 points. Consequently, we can use exactly the same proof
as we did for the class U13 , since the leftmost three points and the rightmost threepoints still share one point which is then queried twice. That is, we directly obtainthe following corollary.

Corollary 1. For every prime number p, there is a p-ultrametric QIM M learning
the class U21 with p-probability 1 with 2 queries.
Consequently, it seems that this idea can be pushed even further. If q = 5 thenin the projective plane P31 each line has exactly 6 points. One could then try to ask
the leftmost 4 pints and the rightmost 4 points and to use Theorem 15 to reduce 4
queries to 2 queries. However, it is not clear how far such a recursive application
may be applied. The obvious diculty is based on the construction of the classes
Um on projective planes Pm . Since we only know projective planes to exist if q is aprime power, the recursive application may stop somewhere and to determine the fullpotential of the ideas developed so far is a future research subject.

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

23

4. Conclusions

In this paper we have studied active learning of classes of recursive functions fromvalue queries. We compared the query complexity of deterministic, nondeterministic,
probabilistic, and ultrametric QIM and showed the somehow unexpected result that pultrametric QIM can learn classes of recursive function with signicantly fewer queries
than nondeterministic, probabilistic QIM can do.
The situation resembles quantum computation. In quantum computation we also
nd the usage of amplitudes and of measurements to transform amplitudes into real
numbers. Quantum computation is famous for algorithms unimaginable in classicalimplementation. For instance, there exists a quantum query algorithm computing theBoolean function x1 ⊕x2 asking only one query but computing the binary xor-function
function with probability 1. The essence of this algorithm is the quantum parallelismof the computation process (cf. Bernstein and Vazirani [5]). One computation pathqueries the value of x1 , the other computation path queries the value of x2 , and the
addition of the amplitudes results in the probability 1 for the correct result and in
the probability 0 for the wrong result.
Our main result (Theorem 9) is based on the same idea. So, it remains to explore
further problems for which ultrametric algorithms can achieve a substantial advantage
over nondeterministic algorithm or probabilistic algorithms.

References[1] Andris Ambainis, Kalvis Apstis, Rusin² Freivalds, and Carl H. Smith. Hierarchies of probabilistic and team FIN -learning. Theoret. Comput. Sci., 261(1):91
117, 2001.
[2] Andris Ambainis and Juris Smotrovs. Enumerable classes of total recursive functions: Complexity of inductive inference. In Algorithmic Learning Theory, 4thInternational Workshop on Analogical and Inductive Inference, AII '94, 5th International Workshop on Algorithmic Learning Theory, ALT '94, Reinhardsbrunn
Castle, Germany, October 1994, Proceedings, volume 872 of Lecture Notes in
Articial Intelligence, pages 1025. Springer-Verlag, 1994.

[3] Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319342,
1988.
[4] Kaspars Balodis, Anda Berina, Kristne Cpola, Maksims Dimitrijevs, Janis
Iraids, Karlis Jerins, Vladimirs Kacs, Janis Kalejs, Rihards Kril²auks, Karlis
Lukstin², Reinholds Raumanis, Irina Scegulnaja, Natalija Somova, Anna Vanaga,
and Rusin² Freivalds. On the state complexity of ultrametric nite automata.
unpublished manuscript, 2013.

24

Rūsiņš Freivalds and Thomas Zeugmann[5] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):14111473, 1997.
[6] Thomas Beth, Dieter Jungnickel, and Hans Lenz. Design Theory. Bibliographisches Institut, Wissenschaftsverlag, Mannheim, Wien, Zürich, 1985.
[7] Nader H. Bshouty. Exact learning from membership queries: Some techniques,
results and new directions. In Sanjay Jain, Rémi Munos, Frank Stephan, andThomas Zeugmann, editors, Algorithmic Learning Theory, 24th International
Conference, ALT 2013, Singapore, October 6-9, 2013, Proceedings, volume 8139
of Lecture Notes in Articial Intelligence, pages 3352, Berlin, Heidelberg, New
York, 2013. Springer.
[8] François Denis, Aurélien Lemay, and Alain Terlutte. Learning regular languages
using non deterministic nite automata. In Grammatical Inference: Algorithms

and Applications, 5th International Colloquium, ICGI 2000, Lisbon, Portugal,
September 11-13, 2000, Proceedings, volume 1891 of Lecture Notes in ArticialIntelligence, pages 3950. Springer-Verlag, 2000.

[9] B. Dragovich and A. Yu. Dragovich. A p-adic model of DNA sequence and genetic
code. p-Adic Numbers, Ultrametric Analysis, and Applications, 1(1):3441, 2009.
[10] Rusin² Freivalds. Inductive inference of recursive functions: Qualitative theory.
In Baltic Computer Science, volume 502 of Lecture Notes in Computer Science,
pages 77110. Springer, Berlin, 1991.
[11] Rusin² Freivalds. Ultrametric automata and Turing machines. In Andrei
Voronkov, editor, Turing-100, volume 10 of EPiC Series, pages 98112. EasyChair, 2012.
[12] Rusin² Freivalds, Janis Barzdin², and Karlis Podnieks. Inductive inference ofrecursive functions: Complexity bounds. In Baltic Computer Science, volume
502 of Lecture Notes in Computer Science, pages 111155. Springer, Berlin, 1991.
[13] Rusin² Freivalds, Em Kinber, and Carl H. Smith. On the impact of forgetting
on learning machines. J. ACM, 42(6):11461168, 1995.
[14] Pedro García, Manuel Vázquez de Parga, Gloria I. Álvarez, and José Ruiz. Learning regular languages using nondeterministic nite automata. In Implementation

and Applications of Automata, 13th International Conference, CIAA 2008, San
Francisco, California, USA, July 21-24, 2008. Proceedings, volume 5148 of Lecture Notes in Computer Science, pages 92101. Springer, 2008.

[15] William Gasarch, Em Kinber, Mark Pleszkoch, Carl Smith, and Thomas Zeugmann. Learning via queries, teams, and anomalies. Fundamenta Informaticae,
23(1):6789, 1995. Shorter version in Third Annual Workshop on Computational
Learning Theory, 1990, pages 327-337, published by Morgan Kaufman.

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

25[16] William Gasarch and Carl H. Smith. A survey of inductive inference with anemphasis on learning via queries. In Andrea Sorbi, editor, Complexity, Logic, andRecursion Theory, volume 187 of Lecture Notes in Pure and Applied Mathematics,
pages 225260. Marcel Dekker, Inc., 1997.
[17] William I. Gasarch and Carl H. Smith. Learning via queries. J. ACM, 39(3):649
675, 1992.
[18] E. Mark Gold. Language identication in the limit. Inform. Control, 10(5):447
474, 1967.
[19] Fernando Quadros Gouvea. p-adic Numbers:
Springer, Berlin, second edition, 1983.

An Introduction (Universitext).

[20] Inguna Greitane. Probabilistic inductive inference of indices in enumerable classesof total recursive functions. In Analogical and Inductive Inference, International
Workshop AII '89, Reinhardsbrunn Castle, GDR, October 1989, Proceedings, volume 397 of Lecture Notes in Articial Intelligence, pages 277287. Springer, 1989.
[21] Juraj Hromkovi£. Design and Analysis of Randomized Algorithms. Introduction
to Design Paradigms. Springer, Berlin, Heidelberg, 2005.
[22] Charles H. Jepsen. On colorings of nite projective planes. Discrete Mathematics,
63(1):9596, 1987.
[23] Karlis Jerin², Kaspars Balodis, Rihards Kri²lauks, Kristne Cpola, and Rusin²
Freivalds. Ultrametric query algorithms. unpublished manuscript, 2012.
[24] Andrei Khrennikov. Non-Archimedean Analysis: Quantum Paradoxes, Dynamical Systems and Biological Models. Kluwer Academic Publishers, 1997.
[25] Em Kinber and Thomas Zeugmann. One-sided error probabilistic inductive
inference and reliable frequency identication. Inform. Comput., 92(2):253284,
1991.
[26] Em B. Kinber and Thomas Zeugmann. Rened query inference. In Analogicaland Inductive Inference, International Workshop AII '89, Reinhardsbrunn Castle, GDR, October 1989, Proceedings, volume 397 of Lecture Notes in ArticialIntelligence, pages 148160. Springer-Verlag, 1989.

[27] Neal Koblitz. p-adic Numbers, p-adic Analysis, and Zeta-Functions. Springer,
Berlin, second edition, 1984.
[28] S. V. Kozyrev. Ultrametric analysis and interbasin kinetics. In 2nd International
Conference on p-Adic Mathematical Physics, Belgrade, Serbia and Montenegro,
15 - 21 September 2005, volume 826 of American Institute of Physics Conference
Proceedings, pages 121128, 2006.

26

Rūsiņš Freivalds and Thomas Zeugmann[29] Steen Lange, Thomas Zeugmann, and Sandra Zilles. Learning indexed familiesof recursive languages from positive data: A survey. Theoret. Comput. Sci., 397(13):194232, 2008. Special issue Forty Years of Inductive Inference: Dedicated to
the 60th Birthday of Rolf Wiehagen.
[30] Bruce E. Meserve. Fundamental Concepts of Geometry. Dover Publications, New
York, 1983.
[31] Léa Meyer. Probabilistic language learning under monotonicity constraint. Theoret. Comput. Sci., 185(1):81128, 1997.
[32] Léa Meyer. Comparing the power of probabilistic learning and oracle identication under monotonicity constraints. In Algorithmic Learning Theory, 9thInternational Conference, ALT '98, Otzenhausen, Germany, October 1998, Proceedings, volume 1501 of Lecture Notes in Articial Intelligence, pages 306320.
Springer, 1998.

[33] Léa Meyer. Aspects of complexity of probabilistic learning under monotonicity
constraints. Theoret. Comput. Sci., 268(2):275322, 2001.
[34] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum
Information. Cambridge University Press, 2000.
[35] Alexander Ostrowski. Über einige Lösungen der Funktionalgleichung ϕ(x)·ϕ(y) =ϕ(xy). Acta Mathematica, 41(1):271284, 1916.
[36] L. Pitt. Probabilistic inductive inference. J. ACM, 36(2):383433, 1989.
[37] Leonard Pitt and Carl H. Smith. Probability and plurality for aggregations oflearning machines. Inform. Comput., 77(1):7792, 1988.
[38] Hartley Rogers, Jr. Theory of Recursive Functions and Eective Computability.
McGraw-Hill, 1967. Reprinted, MIT Press 1987.
[39] Raymond M. Smullyan. Theory of formal systems, volume 47 of Annals of Mathematics Studies. Princeton University Press, Princeton, New Jersey, USA, 1961.
[40] V. S. Vladimirov, I. V. Volovich, and E. I. Zelenov. P-Adic Analysis and Mathematical Physics. World Scientic, Singapore, 1994.
[41] Yu-Chieh Wu, Yue-Shi Lee, Jie-Chi Yang, and Show-Jane Yen. An integrated
deterministic and nondeterministic inference algorithm for sequential labeling. In

Information Retrieval Technology 6th Asia Information Retrieval Societies Conference, AIRS 2010, Taipei, Taiwan, December 1-3, 2010. Proceedings, volume6458 of Lecture Notes in Computer Science, pages 221230. Springer, 2010.

Active Learning of Classes of Recursive Functions by Ultrametric Algorithms

27[42] Thomas Zeugmann and Steen Lange. A guided tour across the boundaries
of learning recursive languages. In Algorithmic Learning for Knowledge-Based
Systems, volume 961 of Lecture Notes in Articial Intelligence, pages 190258.
Springer, 1995.
[43] Thomas Zeugmann and Sandra Zilles. Learning recursive functions: A survey.
Theoret. Comput. Sci., 397(1-3):456, 2008. Special issue Forty Years of Inductive
Inference: Dedicated to the 60th Birthday of Rolf Wiehagen.