Language Recognition Using Finite Probabilistic Multitape and Multihead Automata

Rabin demonstrated in [Inf. Control, 1963, vol. 6, no. 3, pp. 230–244] that finite probabilistic automata with an isolated section point can recognize only those languages that can be recognized by finite deterministic automata. In this paper for finite automata with many tapes or with many heads on one tape, we prove the opposite result; namely, that there exists a language that can be recognized with probability $1-\varepsilon$ for any $\varepsilon>0$ but which cannot be recognized deterministically.