8 fixed wrong direction edited Dec 13 '14 at 19:46 user12859 "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 edited Dec 13 '14 at 19:12 user12859 "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 edited Dec 10 '14 at 8:39 David Richerby 75k1616 gold badges117117 silver badges208208 bronze badges "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" edited Dec 10 '14 at 5:37 user12859 4 Improving LaTeX readability. edited Dec 10 '14 at 0:50 David Richerby 75k1616 gold badges117117 silver badges208208 bronze badges 3 Improving LaTeX readability. edited Dec 10 '14 at 0:25 David Richerby 75k1616 gold badges117117 silver badges208208 bronze badges 2 showed the non-decreasing claim edited Dec 10 '14 at 0:17 user12859 1 answered Dec 9 '14 at 23:48 user12859