Can the halting problem be solved probabilistically?
It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $&gt;1/2$, the algorithm outputs the correct answer (and therefore halts), but we allow the existence of infinite runs where the algorithm uses infinitely many random bits.
Indeed, by $\sigma$-additivity of the probabilistic measure, for any input $x$, there exists $n$ such that with probability $&gt;1/2$, the algorithm computes the right answer within $n$ steps. Thus, we can find the answer deterministically as follows: for $n=1,2,3,\dots$, we simulate the algorithm for $n$ steps using all possible sequences of random bits (necessarily of length $\le n$) to count the probability that it halts with any particular answer; sooner or later, we find an $n$ and an answer that’s output with probability $&gt;1/2$ within $n$ steps, and then we declare the winner.