Can a probabilistic Turing machine solve the halting problem? 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.
edit: I just realized some of the things I wrote were total nonsense, sorry for that. Now I changed the proof and made the definition of probabilistic machine I am using more precise.

I don't know whether I get right your definition of probabilistic Turing machine: it is a machine with an additional tape on which an infinite incompressible string is written, and beside that it acts just like a deterministic machine? If we fix the incompressible string, the class we get doesn't seem to be interesting. 

I think we can define a probabilistic Turing machine in several ways. I will use a definition that seems quite natural (and for which my proof works ;) Let's define a probabilistic machine like that: it gets an additional tape on which some infinite string is written, we say that this machine decides a language $L$ if for every $x \in L$ it halts and accepts with probability $>\frac{1}{2}$, when the probability is taken over those additional random strings, and for every $x \not \in L$ it halts and rejects with probability $>\frac{1}{2}$.

We will now show that if there exists such a probabilistic machine $P$ that solves the halting problem for the deterministic machines, we could use it to build a deterministic machine $H$ that solves the halting problem for the deterministic machines - and we know that such a machine cannot exist.

Assume such $P$ exists. We can construct a deterministic machine $M$ that takes as an input a probabilistic machine $R$ with some input $x$, which


halts and accepts if and only if $R$ accepts $x$ (i.e. $R$ halts and accepts $x$ on more than half random strings).
halts and rejects if and only if $R$ rejects $x$ (i.e. $R$ halts and rejects $x$ on more than half random strings).
loops otherwise


Basically, $M$ will for all $i \in 1, 2, ...$ simulate $R$ on input $x$ and on every string from ${{0,1}}^i$ as a prefix of the string on $R$'s random tape. Now:


if for $>\frac{1}{2}$ prefixes of length $i$ $R$ halted and accepted without trying to read more than $i$ bits from the random tape, $M$ halts and accepts
if for $>\frac{1}{2}$ prefixes of length $i$ $R$ halted and rejected without trying to read more than $i$ bits from the random tape, $M$ halts and rejects
otherwise $M$ runs the simulation with $i := i+1$.


We have to convince ourselves now, that if $R$ accepts (rejects) $x$ with probability $p >\frac{1}{2}$, then for some $i$ it will accept (reject) for $>\frac{1}{2}$ prefixes of length $i$ of the random string without trying to read more than $i$ bits from the random tape. It is technical, but quite easy - if we assume otherwise then the the probability of accepting (rejecting) approaches $p >\frac{1}{2}$ as $i$ goes to infinity, hence for some $i$ it will have to be $p >\frac{1}{2}$.

Now we just define our deterministic machine $H$ solving the halting problem (i.e. deciding whether a given deterministic machine $N$ accepts a given word $x$) a as $H(N,x) = M(P(N,x))$. Note that $M(P(N, x))$ always halts, because deciding a language by our probabilistic machines was defined in such a way that one of those two always occurs:


the machine halts and accepts for more than half random strings
the machine halts and rejects for more than half random strings.