8
$\begingroup$

Suppose we have an algorithm like:

n = 0
REPEAT
 c = randomInt(0,1)
 n = n + 1
UNTIL (c == 0)
RETURN n

(Assumuing the random number generator produces "good" random numbers in the mathematical sense.)

I understand that there is no number $n \in \mathbb{N}$ such that the algorithm is guaranteed to terminate after fewer than $n$ steps. However, the probability of terminating after some finite number of steps is 1.

Is there a convention among computer scientists to call an algorithm like this either "terminating" or "non-terminating"?

Raphael
73.3k31 gold badges183 silver badges403 bronze badges
asked Nov 10, 2014 at 19:46
$\endgroup$
1

1 Answer 1

11
$\begingroup$

The formal, unambiguous way to state this is "terminates with probability 1" or "terminates almost surely". In probability theory, "almost" means "with probability 1".

For a probabilistic Turing machine, termination is defined as "terminates always" (i.e. whatever the random sequence is), not as "terminates with probability 1". This definition makes decidability by a probabilistic Turing machine equivalent to decidability by a deterministic Turing machine supplied with an infinite tape of random bits — PTM are mostly interesting in complexity theory. In applied CS, though, computations that always give the correct result but terminate only with probability 1 are a lot more useful than computations that may return an incorrect result.

answered Nov 10, 2014 at 22:17
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.