Probabilistic halting problem
Let $A$ be a randomized procedure which outputs $h_p$ with success probability larger than $1/2$.

Consider the following code, with input $x$:


Let $y$ be the machine corresponding to machine $x$ running on itself as input.
If $A(y) = 1$, go into an infinite loop, otherwise halt.


Denote this program by $B$.
What happens if we run $B$ on itself? Let us consider two cases. In both cases, let $y$ be the machine corresponding to $B$ running on itself.

Case 1: $B$ halts on $B$ with probability at least $1/2$. In this case, $h_p(y) = 1$, and so with probability more than $1/2$, $A(y) = 1$. Therefore $B$ goes into an infinite loop with probability more than $1/2$, contradiction.

Case 2: $B$ halts on $B$ with probability smaller than $1/2$. In this case, $h_p(y) = 0$, and so with probability more than $1/2$, $A(y) = 0$. Therefore $B$ halts with probability more than $1/2$, contradiction.

(This generalizes the usual proof of uncomputability of the halting problem via diagonalization.)