A probabilistic Turing machine flips an unbiased coin in some of its states. It accepts an input if the probability of entering an accepting state is greater than 1/2. Two modifications of this notion of acceptance are studied in the paper under review. First, the threshold 1/2 is replaced by an arbitrary real number r belonging to the interval [0,1]. It is shown that all languages accepted with threshold r are recursively enumerable if and only if the upper Dedekind cut of r is r . e . This result is neither surprising nor hard to prove.
Second, the phrase “greater than 1/2” is replaced by “greater than or equal to r”, where r is again a real number between 0 and 1. It is shown that for any real number r ∈ [0,1] (with r . e . lower Dedekind cut) the class of languages accepted in this way is exactly &Pgr;20. This result is interesting. The authors are right in stating that it is a justification of the usual definition of acceptance.
In my view, the paper under review does not deal with a central question of computer science. Notions from complexity theory are not involved. But it is written in a clear style and is completely self-contained. The length is suitable for its subject.
