Is code that terminates on a random condition guaranteed to terminate?
Posted
by
Simon Campbell
on Programmers
See other posts from Programmers
or by Simon Campbell
Published on 2012-11-29T07:16:28Z
Indexed on
2012/11/29
11:20 UTC
Read the original article
Hit count: 397
If I had a code which terminated based on if a random number generator returned a result (as follows), would it be 100% certain that the code would terminate if it was allowed to run forever.
while (random(MAX_NUMBER) != 0): // random returns a random number between 0 and MAX_NUMBER
print('Hello World')
I am also interested in any distinctions between purely random and the deterministic random that computers generally use. Assume the seed is not able to be known in the case of the deterministic random.
Naively it could be suggested that the code will exit, after all every number has some possibility and all of time for that possibility to be exercised. On the other hand it could be argued that there is the random chance it may not ever meet the exit condition-- the generator could generate 1 'randomly' until infinity.
(I suppose one would question the validity of the random number generator if it was a deterministic generator returning only 1's 'randomly' though)
© Programmers or respective owner