25
\$\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\$
5
  • 1
    \$\begingroup\$ See also codegolf.meta.stackexchange.com/questions/12498 \$\endgroup\$
    – Misha Lavrov
    Commented Nov 23, 2018 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
    Commented Nov 27, 2018 at 11:32
  • \$\begingroup\$ @user202729 Could you link to the actual comment? \$\endgroup\$
    – mbomb007
    Commented Dec 1, 2018 at 19:54
  • \$\begingroup\$ @mbomb007 Oops, wrong link. The comment. \$\endgroup\$
    – user202729
    Commented Dec 2, 2018 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
    Commented Dec 3, 2018 at 0:45

2 Answers 2

Reset to default
30
\$\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\$
6
  • 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
    Commented Nov 20, 2018 at 22:23
  • \$\begingroup\$ @LuisMendo That is just rephrasing the question. \$\endgroup\$
    – Christopher King
    Commented Nov 25, 2018 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
    Commented Nov 25, 2018 at 16:18
  • \$\begingroup\$ Every computer program has probability 1 it terminate (but possible without return the result) \$\endgroup\$
    – user58988
    Commented Nov 25, 2018 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
    Commented Nov 25, 2018 at 19:28
  • 3
    \$\begingroup\$ The question asker can require a guaranteed termination if they want to though, right? \$\endgroup\$
    – Christopher King
    Commented Nov 27, 2018 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\$
6
  • 6
    \$\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
    Commented Nov 20, 2018 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
    Commented Nov 20, 2018 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
    Commented Nov 20, 2018 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
    Commented Nov 21, 2018 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
    Commented Nov 23, 2018 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
    Commented Nov 23, 2018 at 15:22

You must log in to answer this question.

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