16
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Note that a non-deterministic machine, doesn't extend computability. From this, it is hard to believe that randomness can. $\endgroup$
    – Lucas K.
    Mar 10, 2011 at 15:05
  • 6
    $\begingroup$ The program that enumerates every string generates strings of arbitrarily high Kolmogorov complexity. $\endgroup$ Mar 10, 2011 at 15:34
  • $\begingroup$ The answers to this question are quite satisfactory, but don't really provide citable references. “Fact ①” from this other question on CSTheory StackExchange provides a few for the fact that “if $L$ is computable by a non-measure-zero set of oracles, then it is computable”: Sacks, Degrees of Unsolvability (1963), §10, theorem 1 (p. 154); Nies, Computability and Randomness (2009), theorem 5.1.12 (p. 169); or Downey & Hirschfeldt, Algorithmic Randomness and Complexity (2010), corollary 8.2.12 (p. 358). $\endgroup$
    – Gro-Tsen
    Nov 27, 2023 at 15:39

2 Answers 2

20
$\begingroup$

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.

$\endgroup$
1
  • 10
    $\begingroup$ I believe that the result "randomness doesn't help computability" goes back to a 1956 paper, "Computability by probabilistic machines" by K. de Leeuw, E.F. Moore, C.E. Shannon, and N. Shapiro [in "Automata Studies" Princeton Univ. Press, pp. 183-212]. In modern set-theoretic terminology, the result can be phrased as "any ground model real that is recursive relative to a random (over that ground model) real is in fact recursive." $\endgroup$ Mar 10, 2011 at 13:42
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.