Can a probabilistic Turing machine solve the halting problem?

Question

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.

Answer 1

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.

Answer 2

It depends on what you mean by a probabilistic algorithm determines some predicate.

There is a trivial probabilistic algorithm P such that, for a deterministic Turing machine M,

• P(M) accepts with nonzero probability if M halts,
• P(M) never accepts if M does not halt, and
• P(M) halts with probability 1 for every M.

Therefore, the probabilistic algorithm P solves the halting problem for deterministic Turing machines in this sense. (Here “M halts” means “M halts on the empty input.”)

However, if you strengthen the requirement in any sensible way, it is unlikely that you can solve the halting problem for deterministic Turing machines anymore. For example,

• If you require P(M) to halt always instead of merely with probability 1, then it is clear that P can be simulated by a deterministic algorithm. (See Wikipedia for an explanation of the difference between “always” and “with probability 1.”)
• If you make the error bounds strict by requiring P(M) to halt and give the right answer with probability strictly greater than 1/2 for every M (that is, you do not care if P(M) does not halt or halts and give the wrong answer in the rest of the cases), then P can be simulated by a deterministic algorithm by using the argument stated in Karolina Sołtys’s answer.

Therefore, a probabilistic algorithm cannot solve the halting problem for deterministic Turing machines in these senses.

Answer 3

In general, if you have a probabilistic Turing machine $P$ solving some decision problem, you can always simulate it deterministically by running $P$ for every possible value of the randomness and outputting the majority answer of $P$. Therefore, no probabilistic Turing machine can solve an undecidable decision problem.

I think this was the meaning of Raphael's comment.

Answer 4

If the Lebesgue measure of those oracles that compute a set $A\subseteq\mathbb N$ is positive, then $A$ is computable. This goes back to de Leeuw, Moore, Shannon, and Shapiro in 1956 and Sacks in 1963. For a discussion see Downey and Hirschfeldt's new book Algorithmic randomness and complexity. As other answers have mentioned, the idea is to take a majority vote. (While this can be done computably, there is no claim that the algorithm is efficient.)

de Leeuw, K., Moore, E. F., Shannon, C. E., and Shapiro, N. Computability by probabilistic machines, Automata studies, pp. 183–212. Annals of mathematics studies, no. 34. Princeton University Press, Princeton, N. J., 1956.

G. Sacks, Degrees of Unsolvability, Princeton University Press, 1963.