Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
1 of 8

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




$\operatorname{Prob}(\hspace{.02 in}M \text{ accepts}) \; = \; \operatorname{Prob}\hspace{-0.04 in}\big(\hspace{-0.02 in}(\exists n)(\hspace{.02 in}M \text{ accepts after exactly } n \text{ steps})\big)$
$=$

$\displaystyle\sum_n \operatorname{Prob}(\hspace{.02 in}M \text{ accepts after exactly } n \text{ steps})$

$=$
$\displaystyle\lim_N \left(\displaystyle\sum_{n\leq \hspace{.02 in}N} \operatorname{Prob}(\hspace{.02 in}M \text{ accepts after exactly } n \text{ steps})\hspace{-0.04 in}\right)$

$=$

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



Since $\: \operatorname{Prob}(\hspace{.02 in}M \text{ accepts in at most } n \text{ steps}) \:$ is non-decreasing in $n$,


$\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)$