Answers should surely give a correct result within some arbitrary finite time bound
In other words, almost surely is not enough. PRNG's are assumed to be truly random.
- We often expect programs to run within reasonable time, where the definition on 'reasonable' depends on the problem. While a program could give an answer with probability of 1, the expected runtime is then arbitrarily long (possibly even infinite.
- Interesting challenges could be trivialized; for example, when verifying the correct solution is trivial compared to generating the correct result.
This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.
