[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.