3 ms·
Maybe the problem is that you can use uncomputable numbers in the matrix? (e.g. https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki
by zielmicha 7y ago
Maybe the problem is that you can use uncomputable numbers in the matrix? (e.g. https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant)
- throwawaymath 7y agoUnless 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 7y agoI 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 7y agoComplex values (a unitary matrix) make sense if the stochastic matrix is representing a probability amplitude.