10
\$\begingroup\$

Many challenges, mainly , are impossible in some languages. Find an Illegal String is a good example—many languages without syntax errors, such as brainfuck (deleted answer), can simply be put in an infinite loop before the illegal string is reached within the code. The challenge even brings Jelly to its knees (deleted answer by Dennis himself), as you can simply put ¶1 at the end of any program (after closing any open strings) and the parser won't even look at the line with the syntax error.[citation needed]

Now, it's not always obvious whether a challenge like this is possible in a given language. Even if someone has a proof that there are no solutions, it's not currently clear whether or not it's legal to post this as an answer in itself. (This is the closest question I could find, but it asks specifically about challenges that aren't possible in general.)

So, what should be done when a language provably cannot answer a challenge? What about when it's almost certain, but not proven impossible?

\$\endgroup\$

3 Answers 3

Reset to default
17
\$\begingroup\$

Don't use that language for that challenge

I'm sure many users avoid challenges that are not suited to their language(s) of choice. I know I do.

If the challenge is actually impossible for a language, that is an extreme version of "not suited".

\$\endgroup\$
4
  • \$\begingroup\$ To clarify, are you saying that proofs of impossibility in a given language should not be answers, and if posted be deleted as "not an answer"? \$\endgroup\$
    – lirtosiast
    Commented Nov 30, 2018 at 6:41
  • \$\begingroup\$ @lirtosiast this answer is what I thought was the best answer to represent the "No" side of the question. If it had turned out to be the overwhelming consensus, then I think proofs would be deleted as non-answers. Given the votes, though, I don't think there will be a consensus. I'm not a computer scientist but I think the idea of "proving" possibility or impossibility or the even correctness of an answer is, when you really get down to it, very difficult in general. My personal view is that people just shouldn't answer when it's impossible. \$\endgroup\$
    – ngm
    Commented Nov 30, 2018 at 18:31
  • 1
    \$\begingroup\$ @lirtosiast that being said, there might be occasions where a proof could be interesting, especially a proof for most or all languages. \$\endgroup\$
    – ngm
    Commented Nov 30, 2018 at 18:32
  • 1
    \$\begingroup\$ I agree there's a problem with proving impossibility. Proofs are even more susceptible to subtle bugs than code, since you can run code to check it works \$\endgroup\$
    – trichoplax is on Codidact now
    Commented Dec 15, 2018 at 20:47
13
\$\begingroup\$

Follow mbomb007's answer as to when to post proofs as answers. This also follows precedent from the linked question.

In the rare case that it is interesting to know the class of impossible languages, or many languages have trivial proofs of impossibility, create a canonical answer of the form below containing all such languages.

List of languages that cannot solve this challenge

  • Any non-Turing complete language, by @user's proof of universality.

  • [Language], by @otheruser's exhaustive search of all 63340000 possible encodings of the payload.

  • Any language with multiline comments, because [reason].

  • Any language with a one-character builtin for [operation], because [other reason]. This includes [languages].

\$\endgroup\$
3
  • 2
    \$\begingroup\$ I think this is the best answer, as it's often interesting to know, for example that multiline comments or builtins for a certain operation (or some other criteria) disqualify languages from being able to solve a challenge and, more importantly, why. Examples of non-interesting reasons for languages being unable to solve a challenge are: Incapable of supporting Unicode characters, Incapable of handling floating point values, Incapable of required method of input or output. \$\endgroup\$
    – Mayube
    Commented Nov 21, 2018 at 21:33
  • \$\begingroup\$ Sometimes a language's explanation gets too long. Should anything be done in that case? \$\endgroup\$
    – user202729
    Commented Nov 22, 2018 at 6:29
  • \$\begingroup\$ @user202729 If it's kinda long and trivial it can be glossed over. If very long it's probably nontrivial and/or interesting and should be posted as its own answer. \$\endgroup\$
    – lirtosiast
    Commented Dec 11, 2018 at 14:19
8
\$\begingroup\$

Reasons to Post an Answer

  • The proof of impossibility may be interesting to see
  • It demonstrates for all to see that the challenge cannot be solved in that language
  • It makes it less likely that invalid solutions will be posted

Reasons NOT to Post an Answer

  • If the proof is trivial
  • Non-solutions may distract from actual solutions to the given challenge

When a solution in a given language is almost certainly impossible, it is hard to say whether an answer would be worth posting or not. If a non-trivial amount of work was done to eliminate a significant set of potential solutions and narrow the remaining options for the language, then perhaps an answer would be worth it, provided it's made clear that it is not a definite answer. Otherwise, probably not.

\$\endgroup\$

You must log in to answer this question.

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