8 fixed wrong direction
source | link

"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 whenevercan only occur 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.

"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 whenever $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.

"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 can only occur 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.

7 fixed incorrect claim
source | link

"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 ifwhenever $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.

"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.

"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 whenever $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.

6 deleted 22 characters in body
source | link

"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} \;\;$$\tfrac12 < \operatorname{Prob}(M \text{ accepts in at most $n$ steps})$ will accept
 exactly the inputs that $M$ has a probability greater than 1/2$\tfrac12$ of accepting.

 

"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 1/2 of accepting.

 

"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.

5 stated "a bit more explicitly what" my "argument is here"
source | link
4 Improving LaTeX readability.
source | link
3 Improving LaTeX readability.
source | link
2 showed the non-decreasing claim
source | link
1
source | link