Active Learning of Recursive Functions by
Ultrametric Algorithms?
Rusin² Freivalds1 and Thomas Zeugmann2
1

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

We study active learning of classes of recursive functions by
asking value queries about the target function f , where f is from thetarget class. That is, the query is a natural number x, and the answer
to the query is f (x). The complexity measure in this paper is the worstcase number of queries asked. We prove that for some classes of recursivefunctions ultrametric active learning algorithms can achieve the learning
goal by asking signicantly fewer queries than deterministic, probabilistic, and even nondeterministic active learning algorithms. This is the rstever example of a problem where ultrametric algorithms have advantages
over nondeterministic algorithms.
Abstract.

1

Introduction

Inductive inference has been studied intensively. Gold [12] dened learning in thelimit. The learner is a deterministic algorithm called inductive inference machine(abbr. IIM), and the objects to be learned are recursive functions. The information source are growing initial segments (x0 , f (x0 )), . . . , (xn , f (xn )) of orderedpairs of the graph of the target function f . It is assumed that every pair (x, f (x))
appears eventually. As a hypothesis space one can choose any Gödel numbering
ϕ0 , ϕ1 , ϕ2 , . . . of the set of all partial recursive functions over the natural numbers N = {0, 1, 2, . . .} (cf. [27]). If an i ∈ N is such that ϕi = f then we call i a
ϕ-program of f . An IIM, on input an initial segment (x0 , f (x0 )), . . . , (xn , f (xn )),has to output a natural number in which is interpreted as ϕ-program. An IIM
learns f if the sequence (in )n∈N of all computed ϕ-programs converges to a
program i such that ϕi = f .
Every IIM M learns some set of recursive functions which is denoted 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 research was supported by Grant No. 09.1570 from the Latvian Council of
Science and the Invitation Fellowship for Research in Japan S12052 by Japan Society
for the Promotion of ScienceActive Learning of Recursive Functions by Ultrametric Algorithms

247

the Gold model. This family is denoted by EX (short for explanatory) and it isdened by EX = {U | ∃M (U ⊆ EX(M )}. Many studies of inductive inference
set-theoretically compare the family EX with families that arise from consideringother models (cf., e.g., [30]). One such model is nite learning, where the IIM
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 no inuence on the order in which examples are presented. In contrast, thelearning model considered in the present paper is an active one. This model goesback to Angluin [3] and is called query learning. In the query learning model thelearner has access to a teacher that truthfully answers queries of a prespeciedtype. In this paper we only consider value queries. That is, the query is a natural
number x, and the answer to the query is f (x). A query learner is an algorithmic
device that, depending on the answers already received, either computes a newvalue query or it returns a hypothesis i and stops. As above, the hypothesis isinterpreted with respect to a xed Gödel numbering ϕ and it is required thatthe hypothesis returned satises ϕi = f . So active learning is nite learning.
As in the Gold [12] model, we are interested in active learners that can infer
whole classes of recursive functions. The complexity measure is then the worstcase number of queries asked to identify all the functions from the target class U .
We refer to any query learner as query inference machine (abbr. QIM).
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, 5, 11, 29] and probabilistic algorithms [14, 17, 21, 22, 25, 26].

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., a program j such that ϕj = f ;(2) at no computation path the QIM produces an incorrect result on f .
Denition 2. 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 [7] introduced a new type of indeterministic algorithms called
ultrametric algorithms. An extensive research on ultrametric algorithms of various kinds is performed by him and his co-authors (cf. [4, 15]). So, ultrametricalgorithms are a very new concept and their potential still has to be explored.
This is the rst paper showing a problem where ultrametric algorithms haveadvantages over nondeterministic algorithms. Ultrametric algorithms are very

248

R. Freivalds and T. Zeugmann

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 parameters. The usage of p-adic numbers as amplitudes and theability to perform measurements 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 [24] 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 absolutevalue. This result shows that using p-adic numbers was not merely one of many
possibilities to generalize 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 [28],chemistry [19] and molecular biology [6, 16] 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 ofprobabilities and later in terms of probabilistic combinations of amplitudes mostconveniently described by density matrices. Using p-adic numbers to describe
indeterminism allows to explore some aspects of indeterminism but, of course,
does not exhaust all the aspects of 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 torational and irrational numbers as measures for distances, and there is a psychological diculty to imagine 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 linearlyordered. This is why valuations and norms of p-adic numbers are considered.
The situation is similar in Quantum Computation (see [23]). Quantum amplitudes are complex numbers which also cannot be linearly ordered. The counterpart of valuation 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. We continue with a short description of p-adic numbers.
2

