34
\$\begingroup\$

It's a fairly long-standing principle of PPCG that languages are defined by their implementations; in other words, the language specification is entirely ignored, and we look at the behaviour of an implementation in practice to determine how the program works. This means that if no interpreter can run the program (e.g. because existing interpreters are buggy), the program can't be submitted at all.

It's also a fairly long-standing principle of PPCG that submissions should work on all possible inputs (even if the corresponding output would be far too complex for a system to print, or far too large for a computer to be able to store); and on the flip side, submissions are commonly so inefficient that they couldn't possibly run in practice even on fairly small inputs. (For example, a program that uses O(22n) time or memory would typically be considered an appropriate submission.) As such, submissions tend to be verified not by using test cases (which would be impossible for most challenges, as they accept an infinite space of possible inputs), but rather by giving a proof that the submission would work (or even more indirectly, by challenging people to find a counterexample and assuming the answer is correct if nobody can find one).

However, there's something of a contradiction here. We're starting off by saying "following the specification is not enough, you have to run the program to prove it works". Then we're saying "it's OK if the program can't actually run in practice, just so long as it could run in theory if you had an infinitely powerful computer". From my point of view, it doesn't make sense to have these rules at the same time; we could have either individually, but the combination is problematic. We have a rule that language specifications aren't relevant – and yet people repeatedly resort to them in an attempt to demonstrate that their program works for all input (because trying to prove facts about a language implementation is almost impossible in practice unless using a certified compiler, as the implementation tends to be much more complex than the specification). We have a rule that languages can't exploit their own limited integer sizes to simplify the problem – and yet we define the behaviour of the language on those integers via observing what the implementation does, and it doesn't.

How can we reconcile these rules to be more compatible with each other?

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – Mego Jun 12 '17 at 15:39
  • 3
    \$\begingroup\$ Disallowing submissions that can't run on any computer would invalidate entire swaths of questions, like "print the largest number in 10 bytes" or "slowest growing function in 100 bytes." ALL of the answers are effectively non-computable, either requiring billions of stack space or trillions of bits to hold the answer. \$\endgroup\$ – Draco18s Jun 13 '17 at 18:24
  • 4
    \$\begingroup\$ This seems way too nitpicky to me. We haven't had any problems before with these rules, and they've been in place for years. I don't think there's any real confusion about what is meant - languages are defined by their implementation, so you have to have a program for the language, not just a text document that describes the language. You can require arbitrarily-large amounts of time and memory for a given solution. \$\endgroup\$ – Mego Jun 16 '17 at 20:47
5
\$\begingroup\$

A question can allow for theoretical solutions, on a case-by-case basis

When in doubt, an answer must be runnable. It's ok if it takes an excessive amount of time or memory, as long as it can be tested for smaller values and shown to scale.

If a question is ok with assuming that memory is infinite or basic integer types count as arbitrarily large, then they must say so. There can be an exception for challenges that inherently require answers to be unrunnable, like a "longest running terminating program" challenge, but I think the questions you linked should be edited for clarification.

Another interesting edge case would be a language implementation that degrades over a long period of time. Would we even know if an esolang interpreter would fail if run for 2^32 seconds? Should it retroactively invalidate answers if we find out later?

\$\endgroup\$
-2
\$\begingroup\$

Languages are defined by an idealized version of their implementation

For example, if you are working in python and are using the official python implementation, you are actually using one that has all limits set arbitrarily high, and executes immediately.

\$\endgroup\$
-7
\$\begingroup\$

As long as no one can disprove that it works, it's fine

When submitting a potentially problematic answer, the user can specify which implementation it would theoretically work on, and, as long as no one disproves that it would work in that implementation, on a computer with infinite resources, the submission is valid.

\$\endgroup\$
  • 1
    \$\begingroup\$ How do you define the behaviour of an implementation on an infinite computer, though? Most programming language implementations I'm aware of have baked-in assumptions that the computer is finite (including specific hardcoded limits for, e.g., the amount of memory addressable by a single process). \$\endgroup\$ – user62131 Jun 12 '17 at 1:02
  • 2
    \$\begingroup\$ The answerer should have to prove that it works. The burden of proof should not be on the community. \$\endgroup\$ – Stephen Jun 18 '17 at 11:22
-7
\$\begingroup\$

Very slow solutions should be non-competing

Note: non-competing does not mean the user must notpost her solution. Rather, the solution should be posted and labeled "non-competing."

Per this consensus, the OP should accept answers after verifying them. That is, if some answers cannot be verified (either by OP or other members), they are not eligible to get accepted, meaning they are non-competing.

Thus, a slow (practically impossible to run) program should be non-competing, as it is impossible to verify whether the solution actually works.

Of course, if the solution becomes not-slow due to improvement in technology, it could become competing. Conversely, a slow solution should not be competing until it can be verified.

\$\endgroup\$
  • 3
    \$\begingroup\$ How do you make this objective? That is, if the question doesn't state a complexity bound, what complexity bound are we assuming by default? Additionally, I don't think it solves the original issue; even if the program runs in O(n), it might be untestable because the problem might require it to work for very large n (by default, it'd have to work for arbitrarily large n, including values too high to test, and even when limits are stated in the question, they're often in the billions or larger). \$\endgroup\$ – user62131 Jun 12 '17 at 7:12
  • \$\begingroup\$ @ais523 Reworded. \$\endgroup\$ – JungHwan Min Jun 12 '17 at 15:04
  • \$\begingroup\$ The difference between a slow solution and a solution in an unimplemented language is that a slow solution can eventually become not-slow with hardware and software upgrades, without changing the solution or the language. An unimplemented language will stay unimplemented until it is implemented. \$\endgroup\$ – Mego Jun 12 '17 at 15:21
  • \$\begingroup\$ @Mego That is indeed a fair point. However, it is highly unlikely that such an improvement could be made in the short period when the challenge is on the first few pages of "newest". A slow solution could be non-competing until somebody can verify that the program functions as intended, not just in theory. \$\endgroup\$ – JungHwan Min Jun 12 '17 at 15:35
  • \$\begingroup\$ I don't think long-running solutions should be marked as non-competing. We should assume good faith - every solution is valid until proven invalid. \$\endgroup\$ – Mego Jun 12 '17 at 15:38
  • \$\begingroup\$ @Mego Relevant; it is recommended that the poster verify solutions that she is accepting. If some solutions cannot be verified, I don't think they're eligible for getting accepted, which (imo) is synonymous to non-competing. \$\endgroup\$ – JungHwan Min Jun 12 '17 at 15:47

You must log in to answer this question.