A notion of ultrametric automata and Turing machines using p-adic numbers is introduced to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.

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. However, there is an important feature that distinguishes p-adic numbers from real numbers. Real numbers (both rational and irrational) are linearly ordered. 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. 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.