Rulings on machine limits

Question

An awkward question comes up in code golf specs as to whether answer code is to be judged as running on a theoretical machine, an actual one with finite precision and memory, or somewhere in between. For example, see feersum's comments on Find the simplest value between two values that two posted answers arguably fail for large values due to limits of float representation.

For my question, I edited the spec afterwards to try to handwave away such limits, but I'd like to ask the community opinion on how and if to do this. It would also be nice to have a general agreement or standard options to avoid disagreements and avoid fiddly boilerplate in specs.

What are your thoughts on:

• Should questions specify bounds and precisions for inputs?
• Can and should questions handwave-away overflow and precision issues?
• Is it OK to submit answers that "eventually" give the answer, like one that loops through all 2^64 machine-representable integers regardless of input size?
• Should answers have to handle extreme cases like inputs 1 away from overflow?
• Are answers responsible for machine-precision failures like 21.0/7.0>3.0?
• What about stack-overflows for recursive code without tail-recursion?

Answer 1

I’d say that the asker is free to set (objective) rules and limits as they like. If any issues like overflow or precision are particularly relevant to the question, it would be good to specify what’s acceptable. Otherwise, I think it’s fine to ignore them.

Regardless, the solution should always produce the correct output for all test cases. As mentioned here, you shouldn’t post the answer until after it has successfully completed these. This is a nice way to weed out ridiculous or unverifiable answers.

But I think we should be lenient with extreme cases and slow solutions. There is often a tradeoff between length and efficiency when it comes to code golf, and every solution, language and system will have its limits (especially some of the more esoteric languages). So we shouldn’t rule out the clever recursive solution that has memory limitations, or the super-short FizzBuzz answer that overflows after 2^32, et cetera.

Answer 2

All of your questions seem to me like they're pretty much asking the same thing: "A computers can screw up, even if you programmed it correctly, because there are limitations on what you can do that stem from how the technology works. How (and should) we account for this?"

This answer is one suggestion that I think applies to every question you asked except 4. I'll answer that one separately.

---

Unless the question specifies otherwise, golfers should be allowed to assume exactly one of the following:

• Their machine is a real, physical computer that runs code.

• Their machine is theoretical. It lacks limitations of a real computer like stack overflows or lost precision. It runs your code flawlessly, even if no real computer in the universe ever could. It also runs it instantly.

Write a program that works by abusing integer overflows? Great! That's the first option.

Write a program that works by assuming that integers will never overflow, you can recurse as deep as you like, and precision is infinite? Great! That's the second.

There are so many great programs that have been written, but never run to completion, because the technology holds us back. At the same time, restrictions breed creativity, and great programs have been written abusing technological failure. I believe this proposal would allow both kinds of program to live in harmony on this site.

Answer 3

I'm just addressing question 4 (and to a lesser extent, 1) here. I gave my opinion about the others in my other answer.

---

Should answers have to handle extreme cases like inputs 1 away from overflow?

I don't think so. But how do we define "extreme"? That's exactly the issue. We can't exactly have rules about objective questions if we have the word "extreme" floating around.

If a question specifically includes input boundaries then your program must work for the every specified input. Note that saying "an integer" doesn't count as boundaries. It might technically mean -2^31 < n < 2^31-1 but that's usually not what people mean when they say it. If those are the bounds you want answers to work for, specifically say it.

If a question does not include boundaries, things get tricky. Here's my proposal. I think we, as a community, should decide on boundaries to default to for different archetypes of problems. It doesn't need to be comprehensive, but over time it could grow into something that could be relied on when the OP doesn't supply limits.

For example, something like this:

Problem Type: One integer input n. Guaranteed non-negative. More computationally intensive as n increases.

Default Boundaries: 0 < n < 21474

Or this:

Problem Type: Some number n of input strings.

Default Boundaries: 1 < n < 10, each string's length < 15

At the moment this is just an idea, I haven't even really fleshed it out. But does it seem feasible?

Answer 4

on the unambiguous answers

This question start wrong, because "Theoretical machine"

DOESN'T EXIST.

Exist one implementation, one compiler or better, one Os + compiler system + cpu and hardware. If one question request calculate in one programming language f(x) with x in [0, 8000] it has not significance until they specific, for example "in all more 2 widely used know compiler + Os in their default installation".

What it is easy to say for remove all ambiguity:
"the answer code function f has to return the right result
in the input range for example 0..10000 for the online compiler in   
http:/someone.it in less of 1 minute for each number of input
in its range."

Otherwise this is the C answer to all question:

main(){for(;;);}

Because all you accept solution that never return one result.

Op xnor is •

•What are your thoughts on: •Should questions specify bounds and precisions for inputs?

Yes and yes

•Can and should questions handwave-away overflow and precision issues?

No and no

•Is it OK to submit answers that "eventually" give the answer, like one that loops through all 2^64 machine-representable integers regardless of input size?

No the answer has to print its right result in the real machine, 
in the specified time the question assign to that calculus
for example in Tio web interface compilers. It can be 1 minute
if it is not specified (or one rationally good chose time)

•Should answers have to handle extreme cases like inputs 1 away from overflow?

I Don't understand 

•Are answers responsible for machine-precision failures like 21.0/7.0>3.0?

Yes yes and yes

•What about stack-overflows for recursive code without tail-recursion?

If stack end in the real machine of test in Tio, 
for some value of the range request in the question
the answer 
is invalid or not determinate