A computer given an infinite stream of truly random bits is more powerful than a computer without one.  The question is: is it powerful enough to solve the halting problem?That is, can a probabilistic computer determine whether or not a deterministic program halts?Example of a probabilistic computer doing something a deterministic one can't: Consider a small program (less than a kilobyte in length) that outputs a string with Kolmogorov complexity greater than a gigabyte.  The Kolmogorov complexity of a string is the length of the shortest deterministic program producing that string.  Thus, by definition, a deterministic program cannot produce a string whose complexity is greater than its own length.  However, if given an infinite stream of truly random bits, a small program is capable of achieving the task with 99.99999...% success by simply echoing out, say, 10 billion random bits and hoping the Kolmogorov complexity of those bits is high enough.  Hence, producing a string of superior Kolmogorov complexity is within the possibility horizon of the probabilistic program, but not possible at all for the deterministic program.That said, I'm wondering if it is possible to use truly random bits to hacksaw at the halting problem.  For instance, an algorithm might randomly generate theorems and prove/disprove/discard them until it knows enough to prove/disprove that a given deterministic program halts.
Can a probabilistic Turing machine solve the halting problem?
computability;randomness;turing machines