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