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

Question

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?

Answer 1

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.

Answer 2

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.