Is there a probabilistic Turing machine whose halting probability is non-measurable?

Question

I was wondering if there a probabilistic turing machine whose halting probability is non-measurable? By that, I mean that the probability measure applied to the event "the machine halts" is undefined.

Answer 1

No, this can't happen (assuming we're fixing the input). The probability that a probabilistic Turing machine halts is given by the sum of the probabilities of each of the possible finite sequences of states which end in a halting configuration; there's no room for anything interesting to happen.

---

Incidentally, non-measurability really just applies to a given space, and there isn't one here explicitly. Of course we can shoehorn one in, viewing a probabilistic Turing machine as depending on an input and a point in an appropriate space representing the "sequence of events;" each reasonable such way, though, leads to the set of points yielding halting computations - after fixing the input, of course - being a low-complexity set (at worst, low-level Borel), well below the threshold for non-measurability.

For a controlled example, for any Turing machine $\Phi_e$ and any input $n$, the set of oracles $f\in 2^\omega$ for which $\Phi_e^f(n)$ halts is an open set since halting is ensured by some finite initial segment of $f$, and open sets are always measurable.=