3 of 8 Improving LaTeX readability.

"this class of problems lies" 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$$, if $$m\leq n$$ then, for all randomness strings $$r$$,

$$\text{on randomness } r, \: M \text{ accepts in at most } m \text{ steps}$$
$$\iff$$
$$(\exists t)\big((\text{on randomness } r, \: M \text{ accepts after exactly } t \text{ steps}) \: \text{ and } \: t\leq m\big)$$
$$\implies$$
$$(\exists t)\big((\text{on randomness } r, \: M \text{ accepts after exactly } t \text{ steps}) \: \text{ and } \: t\leq n\big)$$
$$\iff$$
$$\text{on randomness } r, \: M \text{ accepts in at most } n \text{ steps}$$

.

For all $$m$$ and $$n$$, if $$\: m\leq n \:$$ then $$\operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } m \text{ steps}) \; \leq \; \operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } n \text{ steps}) \;\;\;\;$$.

$$\frac12 \;\; < \;\; \operatorname{Prob}(\hspace{.02 in}M \text{ accepts})$$

$$\iff$$

$$\frac12 \;\; < \;\; \displaystyle\lim_n \: \operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } n \text{ steps})$$

$$\iff$$

$$(\exists n)\left(\frac12 < \operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } n \text{ steps})\hspace{-0.02 in}\right)$$

 answered Dec 9 '14 at 23:48 user12859