p-adic Numbers and Ultrametric Algorithms

Let p be an arbitrary prime number. A number a ∈ N with 0 ≤ a ≤ p − 1 iscalled a 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 writtenfrom left to right.

Active Learning of Recursive Functions by Ultrametric Algorithms

249

If n is a natural number, and n = ak−1 ak−2 · · · a1 a0 is its p-adic represenPk−1
tation, i.e., n = i=0 ai pi , where each ai is a p-adic digit, then we identify nwith the p-adic integer (ai ), where ai = 0 for all i ≥ k . This means that thenatural 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 the p-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 isallowed to have innitely many (!) digits to the left of the  p-adic point but
only a nite number of digits 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
can give rise to many dierent metric spaces. If X is a linear space over the real
numbers then 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.

Denition 3. 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 suchthat 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

ord7 x = +1

ord3 x = +2

ord11 x = −1

ord5 x = −2

ordp x = 0 for every prime p ∈/ {2, 3, 5, 7, 11} .

Denition 4. 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.

250

R. Freivalds and T. Zeugmann

For example, with x = 63/550 = 2−1 · 32 · 5−2 · 71 · 11−1 we obtain:

kxk2 = 2

kxk7 = 1/7

kxk3 = 1/9
kxk5 = 25

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 definitions 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 [13, 18].
We continue with ultrametric algorithms. In the following, p always denotes
a prime number. Ultrametric algorithms are described by nite directed acyclic
graphs (abbr. DAG), where exactly one node is marked as root. As usual, theroot does not have any incoming edge. Furthermore, every node having outdegree
zero is said to be a 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 padic number which we call amplitude. We require that the sum of all amplitudes
that correspond to v is 1. In order to determine the total amplitude along a
computation path, we need the following denition.

Denition 5. 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 , · · · , βk be 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
are joined, say m paths, then let α, γ2 , . . . , γm be the corresponding total
amplitudes of the predecessors of v` and let β` , δ2 , . . . , δm be the amplitudesof the incoming edges The total amplitude of the node v` is then dened tobe αβ` + γ2 δ2 + · · · + δm γm .
Note that the total amplitude is a p-adic integer.
We refer the reader to the proof of Theorem 7 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 aso-called measurement at the leaves of the corresponding DAG. Here by measurement we mean that 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 6. We say that a p-ultrametric algorithm produces a result m witha p-probability q if the sum of the p-probabilities of all leaves which correctly
produce the result m is no less than q.
Denition 7. We say that a p-ultrametric QIM learns a function f with ap-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 .

Active Learning of Recursive Functions by Ultrametric Algorithms
3

251

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 froma prespecied class U . The hypothesis space will always be a Gödel numbering ϕ (cf. [27]). 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
for several decades [2, 8, 10, 30]. In this paper we compare the query complexityof deterministic, nondeterministic, probabilistic, and ultrametric QIMs.
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, 7, 15] ultrametric algorithms also gave medium
complexity sometimes better and sometimes worse than probabilistic algorithms.
Our results in this paper show that, for learning recursive functions from value
queries, there are classes U of recursive functions such that ultrametric QIMs
have a much smaller complexity than even nondeterministic QIMs.
To show these results we use a combinatorial
0
structure called the Fano plane. It is one ofnite geometries (see [20]). The Fano planeconsists of seven points 0, 1, 2, 3, 4, 5, 6 and1
5seven 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
2i, j with i 6= j , in this geometry there isexactly one line that contains these points
3
4
6(cf. Figure 1). For any two dierent lines inthis geometry there is exactly one point conFig. 1. The Fano Plane
tained in these two lines. In our construction the points 0, 1, 2, 3, 4, 5, 6 are interpreted as colored in two colors RED andBLUE, respectively.

Lemma 1 ([20]). 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 ([20]). For any coloring of the Fano plane there cannot exist twolines colored in opposite colors.
Proof. Any two lines intersect at some point.

tu

