6 of 8 deleted 22 characters in body

"this class of problems lie"s in RE, so its name is "RE".

\begin{align*}\operatorname{Prob}(M \text{ accepts}) &= \operatorname{Prob}\big((\exists n)(M \text{ accepts after exactly n steps})\big)\\ &=\sum_n \operatorname{Prob}(M \text{ accepts after exactly n steps})\\ &=\lim_N \sum_{n\leq N} \operatorname{Prob}(M \text{ accepts after exactly n steps})\\ &=\lim_N \;\operatorname{Prob}(M \text{ accepts in at most N steps}) \\ &= \lim_n \; \operatorname{Prob}(M \text{ accepts in at most n steps})\,. \end{align*}

For all $$m$$ and $$n$$ with $$m\leq n$$, and for all randomness strings $$r$$, $$M$$ accepts in at most $$m$$ steps if and only if it accepts in exactly some $$t\leq m$$ steps. But then $$t\leq n$$ so this occurs if and only if $$M$$ accepts in at most $$n$$ steps with randomness string $$r$$.

For all $$m$$ and $$n$$, with $$m\leq n$$, the probability that $$M$$ accepts in at most $$m$$ steps does not exceed the probability that it accepts in at most $$n$$ steps.

\begin{align*} &\tfrac12 < \operatorname{Prob}(M \text{ accepts}) \\ &\iff \tfrac12 < \lim_n \; \operatorname{Prob}(M \text{ accepts in at most n steps})\\ &\iff (\exists n)\left(\tfrac12 < \operatorname{Prob}(M \text{ accepts in at most n steps})\right)\,. \end{align*}

Therefore, a machine that loops over the positive integers $$n$$ and accepts if and only if $$\tfrac12 < \operatorname{Prob}(M \text{ accepts in at most n steps})$$ will accept exactly the inputs that $$M$$ has a probability greater than $$\tfrac12$$ of accepting.

 answered Dec 9 '14 at 23:48 user12859