7
\$\begingroup\$

This is related to Martin Ender's question here, but in my opinion different enough to warrant a separate meta post.

Are programs required to provably terminate, even if an algorithm that is not proven to terminate works for the given input range?

A basic example would be having a program calculate the nth term in the sequence A006577. It is unknown whether or not all values of n eventually reach 1, and therefore it is impossible to have a program calculate the nth term of this sequence in a finite amount of time. However, it has been proven for all values up to 260, which is satisfactory for most purposes.

This question also expands to situations where there are algorithms proven to terminate. Let's assume that there is a problem A that can be solved with 2 algorithms B and C. B is mathematically proven to always solve problem A in a finite amount of time. Algorithm C is not proven as such, but despite estensive testing up to numbers vastly exceeding the maximum value of an int32, there have been no such numbers that cause it to never termimate. Would an answer using algorithm C be acceptable?

\$\endgroup\$
  • 4
    \$\begingroup\$ I think only very few (if at all) of the algorithms used to answer any challenge here have been proven to always terminate, and I don't think we should change that. \$\endgroup\$ – flawr Nov 14 '16 at 8:44
  • \$\begingroup\$ There is a challenge on this subject codegolf.stackexchange.com/questions/97004/… \$\endgroup\$ – AlexRacer Nov 19 '16 at 14:35
  • \$\begingroup\$ Proofs about programs are hard to prove correct. \$\endgroup\$ – trichoplax Nov 19 '16 at 21:21
10
\$\begingroup\$

Yes, programs that are not proven to terminate are valid

As flawr mentioned in a comment:

I think only very few (if at all) of the algorithms used to answer any challenge here have been proven to always terminate, and I don't think we should change that.

Deciding whether or not a single program terminates can be a daunting task. Deciding whether or not every program posted terminates is unreasonable and infeasible, since it cannot be done programmatically. Furthermore, that would conflict with challenges that allow solutions to require infinite time (which is most of them).

\$\endgroup\$

You must log in to answer this question.

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