If languages are defined by their implementations, how do we judge answers that can't run on any existing computer?

Question

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(2²ⁿ) 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?

Answer 1

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?

Answer 2

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.

Answer 3

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.

Answer 4

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.