7
$\begingroup$

I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions.

So I was thinking, much in the way that some primality testers are probabilistic(they give you yes or no but have a chance to be wrong). Would it be possible to build a probabilistic halting problem solver? One that reports within a certain degree of error, whether a problem halts or not?

Improve this question
$\endgroup$
3
  • $\begingroup$ there exist halt-detection algorithms that succeed in giving the correct answer with some unknown probability and return "inconclusive" otherwise. these algorithms are studied eg in busy beaver research, automated thm proving, program termination analysis, & some other contexts. $\endgroup$
    – vzn
    Commented Feb 14, 2014 at 5:46
  • $\begingroup$ @vzn The sample algorithm running the input for $T$ steps also has the same properties. How are your algorithms better? Can you quantify it? $\endgroup$
    – Yuval Filmus
    Commented Feb 14, 2014 at 6:12
  • $\begingroup$ @YuvalFilmus it is probably theoretically impossible to compare these algorithms much; one way is mentioned in my answer on this question algorithm to solve halting problem... its an active area of research but also at the fringes of TCS without much widespread recognition of its significance/interconnection. the algorithms succeed in identifying some inputs that dont halt, which cannot be said of just running the TM on the inputs. intend to write up more detail on a blog at some pt (have various links). $\endgroup$
    – vzn
    Commented Feb 14, 2014 at 16:47

1 Answer 1

Reset to default
6
$\begingroup$

It depends what you mean by "probabilistic". There are at least two interpretations. First, the algorithm has some probability of success for every input. Second, the algorithm succeeds on a certain fraction of inputs.

For the first interpretation, it is easy to rule out such an algorithm: probabilistic computation can be simulated (inefficiently but effectively) using deterministic computation, by trying all possible coin tosses.

For the second interpretation, we will have to work a bit harder. Suppose that your algorithm is guaranteed to work with an asymptotic success probability of $2/3$. That means that the fraction of inputs in $[1,N]$ for which it gives the correct answer is some $p_N \to 2/3$. Now suppose you're interested in a certain program $P$. It seems that under a reasonable encoding of programs, you would be able to come up with a long stretch $[M,10M]$ (say) of programs equivalent to $P$. By taking $M$ large enough, it should be the case that by taking the majority vote on the answer of a "probabilistic" algorithm on all of these equivalent programs, you will be able to ascertain whether $P$ halts or not. This rules out even this interpretation of a "probabilistic" algorithm.

Improve this answer
$\endgroup$
11
  • $\begingroup$ nice proof but it doesnt apply to algorithms that have unknown probability. $\endgroup$
    – vzn
    Commented Feb 14, 2014 at 5:49
  • $\begingroup$ And what might these be? My logic is not intuitionistic, so every program either halts or doesn't halt, even if the axiom system is not strong enough to decide which. $\endgroup$
    – Yuval Filmus
    Commented Feb 14, 2014 at 6:11
  • $\begingroup$ another assumption here in this proof sketch is that the probabilistic algorithm would have independent probability on equivalent machines ie it would return the correct answer with same independent probability. but thats a big stretch. eg it could not be independent and with high correlation get the wrong answer for equivalent machines etc. $\endgroup$
    – vzn
    Commented Feb 14, 2014 at 16:52
  • 1
    $\begingroup$ There is no such assumption. In the second interpretation, the algorithm is completely deterministic, it just doesn't always tell the truth. I give an interpretation for a statement like "the algorithm outputs the correct answer on a 99% fraction of the inputs", and under this interpretation the argument should work. More generally, randomized algorithm can be simulated deterministically, so if we're not interested in the running time, we can always assume that the algorithm is deterministic. $\endgroup$
    – Yuval Filmus
    Commented Feb 14, 2014 at 21:44
  • $\begingroup$ "By taking M large enough, it should be the case that by taking the majority vote on the answer of a "probabilistic" algorithm on all of these equivalent programs," — there seems to be an assumption that if you ran the same experiment on different instances of the same machine, the algorithm has the same independent probability. but what if it is 100% guaranteed to fail on some particular instance, no matter how it is "padded" (where here "padding" refers to adding irrelevant states or structures to the TM that do not alter its function.) so defns must be very careful in this type of proof $\endgroup$
    – vzn
    Commented Feb 14, 2014 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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