17
\$\begingroup\$

The main motivation for my question is hash functions. Let's take an example challenge (although here's a real challenge):

Print 42 if the input is "the answer to life the universe and everything", 0 otherwise.

You might program this like this in Python 2:

print(42if raw_input()=="the answer to life the universe and everything"else 0)

You could also solve it like this:

from hashlib import*
print(42if sha1(raw_input()).hexdigest()=="2adc3e9a2bfb6b4ae5285b11dacc3990bb075585"else 0)

In this case it's not any shorter, but the idea is there.

Is this allowed? It's cryptographically impossible to find an input that fails, but theoretically there are inputs for which the program exhibits wrong behavior.

If this is allowed, how hard must it be to find an incorrect input before allowing it?

\$\endgroup\$
7
  • 3
    \$\begingroup\$ on one hand, i don't think your example should be allowed. on the other hand, i don't mind probabilistic primality tests... yeah, this contradiction probably means we need policy on this :P \$\endgroup\$
    – undergroundmonorail
    Commented Feb 11, 2016 at 17:29
  • \$\begingroup\$ What do you mean by "allowed"? Do you mean "eligible for deletion" or "eligible for downvotes" or something else entirely? \$\endgroup\$
    – Rainbolt
    Commented Feb 11, 2016 at 17:29
  • 2
    \$\begingroup\$ Surprisingly relevant: codegolf.stackexchange.com/a/1587/3808 \$\endgroup\$
    – Doorknob Mod
    Commented Feb 11, 2016 at 17:49
  • 2
    \$\begingroup\$ I guess there's also a difference between requiring proof for incorrectness and requiring a constructive proof. (It shouldn't be hard to prove that there is an infinite amount of strings hashing to any finite-length hexdigest, so it's easy to prove that the above program doesn't work, but finding a specific failing input is likely impossible.) \$\endgroup\$
    – Martin Ender Mod
    Commented Feb 11, 2016 at 17:51
  • \$\begingroup\$ @MartinBüttner I'm talking about finding a specific failing input. \$\endgroup\$
    – orlp
    Commented Feb 11, 2016 at 17:53
  • 1
    \$\begingroup\$ @MartinButtner : ​ stackoverflow.com/q/2658601/380772 ​ ​ ​ ​ \$\endgroup\$
    – user30594
    Commented Feb 13, 2016 at 2:30
  • \$\begingroup\$ Relevant: meta.codegolf.stackexchange.com/a/7990/45941 \$\endgroup\$
    – user45941
    Commented Jun 28, 2016 at 3:33

2 Answers 2

Reset to default
25
\$\begingroup\$

No

Given that we allow answers which have infinite memory and infinite processing time, if theoretically an input exists that makes the answer invalid, the answer should be deemed invalid. This holds true even if no explicit examples are or can be provided.

\$\endgroup\$
4
  • \$\begingroup\$ +1 I think this is generally the way to go, even if it makes probabilistic primality tests invalid. Although, I wonder the the policy should be when an open mathematical problem is involved. For example, I think "this program works iff the twin prime conjecture is correct" should be allowed. \$\endgroup\$
    – PhiNotPi
    Commented Feb 11, 2016 at 18:57
  • 3
    \$\begingroup\$ @PhiNotPi I would say that an answer is valid unless it can be proven invalid (not necessarily with a constructive proof). Since an answer that depends on the twin prime conjecture being true cannot be proven invalid without also disproving the twin prime conjecture (and if you disprove that, why are you on PPCG instead of making a lot of money?), the answer is valid. \$\endgroup\$
    – user45941
    Commented Feb 11, 2016 at 20:05
  • 12
    \$\begingroup\$ @Mego, the burden of proof should be on the person claiming to have a valid answer. If their answer is only valid assuming some conjecture (even if it's the Riemann hypothesis or P != NP) then they should first ask in a comment on the question whether that conjecture may be assumed. \$\endgroup\$
    – Peter Taylor
    Commented Feb 11, 2016 at 20:46
  • \$\begingroup\$ @PeterTaylor I also like that way of looking at it. I would be in support of either method for dealing with answers that are valid assuming a certain outcome of an open question. \$\endgroup\$
    – user45941
    Commented Feb 11, 2016 at 20:49
4
\$\begingroup\$

Yes

My suggestion is that we assume a program is correct until someone finds an explicit input/output pair for which it fails.

I believe this is the most clear-cut, objective way to determine whether or not an answer is correct.

(Edit: this answer is regarding "allowed" as "not deleted" instead of "not downvoted")

\$\endgroup\$
2
  • \$\begingroup\$ So... To answer the question "Are incorrect, but impossibly to show incorrect answers allowed?", you'd say "no?" \$\endgroup\$
    – Addison Crump
    Commented Feb 11, 2016 at 17:55
  • \$\begingroup\$ @VoteToClose Maybe I phrased my edit wrong. I mean I'm interpreting "are they allowed" as "should they not be deleted" rather than "should they not be downvoted." My answer to the titular question is "yes." \$\endgroup\$
    – PhiNotPi
    Commented Feb 11, 2016 at 18:00

You must log in to answer this question.

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