# Could Turing machines + random "do something" Turing machines cannot?

A machine G that outputted a bit randomly could decide any language (by guessing luckily). Formally, for all languages L, for all natural numbers k, if you give G k finite-length inputs, G has 1/2^k probability of deciding the "k-sampling" of L.

Turing machines cannot decide some languages. Formally, for some languages L, for all Turing Machines M, for all natural numbers k, for some natural numbers i, if you give M k finite-length inputs, it has 0 probability of deciding the "k-sampling" of L (since, for sufficiently small i, M may not halt in i steps).

Therefore, a simple machine that outputted randomly, though unlikely, could outperform some of the lengthiest Turing machines.

This is a contrived example. However, 1/2^k > 0; Maybe random can do something that Turing machines cannot. Hence the motivation for this question:

Could Turing machines + random "do something" Turing machines cannot?

If so, what does that mean for the Church-Turing thesis that everything that can be computed can be computed by a Turing machine?

This answer assumes some familiarity with complexity classes. You may be interested in the complexity class RP. What is known is that $$\textbf{P}\subset \textbf{RP}\subset \textbf{NP} \subset \textbf{EXPTIME}$$. What this means is that we can simulate a Turing machine that is allowed to flip random bits and answers in polynomial time with a nondeterministic Turing machine, which in turn can be simulated by a Turing machine that runs in exponential time. So the answer to your question is no - any Turing machine that can use randomness can be simulated by one that doesn't but potentially takes longer.

• I’m still learning about complexity classes. Are you saying randomized recursively enumerable is equivalent to recursively enumerable? How does that follow from RP being a subset of NP? Is randomness always a subset of non-determinism? May 2, 2020 at 21:45

This sort of question depends on pinning down what "do something" means. For example, here are a pair of results, one negative and one positive.

On the level of individual problems, there's a straightforward negative answer:

Negative: There is no specific decision problem which can be solved with randomness but can't be solved classically. More precisely, if $$X$$ is any set which is computable relative to any $$Y\in\mathcal{Y}$$ with $$\mathcal{Y}$$ a set of oracles with positive measure, then $$X$$ is computable.

However, we can also ask about "higher-order" tasks (mass problems), where there is not a single correct solution but rather many possible ways to achieve the desired goal. Here we do see some positive results:

Positive: There is a structure $$\mathfrak{S}$$ such that we can't build a copy of $$\mathfrak{S}$$ computably but we can build a copy of $$\mathfrak{S}$$ computably relative to even a little randomness - more precisely, the set of oracles computing copies of $$\mathfrak{S}$$ is exactly the set of noncomputable sets (any nontrivial computational power lets us build $$\mathfrak{S}$$).

The negative result is an easy measure-theoretic exercise; the positive result (the Slaman-Wehner theorem) is significantly more difficult.

• Are oracles deterministic black boxes? If so, why would would the negative result imply something about a non-deterministic black box: randomness? May 3, 2020 at 11:30