> Do you have an outline of this proof? Let p be the real number where, iff the k'th program halts, the k'th bit of p (after the decimal point, in binary) is 1

> Do you have an outline of this proof? Let p be the real number where, iff the k'th program halts, the k'th bit of p (after the decimal point, in binary) is 1. Let M be the operation "toggle a bit with probability p", which has matrix [[1-p, p], [p, 1-p]]. When given a program k to solve, keep applying M while counting up how many toggles you see. Do this until the chance that the k'th bit of the sample mean equals the k'th bit of p is greater than 2/3 or whatever other threshold you want, which will take a finite number of samples. Return the k'th bit of the sample mean. This is a probabilistic algorithm which solves the halting problem with arbitrarily high probability.