I asked a related question at CS Theory, which ended with this question:
Is it the case that a TM [Turing Machine] with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?
I received a detailed and knowledgeable reply from Laurent Bienvenu, which I found so enlightening that it may be worth quoting the relevant portions here:
From a computability perspective, the answer is 'Yes and No.' If you are given access to a random source as an oracle (where the output is presented as an infinite binary sequence), with probability 1 you will get a Martin-Löf random oracle, and as we saw earlier [earlier in his own answer], Martin-Löf random implies non-computable, so it suffices to output the oracle itself! Or if you want a function $f:N \rightarrow N$, you can consider the function $f$ which for all $n$ tells you how many zeroes there are among the first $n$ bits of your oracle. If the oracle is Martin-Löf random, this function will be non-computable.
But of course you might argue that this is cheating: indeed, for a different oracle we might get a different function, so there is a non-reproducibility problem. Hence another way to understand your question is the following: Is there a function $f$ which is non-computable, but which can be "computed with positive probability," in the sense that there is an Turing machine with access to a random oracle which, with positive probability (over the oracle), computes $f$. The answer is 'No,' due to a theorem of Sacks whose proof is quite simple. Actually it has mainly been answered by Robin Kothari [citing another answer]: if the probability for the TM to be correct is greater than $\frac{1}{2}$, then one can look for all $n$ at all the possible oracle computations with input $n$ and find the output which gets the "majority vote", i.e. which is produced by a set of oracles of measure more than $\frac{1}{2}$ (this can be done effectively). The argument even extend to smaller probabilities: suppose the TM outputs f with probability $\epsilon >0$. By Lebesgue's density theorem, there exists a finite string $\sigma$ such that if we fix the first bits of the oracle to be exactly $\sigma$, and then get the other bits at random, then we compute $f$ with probability at least 0.99. By taking such a $\sigma$, we can apply the above argument again.