3
$\begingroup$

Suppose I have an algorithm that works as follows when invoked: it calls itself recursively with probability $0 < p < 1$ and terminates with probability $1-p$. Does this algorithm terminate? On the one hand you can show that $\lim_{n \to \infty}p^n = 0$, so it must terminate at some point before infinity. On the other hand it also seems reasonable to say that it is possible for the algorithm to call itself repeatedly indefinitely. What is the correct interpretation?

$\endgroup$
7
$\begingroup$

The question "Does it terminate?" isn't well-formed. You need to define more precisely what you mean by that question before it can be answered.

  • Is it guaranteed to terminate on all possible execution traces? No. There exists an execution trace where it never terminates.

  • Does it terminate with probability one? Yes. If you flip a coin until you first get heads, the probability of getting a never-ending sequences of tails is zero.

  • Is the expected number of repetitions until termination finite? Yes. If you flip a coin until you first get heads, the expected number of flips is finite (it is the expected value of a geometric distribution).

So, the answer to the question depends upon precisely which of those questions you meant to ask. Normally, that's about all we can say.

Usually, if it matters, we try to define what we mean by "terminate" more precisely. For instance, in the definition of the Halting Problem, "terminates" is specified to mean "guaranteed to terminate on all possible inputs and all possible execution traces", and the formalization of the Halting Problem implicitly restricts us to deterministic algorithms (more precisely, to Turing machines, which are necessarily deterministic; they don't have access to randomness). Anyway, in general, if the differences matter, it's your job to specify exactly which meaning you have in mind.

$\endgroup$
  • $\begingroup$ Yes, I meant it in the context of the Halting Problem, so I guess that means it isn't guaranteed to halt since there exists an execution trace where it doesn't terminate? $\endgroup$ – hesson May 30 '14 at 21:04
  • 1
    $\begingroup$ @hesson, In the context of the halting problem, we normally consider only deterministic algorithms -- formally, the precise definition of the halting problem is defined in terms of Turing machines, which are by definition deterministic -- so randomized algorithms aren't even on the table. In other words, it is not even possible to express the kind of algorithm you are mentioning as a Turing machine, so it's out-of-bounds for the usual way that we formalize the Halting problem. Thus, in the context of the Halting problem, this question does not arise (and can not arise). $\endgroup$ – D.W. May 30 '14 at 22:16
  • $\begingroup$ See also this $\endgroup$ – phs Nov 12 '14 at 8:23

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.