To simplify notation, in the following we use P and R to denote the set of allpartial recursive functions and of all recursive functions of one variable over N,
respectively. Let ϕ be a Gödel numbering of P . We consider the following class
U7 of recursive functions. 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 ),252

R. Freivalds and T. Zeugmann(3) if 0 ≤ x1 < x2 ≤ 6, f (x1 ) = 3s and f (x2 ) = 3t , then f (x1 ) = f (x2 ),(4) there is a line (i, j, k) in the Fano plane such that f (i) = f (j) = f (k) = 2sand ϕs = f or there exists a line (i, j, k) in the Fano plane such that f (i) =f (j) = f (k) = 3t and ϕt = f .

Comment. In our construction of the class U7 the points 0, 1, 2, 3, 4, 5, 6 canbe interpreted as colored in two colors. Some points f (i) are such that f (i) = 2s
(these points are described below as RED) while some other points j are suchthat f (j) = 3t (these points are described below as BLUE). The properties of
the Fano plane ensure that for every such coloring in two colors there exists aline such that the three points on this line are colored in the same color, andthere cannot exist two lines colored in opposite colors.
Denition 8. 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 pointcolored 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 iscolored RED or BLUE.
Lemma 3. Given any partial coloring C of the points in the Fano plane assigning colors RED and BLUE to some but not all points such that no line contains
three points 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 BLUEfor the second function.

tuLemma 4. Given any partial coloring C of points in the Fano plane assigningcolors RED and BLUE to some but not all points such that no line contains 3
points in the 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. The assertions of the lemma can be shown by using the xed point theorem [27] and by using Lemma 3.

tuTheorem 1. There is a deterministic QIM M that learns the class U7 with 7
queries.

Active Learning of Recursive Functions by Ultrametric Algorithms

253

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,and outputs the ϕ-program corresponding to this line. Note that by Lemmata 1
and 2 there is precisely one such line. By the denition of the class U7 one candirectly output a correct ϕ-program for the target function f .
tuTheorem 2. There exists no deterministic QIM learning U7 with 6 queries.
Proof. The proof is by contradiction. Using Smullyan's double xed point theorem [27] one can construct two functions f and f˜ such that both are in U7 but
at least one of them is not correctly learned by the QIM M .
tu

Theorem 3. 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 thecomputation 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 . utTheorem 4. There is no nondeterministic QIM learning U7 with 2 queries.
Proof. By Lemma 4, there are two distinct functions in the class U7 with thesame values queried by the nondeterministic algorithm. The output is not correct
for at least one of them.
tu

Theorem 5. 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

corresponding 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 the same color then the computation path is aborted. If they are of thesame color, e.g., f (i) = f (j) = f (k) = 2s , then s is output. By denition of theclass U7 the result is a correct program computing the function f .
tuTheorem 6. There is a probabilistic QIM M learning U7 with probability 47
with 6 queries.
Theorem 7. 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

the root, where each branch corresponds to exactly one line of the Fano plane.
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).
For each of these nodes we formulate two queries. Let v be such that its father

254

R. Freivalds and T. Zeugmann

1/7

1/7

`1
1/3

`2
1/3

1/3

v3

v4

1/3
v1

v2

