[throwawaymath]

Unless I’m misunderstanding the parent commenter’s definition of a probabilistic gate - I’m assuming a unitary matrix - then that shouldn’t be an issue. Chaitin’s constant is in both R and C. More generally, all uncomputable real numbers are also in C, because C is complete over R.

In other words that shouldn't be the issue, because the correct "setting" for the stochastic matrix still allows for that possibility. It's not something you introduce by using real entries.

[krcz]

I don't think the issue here is requiring the matrix coefficients to be real (I don't think that complex values make sense there at all), but allowing arbitrary real numbers. In such case you can show algorithm, for which there exist matrix with real coefficients such that it solves halting problem - the trick is encoding infinite amount of information in the real constant.

[throwawaymath]

Complex values (a unitary matrix) make sense if the stochastic matrix is representing a probability amplitude.