I am a bit confused about the proper role of probabilistic automata (PA) in the theory of computation.

Informally, I can imagine they can accept more than finite automata (FA) as they, for instance, decide the language of equal numbers of 0s and 1s by "tossing a coin" with the probabilities 1/2 (same as the probability of that a string belongs to the language).

I guess the non-regularity of PAs comes from the probabilistic weight defined by a real number:

$w = x_1x_2...x_{n-1}x_n$ | $p(w) = 0.x_nx_{n-1}..x_2x_1$

So it is not possible for a nondeterministic finite automaton (NFA) to simulate the PA as it cannot simulate real numbers.

If this is true, it leads to a question whether the language category defined by PAs, stochastic languages, is actually Turing-undecidable (non-computable)?

Would that mean that stochastic languages are recursively enumerable or even a superset of recursively enumerable languages?

  • 1
    $\begingroup$ A Turing Machine can easily keep track of all the runs of a PA, and accept/reject based on a threshold (as long as the probabilities themselves are computable numbers, e.g., rationals). Moreover, any automaton over a semiring can be simulated by a Turing Machine, so the expressive power does not go beyond computability (it is much weaker). $\endgroup$
    – Shaull
    Commented Nov 1, 2023 at 8:59
  • 2
    $\begingroup$ Well, at least the definition on Wikipedia allows arbitrary reals as thresholds, and a construction of $2^\omega$ distinct stochastic languages is given there. Thus, some stochastic languages are noncomputable, or even outside the arithmetic hierarchy, or any similar hierarchy. This does not in any way imply that stochastic languages are a superset of recursively enumerable languages; I am not familiar with the class of stochastic languages, but I expect that there exist even context-free languages that are not stochastic. $\endgroup$ Commented Nov 1, 2023 at 15:42
  • $\begingroup$ Your understanding of probabilistic automata (PAs) and their role in the theory of computation is quite insightful. Probabilistic automata indeed introduce a probabilistic element into the computation process, and your analogy with tossing a coin to decide whether a string belongs to a language is accurate. Of course, other examples are possible for various tossing probabilities or even more nuanced probability distributions. The non-regularity of PAs is indeed related to the probabilistic weights associated with transitions. The notion of real numbers in these weights makes PAs more expressiv $\endgroup$ Commented Nov 10, 2023 at 9:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.