22
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ See also codegolf.meta.stackexchange.com/questions/12498 \$\endgroup\$ – Misha Lavrov Nov 23 '18 at 15:08
  • 2
    \$\begingroup\$ As pointed out in a comment, those solutions actually may not terminate in real implementation, because of PRNG properties. \$\endgroup\$ – user202729 Nov 27 '18 at 11:32
  • \$\begingroup\$ @user202729 Could you link to the actual comment? \$\endgroup\$ – mbomb007 Dec 1 '18 at 19:54
  • \$\begingroup\$ @mbomb007 Oops, wrong link. The comment. \$\endgroup\$ – user202729 Dec 2 '18 at 5:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Misha Lavrov Dec 3 '18 at 0:45
28
\$\begingroup\$

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.

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

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Nov 20 '18 at 22:28
  • 8
    \$\begingroup\$ @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. \$\endgroup\$ – flawr Nov 20 '18 at 22:44
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Nov 20 '18 at 23:59
  • \$\begingroup\$ @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. \$\endgroup\$ – flawr Nov 21 '18 at 9:03
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Misha Lavrov Nov 23 '18 at 15:16
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ – Misha Lavrov Nov 23 '18 at 15:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .