Can randomness add computability?

Question

I have been looking at Church's Thesis, which asserts that all intuitively computable functions are recursive. The definition of recursion does not allow for randomness, and some people have suggested exceptions to Church's Thesis based on generating random strings. For example, using randomness one can generate strings of arbitrarily high Kolmogorov complexity but this is not possible with recursion alone.

However, these exceptions are not true functions. They generate multiple outputs, which collectively have some property. A recursive function takes an inputs and outputs a single unique answer. So some people do not consider these random coin-flips to be true exceptions to Church's Thesis.

My question is whether it is possible to use randomness to get something which is still essentially deterministic like a function, but is non-recursive.

For example, if we had a sequence of functions $F^r_i(n)$, which are recursive functions relative to a random tape oracle $r$, which have the property that for some function $g(n)$, we have $F^r_i(n) = g(n)$ with probability approaching $1$ as $n \rightarrow \infty$ (the probability taken over the random tapes). Furthermore, $g$ would not be recursive itself.

Here, I am suggesting relativizing to $r$, rather than having $r$ as an input, because one might need arbitrarily many random cells. This could be thought of as allowing to "intuitively compute" $g$.

Answer 1

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.

Answer 2

There is an article by Leonid Levin that the OP might like:

• http://arxiv.org/pdf/cs.CC/0203029.pdf
• informal overview: http://www.cs.bu.edu/fac/lnd/expo/gdl.htm