Skip to main content
Non-determinism is not involved in the question.
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Post Closed as "Duplicate" by D.W., David Richerby, Kevin, FrankW, Juho
Tweeted twitter.com/#!/StackCompSci/status/531914009495076864
edited body
Source Link

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 steps 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"?

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 steps than $n$. 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"?

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"?

Source Link
Loading