`3
1/3

1/3

v6

v7

1/3
v5

1/7

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

Fig. 2. The rst three levels of the DAG representing the computation of the QIM M

node corresponds to the line containing the point i, j, k of the Fano plane, where
we order these points such that i < j < k . If v is the leftmost node then wequery (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 sharea register, say rijk . Initially, the register contains the value ↑ which stands forno output. The node activated when 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, we
note that the following 8 cases may occur as answer. We use again the corresponding colors, where R and B are shortcuts for RED and BLUE, respectively.

(i, j) (j, k) (i, k) (i, j) (j, k) (i, k)(B, B) (B, R) (B, R) (R, R) (R, B) (R, B)(B, B) (B, B) (B, B) (R, R) (R, R) (R, R)(B, R) (R, R) (B, R) (R, B) (B, B) (R, B)(B, R) (R, B) (B, B) (R, B) (B, R) (R, R)
Thus, we need for each node at the third level 8 outgoing edges as the table
above shows. 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 theseamplitudes 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 a node at the third level is dierent from zero, then the node
produces as output the value stored in register rijk . Figure 3 shows the part of
the DAG for the queries performed for the rst line of the Fano plane, i.e., for theline (0, 1, 3). So this part starts at the nodes v1 , v2 and v3 shown in Figure 2. For
the sake of readability, we show 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 dashed (blue) edge denotes the casethat both answers to the queries asked at the corresponding vertex returned avalue of f indicating that the related nodes of the rst line of the Fano plane areblue. This result is then propagated along the dashed (blue) edges. Analogously,
a dotted (red) edge indicates that both answers corresponded to a red node of therst line of the Fano plane. If the answers returned function values indicating

Active Learning of Recursive Functions by Ultrametric Algorithms

255

that the colors of the queried nodes of the rst line of the Fano plane havedierent colors then the edge is drawn in black. Dashed (blue) and dotted (red)edges have the amplitude 1/2 and the black edges have the the amplitude −1/4.

(0, 1)(1, 3)




(0, 3)

  










 


Fig. 3. The part of the DAG representing the computation of the QIM M for the line
(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 5 it is obvious that the total amplitude of each node at
the second 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 5). Figure 3 shows
the corresponding leaves in a squared pattern and lined pattern, respectively.
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 5, 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. Finally, we
perform the measurement. Clearly, for each leaf which has a total amplitude 0
1
kp
the measurement results in k0kp = 0. For the remaining leaves we obtain k 2·7
1which is 1 for every prime p such that p ∈/ {2, 7}. If p = 2 then we have k 2·7 k2 = 2
1
k7 = 7.
and for p = 7 we get k 2·7
By Lemma 1 there must be at least one line such that all nodes have thesame color, and by Lemma 2 it is not possible to have a line colored in RED anda line colored in BLUE simultaneously. So at least one node has p-probability
at least 1, and the result output is correct by 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, theresulting p-probability is always no less than 1.
tu
The idea of this paper can be extended to obtain even more spectacularadvantages of ultrametric algorithms over nondeterministic ones. It is provedthat there exist nite projective geometries with n2 + n + 1 points and n2 + n + 1

256

R. Freivalds and T. Zeugmannlines such that any two lines have exactly one common point and any two points
lie on a common line. This allows us to construct a class Um of recursive functions
similar to the class U7 above, where m =df q 2 + q + 1 for any prime power q .
The counterpart of Lemma 1 does not hold but this demands only an additional
requirement for the function in the class to have a line colored in one color. Dueto the lack of space, we have to omit these results here, but refer the interested
reader to [9].
4Conclusions

In this paper we have studied active learning of classes of recursive functions
from value queries. We compared the query complexity of deterministic, nondeterministic, probabilistic, and ultrametric QIM and showed the somehow unexpected result that p-ultrametric QIM can learn classes of recursive function withsignicantly fewer queries than nondeterministic, probabilistic QIM can do.
References[1] Ambainis, A., Apstis, K., Freivalds, R., Smith, C.H.: Hierarchies of probabilistic
and team FIN -learning. Theoret. Comput. Sci. 261(1), 91117 (2001)[2] Ambainis, A., Smotrovs, J.: Enumerable classes of total recursive functions: Complexity of inductive inference. In: Algorithmic Learning Theory, 4th International
Workshop on Analogical and Inductive Inference, AII '94, 5th International Workshop on Algorithmic Learning Theory, ALT '94, Reinhardsbrunn Castle, Germany,
October 1994, Proceedings. Lecture Notes in Articial Intelligence, vol. 872, pp.
1025. Springer-Verlag (1994)[3] Angluin, D.: Queries and concept learning. Machine Learning 2(4), 319342 (1988)[4] Balodis, K., Berina, A., Cpola, K., Dimitrijevs, M., Iraids, J., Jerins, K., Kacs, V.,
Kalejs, J., Kril²auks, R., Lukstin², K., Raumanis, R., Scegulnaja, I., Somova, N.,
Vanaga, A., Freivalds, R.: On the state complexity of ultrametric nite automata.
unpublished manuscript (2013)[5] Denis, F., Lemay, A., Terlutte, A.: 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. Lecture Notes in Articial Intelligence, vol. 1891, pp. 3950.
Springer-Verlag (2000)[6] Dragovich, B., Dragovich, A.Y.: A p-adic model of DNA sequence and genetic
code. p-Adic Numbers, Ultrametric Analysis, and Applications 1(1), 3441 (2009)[7] Freivalds, R.: Ultrametric automata and Turing machines. In: Voronkov, A. (ed.)
Turing-100. EPiC Series, vol. 10, pp. 98112. EasyChair (2012)[8] Freivalds, R., Barzdin², J., Podnieks, K.: Inductive inference of recursive functions:
Complexity bounds. In: Baltic Computer Science, Lecture Notes in Computer
Science, vol. 502, pp. 111155. Springer, Berlin (1991)[9] Freivalds, R., Zeugmann, T.: Active learning of classes of recursive functions by
ultrametric algorithms. Tech. Rep. TCS-TR-A-13-68, Division of Computer Science, Hokkaido University (2013)

Active Learning of Recursive Functions by Ultrametric Algorithms

257[10] Freivalds, R., Kinber, E., Smith, C.H.: On the impact of forgetting on learning
machines. J. ACM 42(6), 11461168 (1995)[11] García, P., de Parga, M.V., Álvarez, G.I., Ruiz, J.: Learning regular languages
using nondeterministic nite automata. In: Implementation and Applications ofAutomata, 13th International Conference, CIAA 2008, San Francisco, California,
USA, July 21-24, 2008. Proceedings. Lecture Notes in Computer Science, vol.
5148, pp. 92101. Springer (2008)[12] Gold, E.M.: Language identication in the limit. Inform. Control 10(5), 447474(1967)[13] Gouvea, F.Q.: p-adic Numbers: An Introduction (Universitext). Springer, Berlin,second edn. (1983)[14] Greitane, I.: Probabilistic inductive inference of indices in enumerable classes of
total recursive functions. In: Analogical and Inductive Inference, International
Workshop AII '89, Reinhardsbrunn Castle, GDR, October 1989, Proceedings.
Lecture Notes in Articial Intelligence, vol. 397, pp. 277287. Springer (1989)[15] Jerin², K., Balodis, K., Kri²lauks, R., Cpola, K., Freivalds, R.: Ultrametric queryalgorithms. unpublished manuscript (2012)[16] Khrennikov, A.: Non-Archimedean Analysis: Quantum Paradoxes, Dynamical
Systems and Biological Models. Kluwer Academic Publishers (1997)[17] Kinber, E., Zeugmann, T.: One-sided error probabilistic inductive inference andreliable frequency identication. Inform. Comput. 92(2), 253284 (1991)[18] Koblitz, N.: p-adic Numbers, p-adic Analysis, and Zeta-Functions. Springer,
Berlin, second edn. (1984)[19] Kozyrev, S.V.: Ultrametric analysis and interbasin kinetics. In: 2nd International
Conference on p-Adic Mathematical Physics, Belgrade, Serbia and Montenegro,
15 - 21 September 2005. American Institute of Physics Conference Proceedings,
vol. 826, pp. 121128 (2006)[20] Meserve, B.E.: Fundamental Concepts of Geometry. Dover Publications, NewYork (1983)[21] Meyer, L.: Probabilistic language learning under monotonicity constraint. Theoret. Comput. Sci. 185(1), 81128 (1997)[22] Meyer, L.: Aspects of complexity of probabilistic learning under monotonicity
constraints. Theoret. Comput. Sci. 268(2), 275322 (2001)[23] Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information.
Cambridge University Press (2000)[24] Ostrowski, A.: Über einige Lösungen der Funktionalgleichung ϕ(x)·ϕ(y) = ϕ(xy).
Acta Mathematica 41(1), 271284 (1916)[25] Pitt, L.: Probabilistic inductive inference. J. ACM 36(2), 383433 (1989)[26] Pitt, L., Smith, C.H.: Probability and plurality for aggregations of learning machines. Inform. Comput. 77(1), 7792 (1988)[27] Rogers, Jr., H.: Theory of Recursive Functions and Eective Computability.
McGraw-Hill (1967), reprinted, MIT Press 1987.
[28] Vladimirov, V.S., Volovich, I.V., Zelenov, E.I.: P-Adic Analysis and Mathematical
Physics. World Scientic, Singapore (1994)[29] Wu, Y.C., Lee, Y.S., Yang, J.C., Yen, S.J.: 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. Lecture Notes in Computer
Science, vol. 6458, pp. 221230. Springer (2010)[30] Zeugmann, T., Zilles, S.: Learning recursive functions: A survey. Theoret. Comput.
Sci. 397(1-3), 456 (2008)