Ultrametric algorithms are similar to probabilistic algorithms but they describe the degree of indeterminism by p-adic numbers instead of real numbers. No wonder that only very few examples of advantages for ultrametric algorithms over probabilistic ones have been published up to now, and all they are slightly artificial. This paper considers ultrametric and probabilistic one-counter automata with two one-way input tapes. A language is found which is recognizable by ultrametric but not by probabilistic automata of this type.
Let f : f0; 1gn ! f0; 1g be a Boolean function. A query algorithm is an algorithm
for computing f (x1; : : : ; xn) that accesses x1; : : : ; xn by asking questions about
the values of xi. The complexity of a query algorithm is the maximum number
of questions that it asks. The query complexity of a function f is the minimum
complexity of a query algorithm correctly computing f . The theory of
computation studies various models of computation: deterministic, non-deterministic,
and probabilistic and quantum (see [
Deterministic, nondeterministic, probabilistic and quantum algorithms are
widely considered in literature (e.g., see survey [
Our model of the computing device is an automaton with two input tapes and one counter for memory. There is exactly one reading head on each input tape. These heads can move only one direction (or to stay at the same square of the tape). The input words are limited by special markers showing that the word has been completely read. The counter is empty at the beginning of the work.
A new type of indeterministic algorithms called ultrametric algorithms was
introduced in [
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 parameters. The usage of p-adic numbers as amplitudes and the ability 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 definitions, one can say that ultrametric algorithms are the same as probabilistic algorithms, only the interpretation of the probabilities is different.
The choice of p-adic numbers instead of real numbers is not quite arbitrary.
Ostrowski [
The notion of p-adic numbers is widely used in science. String theory [
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 and irrational numbers as measures for distances, and there is a psychological difficulty 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 linearly ordered. This is why valuations and norms of p-adic numbers are considered.
The situation is similar in Quantum Computation (see [
Advantages of ultrametric algorithms over deterministic one have been proved
in [
p-Adic Numbers and p-Ultrametric Algorithms Let p be an arbitrary prime number. A number a 2 N with 0 a p 1 is called a p-adic digit. A p-adic integer is by definition a sequence (ai)i2N of p-adic digits. We write this conventionally as ai a2a1a0, i.e., the ai are written from left to right.
If n is a natural number, and n = ak 1ak 2 a1a0 is its p-adic representation, i.e., n = Pik=01 aipi, 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 identified with the p-adic integers (ai)i2N for which all but finitely 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 is allowed to have infinitely many (!) digits to the left of the “ p-adic” point but only a finite 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) 2 X X the following conditions are satisfied. (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 2 X.
A set X together with a metric d is called a metric space. The same set X can give rise to many different metric spaces. If X is a linear space over the real numbers then the norm of an element x 2 X is its distance from 0, i.e., for all x; y 2 X and any real number we have: (1) kxk 0, and kxk = 0 if and only if x = 0, (2) k yk = j j 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 maxfkxk; kykg. Otherwise, the norm is called Archimedean.
Definition 1. Let p 2 f2; 3; 5; 7; 11; 13; : : :g 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 2 N such that a 0 (mod pm). For any rational number x = a=b we define ordp x =df ordp a ordp b. Additionally, ordp x =df 1 if and only if x = 0.
For example, let x = 63=550 = 2 1 32 5 2 71 11 1. Thus, we have ord7 x = +1 ord11 x =
1 ordp x = 0 for every prime p 2= f2; 3; 5; 7; 11g : ord2 x = ord3 x = +2 ord5 x = 1 2 kxk2 = 2 kxk3 = 1=9 kxk5 = 25 Definition 2. Let p 2 f2; 3; 5; 7; 11; 13; : : :g be any prime number. For any rational number x, we define its p-norm as p ordp x, and we set k0kp =df 0. For example, with x = 63=550 = 2 1325 27111 1 we obtain: kxk7 = 1=7 kxk11 = 11 kxkp = 1 for every prime p 2= f2; 3; 5; 7; 11g :
Rational numbers are p-adic integers for all prime numbers p. Since the
definitions given above are all we need, we finish our exposition of p-adic numbers
here. For a more detailed description of p-adic numbers we refer to [
We continue with ultrametric algorithms. In the following, p always denotes a prime number. Ultrametric algorithms are described by finite directed acyclic graphs (abbr. DAG), where exactly one node is marked as root. As usual, the root 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 p-adic 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 definition.
Definition 3. The total amplitude of the root is defined 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`, ` 2 f1; : : : ; kg, is defined 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 amplitudes of the incoming edges The total amplitude of the node v` is then defined to be ` + 2 2 + + m m.
It remains to define what is meant by saying that a p-ultrametric algorithm produces a result with a certain probability. This is specified by performing a so-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. Definition 4. We say that a p-ultrametric algorithm produces a result m with a probability q if the sum of the p-probabilities of all leaves which correctly produce the result m is no less than q.
Comment. Just as in Quantum Computation, there is something
counterintuitive in ultrametric algorithms. The notion of probability which is the
result of measurement not always correspond to our expectations. It was not easy
to accept that L. Grover’s query algorithm [
A. Ambainis exhibited a function f that provides the first superlinear separation
between polynomial degree and quantum query complexity [
Ambainis’ function f of 4 Boolean variables is defined as follows: f (x1; x2; x3; x4) = x1 + x2 + x3x4 x1x4 x2x3 x1x2:
It is easy to check that for arbitrary 4-tuple (x1; x2; x3; x4), if (x1; x2; x3; x4) 2 f0; 1g4 then f (x1; x2; x3; x4) 2 f0; 1g. To explore properties of the Ambainis’ function we introduce 6 auxiliary sets of variables.
S1 = fx1; x2g T1 = fx1g S2 = fx2; x3g T2 = fx2g
S3 = fx1; x4g T3 = fx3; x4g By S we denote the class (S1; S2; S3) and by T we denote the class (T1; T2; T3).
By (x1; x2; x3; x4) we denote the cardinality of those Si = (xj ; xk) such that xj = xk = 1. By (x1; x2; x3; x4) we denote the cardinality of those Ti such that it contains at least one element xj which equals 0. Lemma 1. For arbitrary 4-tuple (x1; x2; x3; x4) 2 f0; 1g4, f (x1; x2; x3; x4) = 0 iff (x1; x2; x3; x4) + (x1; x2; x3; x4) is congruent to 1 modulo 2.
5
tu Definition 5. Let X and Y be two finite sets such that X Y . Let y be a word in the alphabet Y . Projection projX (y) is the word obtained from y by removing all the symbols not in X.
To define the language L of pairs of words (v; w) where v 2 fa1; a2; a3; a4g ; w 2 fa1; a2; a3; a4g we first define four auxiliary languages L1; L2; L3; L4.
L1 = f(v; w) j projfa1gv = projfa1gwg L2 = f(v; w) j projfa2gv = projfa2gwg L3 = f(v; w) j projfa3gv = projfa3gwg
L4 = f(v; w) j projfa4gv = projfa4gwg
By ci(v; w) where v 2 fa1; a2; a3; a4g ; w 2 fa1; a2; a3; a4g , i 2 f1; 2; 3; 4g we denote the function Lemma 2. For each i 2 f1; 2; 3; 4g there exists a deterministic one-counter automaton with two one-way input tapes recognizing the language Li. tu Proof. Immediate.
Lemma 3. For each pair (i; j) such that i 2 f1; 2; 3; 4g and j 2 f1; 2; 3; 4g, there exists a deterministic one-counter algorithm with two one-way input tapes transforming (v; w) into (ci(v; w); cj(v; w)).
Proof. The needed deterministic automaton does not use counter to check whether projfaigv = projfajgwg and synchronizes the reading of the input tapes to keep the difference between the number of symbols ai already read from the two input tapes minimal. At every moment the content of the counter equals the difference between the number of symbols aj already read from the two input tapes. cj(v; w) = 1 if the counter is empty after reading all the symbols. tu Theorem 1. There exists a 2-ultrametric automaton with two one-way input tapes recognizing the language L.
Proof. The desired algorithm branches its computation path into 6 branches at the root. We assign to each starting edge of the computation path the amplitude 17 .
The first 3 branches (labeled with numbers 1; 2; 3) correspond to exactly one set Si.
Let Si consist of elements xj; xk. Then the algorithm computes the pair (cj(v; w); ck(v; w)) as decribed in the proof of Lemma 3. If the two computed values equal 1 then the algorithm goes to the state q3. If at least one of the computed values equals 0 then the algorithm goes to the state q4.
The next 3 branches (labeled with numbers 4; 5; 6) correspond to exactly one set Ti. Let Ti consist of elements xj; xk. Then the algorithm computes the pair (cj(v; w); ck(v; w)) as described in the proof of Lemma 3. If at least one of the results equals 0 then the algorithm goes to the state q3. If all the results equal 1 then the algorithm goes to the state q4.
1 branch (labeled with number 7) asks no query and the algorithm goes to the state q3.
In result of this computation the amplitude A3 of the states q3 has become 1 A3 = (1 + (x1; x2; x3; x4) + (x1; x2; x3; x4));
7
The 2-ultrametric query algorithm performs measurement of the state q3. The amplitude A3 is transformed into a rational number kA3k. 2-adic notation for the number 7 is : : : 000111 and 2-adic notation for the number 71 is : : : 110110110111. Hence, for every 2-adic integer , k k = k 17 k.
By Lemma 1, k1 + (x1; x2; x3; x4) + (x1; x2; x3; x4)k2 equals 1, if f (x1; x2; x3; x4) = 0 and it equals 12 , if f (x1; x2; x3; x4) = 0 tu
We wish to prove that there is no error bounded probabilistic one-counter automaton with two one-way input tapes recognizing the language L. Had our automaton had two-way input tapes, even deterministic automaton could do the job. The real problem is whether it is possible to combine four deterministic onecounter automata recognizing L1; L2; L3; L4 in a single probabilistic automaton. Our Theorem 2 below shows that it is "almost possible".
M = L1 \ L2 \ L3 \ L4 = f(v; w) j c1(v; w) c2(v; w) c3(v; w) c4(v; w) = 1g which seems to be quite similar to L but probabilistic automata can recognize it. Advantages of ultrametric algorithms can be seen comparing the languages L and M .
Theorem 2. For arbitrary > 0, there exists a probabilistic one-counter automaton with two one-way input tapes recognizing the language M with probability 1 .
We wish to prove that there exists no error bounded probabilistic one-counter automaton with two one-way input tapes recognizing the language L. In the proof we heavily employ the property of Ambainis’ function to be non-monotonic. Being non-monotonic is the property that distinguishes Ambainis’ function from conjunction used in definition of the language M .
8 f (1; 1; 0; 1) = 0 > >< f (0; 1; 0; 0) = 1
f (0; 1; 0; 1) = 1 > >: f (0; 0; 0; 0) = 0
We need main notions of the theory of finite Markov chains for this proof.
(For more details see the classical book [
A finite Markov chain is a stochastic process which moves through a finite number of states, and for which the probability of entering a certain state depends only on the last state occupied.
We describe a Markov chain as follows: We have a set of states,
S = fs1; s2; : : : ; skg: The process starts in one of these states and moves successively from one state to another. Each move is called a step. If the chain is currently in state si, then it moves to state sj at the next step with a probability denoted by pij, and this probability does not depend upon which states the chain was in before the current state. The probabilities pij are called transition probabilities. The process can remain in the state it is in, and this occurs with probability pii. An initial probability distribution, defined on S, specifies the starting state. Usually this is done by specifying a particular state as the starting state.
In particular, the states are divided into equivalence classes. Two states are in the same equivalence class if they "communicate," i.e. if one can go from either state to the other one. The resulting partial ordering shows us the possible directions in which the process can proceed. The minimal elements of the partial ordering are of particular interest.
Definition 6. The minimal elements of partial ordering of equivalence classes are called ergodic sets. The remaining elements are called transient sets. The elements of a transient set are called transient states. The elements of an ergodic set are called ergodic (or non-transient) states.
An ergodic set of states is a set in which every state can be reached from every other state, and which cannot be left once it is entered. A transient set of states is a set in which every state can be reached from every other state, and which can be left.
Since every finite partial ordering must have at least one minimal element, there must be at least one ergodic set for every Markov chain. In particular, if an ergodic set contains only one element, then we have a state which once entered cannot be left. Such a state is called absorbing. However, there need be no transient set. The latter will occur if the entire chain consists of a single ergodic set, or if there are several ergodic sets which do not communicate with others.
If a chain has more than one ergodic set, then there is absolutely no interaction between these sets. Hence we have two or more unrelated Markov chains lumped together. A chain consisting of a single ergodic set is called an ergodic chain. A particular case of an ergodic set is cyclic. A cyclic chain is an ergodic chain in which each state can only be entered at certain periodic intervals. Such a chain has a period d, and its states are subdivided into d cyclic sets (d > 1).
In any finite Markov chain, no matter where the process starts, the probability after n steps that the process is in an ergodic state tends to 1 as n tends to infinity.
An absorbing chain is one all of whose ergodic states are absorbing; or, equivalently, which has at least one absorbing state, and such that an absorbing state can be reached from every state.
In a chain with transient sets the process moves towards the ergodic sets. The probability that the process is in an ergodic set tends to 1, and it cannot escape from an ergodic set once it enters it.
Theorem 3. There exists no error-bounded probabilistic one-counter automaton with two one-way input tapes recognizing the language L.
Proof. Assume from the contrary that A is such an automaton recognizing L with a probability 21 + . We introduce a notion of approximating Markov chain (shortly: AM C) for the automaton A. AM C gives only partial information about the automaton A but it allows to classify several possibilities of properties of the assumed automaton in order to get to contradiction using these properties explicitly.
AM C for the automaton A depends on four parameters: n being a natural number (contradiction is obtained by considering n ! 1), parameters f(r1; r2) j r1 2 f1; 2; 3; 4g; r2 2 f1; 2; 3; 4gg; and a word u 2 fa1; a2; a3; a4g . The work of A cannot be described as a Markov chain. The AM C is the Markov chain obtained by simulating the work of the probabilistic one-counter automaton A on infinitely long input words, namely, the word on the first input tape being u continued by !-word ar1 ar1 ar1 : : : and the word on the second input tape being the !-word ar2 ar2 ar2 : : :
We consider the work of A starting from the moment when the reading of the first input tape has reached the last symbol of u. In the process of the simulation the counter is always neglected—assuming that A always gets information "the counter is not empty". The symbols read from the two input tapes do not change anymore. The state of the automaton at each moment is completely described by a Markov chain. This Markov chain is our AM C(n; u; r1; r2).
Hence the simulated process may differ from the work of A. Rather the AM C describes a part of the work of A.
We start our analysis of A by considering AM C(1; u0; 1; 3) where u0 is an empty word. This means that A does not receive any information from the input tapes but the length of the words read. Moreover, AM C has only a finite number of states, and does not have ability to remember these lengths.
By Theorem 3.1.1 in [
Let si; : : : ; sj be all distinct states in the same ergodic set. Let be the least common multiple of (si); : : : ; (sj ). The Markov chain AM C(1; u0; 1; 3) cannot remember how many fragments of the length have been read form the input. Hence, since A is to remember this, A remembers this by adding some number to the counter. If the states si; : : : ; sj allow different numbers to be added to the counter, then reading n fragments of the length where n tends to infinity, produces a Gauss distribution of the numbers added to the counter. This implies that A is not able to distinguish between close values of the lengths. Hence each ergodic set has to be cyclic. Moreover, for each ergodic set there is a constant c such that, independent of which state the automaton A is in, reading symbols from the first input adds c to the counter.
Note that there may be several ergodic sets of states. However, if the total number of the states is k then k! is an upper bound for the least common multiple of the lengths of all these cycles.
Now we consider another AM C, namely, AM C(n; u; 2; 3), where u is a word in a single-letter alphabet fa1g of the length n (now only letters a2 are read from the first input). In a similar way we prove that for each ergodic set of this AM C there is a constant d such that, independent of which state the automaton A is in, reading symbols from the first input adds d to the counter. This implies that if we are interested only in the content of the counter, the cut-andpaste arguments can be used exactly as in deterministic automata. We can add a fragment consisting of a constant number of symbols to the first input word and the only change in the perfomance of A is adding another d to the counter.
Let n be a natural number large enough to have three properties: 1) the probability after reading the first n symbols a1 from the first input that the process is in an ergodic state exceeds 3+42 . 2) n k!.
Now we consider the work of A on the pair of words (w1; w2) such that w1 has a prefix (a1)n(a2)n+k!(a4)n!+k!, w2 has a prefix (a3)m where m is large enough to assert that with probability exceeding 3+2 the automaton A does not leave the 8 prefix (a3)m of w2 on the second input tape while reading (a1)n(a2)n+k!(a4)n!+k! on the first input tape. Additionally, we complement (w1; w2) by symbols a1; a2; a4 to get (w1; w2) 2 L1 \ L2 \ L3 \ L4.
Note that the prefix (a1)n(a2)n+k!(a4)n!+k! is long enough to ensure that each of 3 fragments (a1)n, (a2)n+k!, (a4)n!+k! allows to use the cut-and-paste arguments exactly as in deterministic automata. We can add a fragment consisting of a constant number of symbols to the first input word and the only change in the perfomance of A is adding a constant number to the counter. It is important to note that A has no possibility to remember how many times this adding has been performed.
If this addition is performed in no fragment of the prefix, then (w1; w2) 2= L because Ambainis’ function f (1; 1; 0; 1) = 0. If this addition is performed in the fragment (a1)n, then (w1; w2) 2 L because Ambainis’ function f (0; 1; 0; 1) = 1. If this addition is performed in the fragments (a1)n and (a4)n!+k!, then (w1; w2) 2 L because Ambainis’ function f (0; 1; 0; 0) = 1. If this addition is performed in the fragments (a1)n and (a2)n+k! and (a4)n!+k!, then (w1; w2) 2= L because Ambainis’ function f (0; 0; 0; 0) = 1. However, the automaton A does not distinguish between these cases. Contradiction. tu