The idea of using p-adic numbers in Turing machines and nite automata to describe random branching of the process of computation was recently introduced. In the last two years some advantages of ultrametric algorithms for nite automata and Turing machines were explored. In this paper advantages of ultrametric automata with one head versus multihead deterministic and nondeterministic automata are observed.
Addition, subtraction, multiplication and division of p-adic numbers are done
the same way like natural numbers. p-adic numbers are widely used in chemistry
[
We will also need an absolute value or norm, which is a distance from zero. It's denoted by jjxjj and has the following properties: 1. jjxjj = 0 if and only if x = 0, 2. jjx yjj = jjxjj jjyjj, 3. jjx + yjj jjxjj + jjyjj.
0; if x = 0 p-norm will be: jjxjjp =
Norm is called ultrametric if jjx + yjj max(jjxjj; jjyjj).
If p is a prime number, then the p-adic ordinal of a, denoted by ordpa, is the
highest power of p which divides a. Accordingly for any rational number x, it's
(1=pordpx; if x 6= 0
[
Ultrametric automata are described in more details by Rusins Freivalds [
Most principles of the work of ultrametric automata are in common with probabilistic automata. Compared to deterministic automaton, probabilistic automaton has a stochastic vector (vector of probabilities) instead of one beginning state. Transitions also have probabilities and can be represented with the help of stochastic matrices. One matrix shows transitions for one speci c letter of the input alphabet. Probabilistic automaton also has a threshold, and input word is accepted if and only if the sum of probabilities of every accepting state exceeds threshold after input word is read.
Ultrametric automaton has an additional element - prime number p. Probabilities of transitions are p-adic numbers, and are called amplitudes. Ultrametric automaton doesn't have limitation for beginning state vector and transition matrices to be stochastic. While probabilistic automaton has an accepting threshold, ultrametric automaton has an accepting interval, which is represented by two real numbers. After reading input word amplitude of every accepting state is transformed into p-norm. If sum of such p-norms belongs to an accepting interval, input word is accepted. 4
M ultihead automata are similar to nite automata with one head. Transition function will be di erent - it will be in the following form: S (A [ f`; ag)k ! S f 1; 0; 1gk where k is number of heads, S is the set of states, A is an input alphabet, ` is left end-marker, a is right end-marker. f 1; 0; 1gk means, that every one of k heads can: { move one symbol to the left on the input word, if value is -1; { stay on the same symbol of the input word, if value is 0; { move one symbol to the right on the input word, if value is 1.
If head is on the left end-marker it can't move to the left, and, respectively,
it can't move to the right, if it is on the right end-marker. Here were mentioned
main principles of how di ers two-way multihead deterministic nite automaton
from two-way deterministic nite automaton with one head. In the case of
oneway automata head can't move to the left. More precise de nition can be found
in [
In the case of nondeterministic and ultrametric nite automata de nition will di er with the fact that we have to deal with multiple heads. So, the only di erence will be in the transition function. It will be like transition function of deterministic multihead automata, but transitions will be made with amplitudes. 5
Advantages of Multihead Ultrametric Automata
It is known that one-way deterministic nite automata with k heads are weaker
(can recognize fewer languages) than one-way nondeterministic nite automata
with k heads for k 2 [
Theorem 1. For every prime number p for every k 1 set of languages recognized by one-way deterministic nite automata with k heads is a proper subset of the set of languages, that can be recognized by one-way p-ultrametric nite automata with k heads.
Proof. For k = 1 let's take language L1 = fw2wrev2jw 2 f0; 1g g where wrev
consists of the same letters, as w, but in opposite order. In [
We can transform any nondeterministic automaton into p-ultrametric. In this case we will keep all states and transitions of nondeterministic automaton, all beginning states will have amplitude 1, all transitions will be made with amplitude 1 and input word will be accepted by ultrametric automaton if p-norm sum of all accepting states will be greater than 0. Resulting ultrametric automaton does not depend on parameter p. This means that one-way ultrametric automata with k heads are at least as powerful as one-way nondeterministic automata with k heads. For every k 2 for every prime number p the set of languages recognizable by one-way deterministic nite automata with k heads is a proper subset nite automata with 2 we obtain that for automata with of set of languages recognizable by one-way p-ultrametric k heads.
From parts of proof for k = 1 and k k heads condition holds for every k 1.
Now let's take a look at situation where we can reduce the number of heads for ultrametric automata compared to deterministic ones.
Theorem 2. For every prime number p for every k 1 there is a language
which can be recognized by one-way p-ultrametric nite automaton with 2 heads
and cannot be recognized by one-way deterministic nite automaton with k heads.
Proof. In [
Power of Ultrametric Automata with One Head
There is a proof that for one-way deterministic and nondeterministic nite
automata class of languages recognizable by automaton with k + 1 head is wider
than class of languages recognizable by automaton with k heads, for all
natural k 1 [
Proof. We will construct 2-adic automaton that recognizes language Lb. For each 1 i b we will make set of states which will check equality of the corresponding pair of fragments, that is, if wi = w2b+1 i. Fragment for one such pair is shown on g. 1.
In the states of bottom row on g. 1 there is a check for fragment length equality. Beginning amplitude is 1. When automaton is reading fragment wi every symbol of the fragment multiplies amplitude by 2. Then automaton goes further on the row of states until it will reach fragment w2b+1 i. While reading this fragment every symbol will divide amplitude by 2. Amplitude will be equal to 1 if and only if both fragments had same length. Then after reading whole input word -1 will be added to amplitude, so amplitude of accepting state will be equal to 0 if condition of fragment equality holds.
Upper two rows on g. 1 ensure check for matching of symbol "1" positions in corresponding fragments wi and w2b+1 i. In the rst row automaton walks through states until it reaches fragment wi. Then in the next step symbols "1" and their positions are counted, and amplitude after reading fragment gets equal n 1 to P ai2i, where n is length of the fragment and ai equals to 1 if i-th symbol was i=0 1, else ai equals to 0. After reading fragment sum is stored in the accepting state. Second row of states in the similar way ensures nding of fragment w2b+1 i and n 1 then from the accepting state P ai2i is being subtracted in the similar way. As i=0 a result amplitude of accepting state will be equal to 0 if and only if positions of symbol "1" in both fragments were the same.
If both conditions hold after reading the input word (that means, if fragments wi and w2b+1 i are equal), then both accepting states will have amplitude 0. So p-norm sum of accepting states will be equal to 0 if and only if wi = w2b+1 i. Else p-norm sum of accepting states will be equal to some positive number.
For every fragment pair wi and w2b+1 i same checks for equality will be made, but in the sets of states will be di erent amount of states that ensure nding of the fragment that we are interested in. In the similar way p-norm sum of accepting states will be equal to 0 if and only if fragments of pair are equal. Else mentioned p-norm sum will be equal to some positive number. By counting together p-norms of accepting states of all sets of that kind we will get 0 if and only if input word belongs to Lb. In this way we can construct 2-adic automaton to recognize language Lb for every positive integer b. By taking b too big (b > k2 respectively) one-way deterministic or nondeterministic nite automaton with k heads won't be able to recognize language Lb.
To prove a theorem for all prime numbers p we can replace amplitude 2 with p in all places where we were multiplying or dividing by 2. So the theorem holds for every prime number p.
In fact we can easily expand the set of the languages that can be recognized by one-way ultrametric nite automaton with one head and cannot be recognized by one-way deterministic or nondeterministic automaton with xed arbitrary amount of heads. When de ning languages we can take as base language Lb, but this time every fragment wi will consist of n letter alphabet instead of two letter alphabet f0; 1g. Situation will be similar to language Lb, but this time p-ultrametric automaton will have to check positions of n 1 symbols of input alphabet instead of one symbol (in the example of language Lb such symbol was "1"). This can result in the increase of number of states.
Results obtained in this chapter and possibility to transform nondeterministic automaton with k heads into p-ultrametric automaton with k heads for any prime number p can give us another result about hierarchy of multihead automata. Theorem 4. For every k 1 for every prime number p the set of languages recognizable by one-way nondeterministic nite automata with k heads is a proper subset of the set of languages recognizable by one-way p-ultrametric nite automata with k heads.
Proof. In the proof of Theorem 1 we can see that for every number of heads k 1 one-way ultrametric automata are at least as powerful, as one-way nondeterministic automata. We can use Theorem 3 to say that for every prime number p for every number of heads k 1 one-way p-ultrametric automaton will be able to recognize some languages that cannot be recognized by one-way nondeterministic automata. 7
Ultrametric automata can have better place in the hierarchy of multihead automata than nondeterministic automata. All begins with the fact that one head of ultrametric automaton can do more than one head of deterministic or nondeterministic automaton. For any xed number of heads k one-way k-head ultrametric automata are stronger than one-way k-head deterministic and nondeterministic automata.
In some cases ultrametric automata with one head can recognize languages better than multihead deterministic and nondeterministic automata. The research made shows potential of the heads of ultrametric automata and researches will be continued to nd the place of ultrametric automata in the hierarchy of multihead automata.