Is it permitted for a submission to terminate merely with probability 1?

The question is in the title. I'm interested in submissions that terminate with probability 1 but have unbounded worst case running times.

This is related to the question Do programs have to terminate?, but that question is specifically about submissions that definitely do not terminate.

For example, the challenge is "sort the array". Should an implementation of a randomized bogosort (shuffle the elements and see if the result is sorted) be permitted?

• Nov 23, 2018 at 15:08
• As pointed out in a comment, those solutions actually may not terminate in real implementation, because of PRNG properties. Nov 27, 2018 at 11:32
• @user202729 Could you link to the actual comment? Dec 1, 2018 at 19:54
• @mbomb007 Oops, wrong link. The comment. Dec 2, 2018 at 5:43
• If someone is persuaded by my comment, maybe they should write up an answer on that basis. But I don't think that this is a problem, as long as an ideal version of the algorithm works for all inputs - after all, because of minor implementation-specific details like "having a limit on memory used", most solutions by brute force don't work for large inputs, and consensus is fine with that. Dec 3, 2018 at 0:45

Yes

Banning submissions that work with a probability of 1 removes the option of rejection sampling which is an approach that already has been used countless times.

• I think the main argument in favour of yes is that the probability that the program runs forever is 0 Nov 20, 2018 at 22:23
• @LuisMendo That is just rephrasing the question. Nov 25, 2018 at 16:04
• And yet it is a much more solid argument than just saying "it has already been used countless times" Nov 25, 2018 at 16:18
• Every computer program has probability 1 it terminate (but possible without return the result)
– user58988
Nov 25, 2018 at 18:38
• @RosLuP No, not at all. Following program's probability to terminate is 0.5: (pseudocode) if( rand() > 0.5 ){ while(true){ print("something"); } } Nov 25, 2018 at 19:28
• The question asker can require a guaranteed termination if they want to though, right? Nov 27, 2018 at 19:32

No

If there is the possibility that a program does not terminate, then it does not actually solve the task. If a program does not do what it is supposed to do, it is not valid as an answer.

• Just in general, for a discussion try to only post the side of the argument you agree with. Letting someone who disagrees make the other post will (hopefully) encourage discussion, rather than just a vote. Nov 20, 2018 at 22:28
• @FryAmTheEggman Everyone is encouraged to post their own opinions. I saw arguments for both so posted both, also with the thought that it might prevent a FGITW effect. Nov 20, 2018 at 22:44
• You can see some more discussion about it here (I've linked to a comment specifically talking about why this wasn't thought to be a great idea). But basically this tends to actually cause a greater FGITW since people will tend not to look for future posts. This isn't a policy or anything, you can do what you want, but personally I think it makes these polls worse. Nov 20, 2018 at 23:59
• @FryAmTheEggman I don't think this is the case - and I hope I did not have any bias as I was undecided how to vote - so I thought it was best to present both arguments that were important to me. Nov 21, 2018 at 9:03
• This argument doesn't make sense as written because if a program terminates with probability 1 (as opposed to probability 0.99) then there is no possibility that it does not terminate. Nov 23, 2018 at 15:16
• On the other hand, in bogosort-like examples, some algorithms actually might never terminate for sufficiently large inputs, because the PRNG isn't capable of producing the specific random sequence that gives a correct answer. For a specific example, on a TI-83 calculator the PRNG only has about 4.6x10^18 possible states, so it's very likely that randIntNoReps(1,25 is not actually capable of producing the output {1,2,3,...,25} no matter how many times you try. Nov 23, 2018 at 15:22