<p>I am a bit confused about the proper role of <a href="https://en.wikipedia.org/wiki/Probabilistic_automaton" rel="nofollow noreferrer">probabilistic automata (PA)</a> in the theory of computation.</p>
<p>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 &quot;tossing a coin&quot; with the probabilities 1/2 (same as the probability of that a string belongs to the language).</p>
<p>I guess the non-regularity of PAs comes from the probabilistic weight defined by a real number:</p>
<p><span class="math-container">$w = x_1x_2...x_{n-1}x_n$</span> | <span class="math-container">$p(w) = 0.x_nx_{n-1}..x_2x_1$</span></p>
<p>So it is not possible for a nondeterministic finite automaton (NFA) to simulate the PA as it cannot simulate real numbers.</p>
<p>If this is true, it leads to a question whether the language category defined by PAs, stochastic languages, is actually Turing-undecidable (non-computable)?</p>
<p>Would that mean that stochastic languages are recursively enumerable or even a superset of recursively enumerable languages?</p>

CC BY-SA 4.0
2023-11-01T08:59:21.053Z
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).
Shaull
CC BY-SA 4.0
2023-11-01T15:42:29.657Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-11-10T09:58:50.387Z
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
Alfonso F R
<computability><probabilistic-computation><probabilistic-automata>
Computational power of probabilistic automata
Barney
# Computational power of probabilistic automata

(Asked by: username_0 on 2023-11-01)

I am a bit confused about the proper role of [probabilistic automata (PA)](https://en.wikipedia.org/wiki/Probabilistic_automaton) 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?

**Tags:** computability, probabilistic-computation, probabilistic-automata

> **Comments:**
> **username_1**: 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).  
> **username_2**: 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.  
> **username_3**: 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  

---

## 0 answers

