Some specialist would know for sure (I've been wanting to ask), but I think current physical theory (whether it really describes Nature or not) allows generation of unlimited amounts of Kolmogorov-random data through quantum processes, which can't be simulated with a Turing machine. As Leonid Levin put it ( http://www.cs.bu.edu/fac/lnd/expo/gdl.htm ):
As is well known, the absence of algorithmic solutions is no obstacle when the requirements do not make a solution unique. A notable example is generating strings of linear Kolmogorov complexity, e.g., those that cannot be compressed to half their length. Algorithms fail, but a set of dice does a perfect job!
Levin has a paper proposing a slight refinement of the Church-Turing thesis to take this into account: http://arxiv.org/abs/cs.CC/0203029
Nachum Dershowitz and Yuri Gurevich have an interesting article where they try to logically deduce CT from some supposedly more basic ideas about abstract state machines: http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf
I've been wondering for a while (based on Levin's example) about a thought experiment: Fix a universal Turing machine U. Flip a coin 2 million times and call the resulting random bit string S. Let P be the proposition that there is no program for U less than 1 million bits long, that writes S onto the tape (i.e. P says that S's Kolmogorov complexity is more than 1 million bits). There is of course some very small probability that P is false (you might have flipped 2 million heads completely by chance), but P is almost certainly true. But, by Chaitin's version of Gödel's incompleteness theorem, P (if true) is independent of any reasonable axiom system for mathematics(, including any iterated consistency hypotheses, reflection schemes, etc.) yet is completely unprovable etc. (or And you could always use 2 billion flips instead of 2 million). So you've got a simple experimental apparatus that can create unlimited amounts of unprovable but (almost certainly) true mathematical statements. This can't be done with classical algorithms. So where does our creaky old physical universe get such knowledge?
