**Problem Detail:**

In Sipser's text, he writes:

When a probabilistic Turning machine recognizes a language, it must accept all strings in the language and reject all strings not in the language as usual, except that now we allow the machine a small probability of error.

Why is he using "recognizes" instead of "decides"? If the machine rejects all strings that are not in the language, then it always halts, so aren't we restricted to deciders in this case?

The definition goes on:

For $0 < \epsilon < 1/2$ we say that

$M$ recognizes language $A$ with error probability $\epsilon$if1) $w \in A$ implies $P(M \text{ accepts } w) \ge 1 - \epsilon$, and

2) $w \notin A$ implies $P(M \text{ rejects } w) \ge 1 - \epsilon$.

So it seems like the case of $M$ looping is simply not allowed for probabilistic Turning machines?

###### Asked By : theQman

###### Answered By : Yuval Filmus

Complexity theory makes no distinction between "deciding" and "recognizing". The two words are used interchangeably. Turing machines considered in complexity theory are usually assumed to always halt. Indeed, usually only time-bounded machines are considered (such as polytime Turing machines), and these halt by definition.

In your particular case, you can interpret *accept* as halting in an accepting state, and *reject* as halting in a rejecting state. The Turing machine is thus allowed not to halt. However, the class BPP also requires the machine to run in polynomial time, that is, to *halt* in polynomial time. In particular, the machine must always halt.

Question Source : http://cs.stackexchange.com/questions/65491

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback