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.

  • 3
    $\begingroup$ @downvoter: This shouldn't have received a down-vote without a comment. $\endgroup$ – Dave Clarke Oct 28 '10 at 7:14
  • 3
    $\begingroup$ What prevents a deterministic TM from enumerating all cases? Here, checking a guess is the problem, not guessing itself. Note also that you cannot really say you are strictly more powerful if you create the desired result only with a probability $p<1$. $\endgroup$ – Raphael Oct 28 '10 at 7:19
  • 1
    $\begingroup$ "a deterministic program cannot produce a string whose complexity is greater than its own length." It is enough that some other deterministic machine outputs the same output. Note that deterministic TMs can simulate not only probabilistic ones, but even nondeterministic TMs (with arbitrary number of alternations). $\endgroup$ – Kaveh Oct 28 '10 at 12:02
  • $\begingroup$ Yesterday I was about to say -- looking at Kaveh et al -- this was too basic a question for this site (same question for NTM is a basic result in every first theory course). Given that it took quite an effort to formalize "probabilistic TM", I am glad I did not. $\endgroup$ – Raphael Oct 29 '10 at 22:30
  • 1
    $\begingroup$ And see the clarifying answers to my earlier related TCS question: cstheory.stackexchange.com/questions/1263/… $\endgroup$ – Joseph O'Rourke Nov 1 '10 at 17:52

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.
  • $\begingroup$ Thanks for elaborating my "just enumerate" comment! ;) Two technical comments: At bullet point one, you mean $>2^{i-1}$? At the end, you mean $S(Q)$? $\endgroup$ – Raphael Oct 28 '10 at 8:31
  • 1
    $\begingroup$ Note that if you do not require P to always halt, it is trivial to construct even a deterministic Turing machine P which accepts if and only if the given deterministic Turing machine halts. $\endgroup$ – Tsuyoshi Ito Oct 28 '10 at 12:13
  • $\begingroup$ What is your assumption? You cannot negate a probabilistic Turing machine unless it is guaranteed to eventually halt. $\endgroup$ – Tsuyoshi Ito Oct 28 '10 at 14:39
  • $\begingroup$ The halting probability is taken over the additional string AND input words, or what ? $\endgroup$ – M. Alaggan Oct 28 '10 at 22:32
  • 1
    $\begingroup$ @Mohammad ALAGGAN: No, that part is correct as is written: the probability is taken over only the additional string (specifying the results of the coin flips). Because we are not assuming any probability distribution on the input string, the probability over the input string is not well-defined. Even if a probability distribution on the input string is defined, the high probability of correct answer over the input string implies only that the algorithm is correct for most inputs, which is different from the usual requirement on an algorithm. $\endgroup$ – Tsuyoshi Ito Oct 29 '10 at 15:35

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.

  • $\begingroup$ Forgive my ignorance, but what's the difference between halting ''always'' and halting ''with probability 1''? $\endgroup$ – Rob Simmons Oct 29 '10 at 0:46
  • 1
    $\begingroup$ @Rob: I think that it is a tricky point. Consider a simple probabilistic Turing machine which just tosses a coin repeatedly until the outcome is the heads. This Turing machine halts except when all coin tosses result in the tails. Therefore, it halts with probability 1, but it does not always halt. $\endgroup$ – Tsuyoshi Ito Oct 29 '10 at 1:08
  • $\begingroup$ I found an explanation of the difference between “always” and “with probability 1” in Wikipedia, and I added the same link in the answer. $\endgroup$ – Tsuyoshi Ito Oct 29 '10 at 1:21
  • $\begingroup$ If you allow for P(M) to fail by not halting, then I don't know how you can do a deterministic simulation. For instance, suppose you run your deterministic simulation on some set of length-N prefix strings, and after some length of time, < 50% of the prefixes have halted and given an answer. How do you know whether the remaining prefix strings simply need more time to return an answer, or if they are all stuck in an infinite loop as part of the failure condition? If the former, you continue to wait. If the latter, you terminate the current round and run again on all prefixes of length-N+1. $\endgroup$ – Mike Battaglia Sep 22 '17 at 4:15
  • $\begingroup$ But this is impossible to determine, because it is the halting problem! We have no way of knowing whether the Turing machine will halt on those inputs or not. $\endgroup$ – Mike Battaglia Sep 22 '17 at 4:18

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.