7
\$\begingroup\$

We seem to have implied restrictions that code submissions should be deterministic, but this doesn't seem to be well-defined or explicitly restricted as a loophole.

The closest loophole is this one. See this comment, which provides an example where the forbidden loophole would've been used to prevent non-deterministic submissions.

Some users are unfamiliar with what it means for a program to be deterministic, so we should provide a clear definition of what our requirements are. Then we can specify whether such a restriction should be the default, which I think it should be.

\$\endgroup\$
  • \$\begingroup\$ Because there needs to be a default, and deterministic makes the most sense. \$\endgroup\$ – mbomb007 May 19 '17 at 17:11
  • \$\begingroup\$ That's what we're determining. :) This was posted because of your answer, which is not deterministic, but you didn't know what that really means. So it's safe to assume that other users don't either. Clarification will be helpful. \$\endgroup\$ – mbomb007 May 19 '17 at 17:12
  • 1
    \$\begingroup\$ I think it'd be more gracious to some of the inherently random esolangs to have a "minimal chance of incorrectness", say, 0.05% or smth \$\endgroup\$ – Conor O'Brien May 22 '17 at 3:39
  • \$\begingroup\$ Should that be an answer? \$\endgroup\$ – CalculatorFeline May 27 '17 at 19:47
18
\$\begingroup\$

An answer must always comply with the specification, but need not always comply in the same way

For example, suppose the challenge is "return the longest substring of the input made entirely of vowels; it doesn't matter which substring you return in the situation where there's a tie". A submission that, on the input aeziozu, sometimes returns ae and sometimes returns io, would be acceptable despite not being deterministic. A submission that usually returns ae and sometimes returns u would not be acceptable, as it doesn't always comply with the specification.

Or to put it another way, we check whether the worst-case output is still valid. If it is, the answer is valid, even if it isn't deterministic.

If an answer is nondeterministic, it can't necessarily be verified by running the program, and as such it would need some sort of proof or argument that that's valid. (This isn't really an issue, as determinism of the program also can't be verified by running it, and many challenges have infinitely many valid inputs anyway, so some sort of proof that the program is valid is typically going to be required regardless of what we decide here.)

\$\endgroup\$
  • \$\begingroup\$ If more than one solution is acceptable like that, the OP states in the challenge description that any of the answers is acceptable. That isn't really what this meta question is meant to address, though, because there's no disagreement there. It's meant to address this answer \$\endgroup\$ – mbomb007 May 19 '17 at 19:34
  • 1
    \$\begingroup\$ Right, I'm just making sure that the sort of obviously valid answer my post is about won't be disqualified by a stock rule against deterministic programs; the answer in question is clearly nondeterministic, but equally clearly valid. You're talking about the situation where a post has a nondeterministic score, which is somewhat different; that could be covered in other answers (e.g. if you think questions should have a deterministic score to be valid, you can post that). \$\endgroup\$ – user62131 May 19 '17 at 20:20
  • \$\begingroup\$ I agree with this as a default, provided rhe challenge author can still override this rule for a specific challenge by specifying that answers must be deterministic. \$\endgroup\$ – trichoplax Dec 15 '18 at 20:35
7
\$\begingroup\$

Nondeterministic solutions are acceptable, providing they are correct with probability 1, under the assumption that their PRNG actually works. No finite time bound is needed.

Solutions to problems never need to be deterministic, but authors should be able to provide some argument to show that their solution gives their claimed answer almost-surely, assuming that any pseudo-random effects are seeded correctly.

Suppose a challenge involved sorting a list of ints. Consider the following two ruby-ish snippets:

def valid_solution(x)
  loop do
    x.shuffle!
    return x if x.sorted?
  end
end

def invalid_solution(x)
  loop{nil}
end

The first is a bogosort, the second loops forever. Clearly the second does not fulfil the terms of the challenge. We could argue that there's a vanishingly small possibility that the two programs are equivalent, since a broken PRNG would make the first loop forever, but the probability of the first snippet eventually returning a sorted list is precisely 1, therefore the first snippet is an acceptable solution.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think this paves the way for lengthy discussions regarding correctness: things that happen with probability 0 are not impossible (for example, if the challenge is to output a real number between 0 and 1 exclusive, a random real number between 0 and 1 inclusive will have a zero probability of violating the spec). Things get especially muddled when it's unclear how much we can idealize the implementation; for example, if we can assume a true source of randomness, can we also assume that we're working with real numbers instead of finite-precision floating-point numbers? \$\endgroup\$ – Sanchises May 31 '17 at 10:06
  • 1
    \$\begingroup\$ (also, more subjectively, I really don't like bogosort-like approaches) \$\endgroup\$ – Sanchises May 31 '17 at 10:07
  • \$\begingroup\$ @Sanchises A challenge like that would likely override the default. \$\endgroup\$ – PyRulez May 31 '17 at 21:54
  • 1
    \$\begingroup\$ That bogosort doesn't check if the input array is sorted. This makes me a sad puppy. \$\endgroup\$ – Draco18s Jun 1 '17 at 3:28
-3
\$\begingroup\$

Definition:

From Google:

deterministic

relating to the philosophical doctrine that all events, including human action, are ultimately determined by causes regarded as external to the will.

In relation to answers on this site, this means that the user cannot determine with 100% accuracy what the output of their program will be, or the output will not be consistent and identical across multiple executions.

As simple example of a non-deterministic program is a program that prints the current system time in nanoseconds. The user has no control over the output of the program with regard to the source code, and the output of the program depends on something other than the user, the input, and the source code. The output will not be the same across multiple executions, and the user cannot determine what the output will be without running the program.

This definitions fits our criteria for our challenges because:

  1. Challenges require a specific solution or output, and if the program ever doesn't produce the correct solution, it's invalid.
  2. If you can't determine the output, you can't maintain that your answer is correct, unless the output is not required to be consistent.

Default:

The restriction that an answer should be deterministic should be a default restriction. The number of challenges that require a constant or consistent solution is far greater than the ones that do not.

If the OP posts a challenge, they can override the default by stating the non-deterministic solutions are allowed. If the challenge obviously does not require deterministic output due to its nature, then stating this is not necessary. An example of this would be a challenge where the goal is to output the current time, which obviously will not be consistent. challenges often involve randomness, so it should be allowed by default for those.

\$\endgroup\$
  • 2
    \$\begingroup\$ Perhaps non-deterministic should be allowed for KOTH challenges by default? \$\endgroup\$ – John Dvorak May 19 '17 at 17:01
  • \$\begingroup\$ Is there anything on here about scoring? That should also be as deterministic as the post, no? \$\endgroup\$ – tuskiomi May 19 '17 at 17:13
  • 1
    \$\begingroup\$ @tuskiomi There won't need to be. If a challenge requires a deterministic score, it either requires a deterministic solution, or the OP will have a separate method of scoring. For KOTH, the OP usually runs the programs a fixed number of times and averages the results. \$\endgroup\$ – mbomb007 May 19 '17 at 17:14
-4
\$\begingroup\$

Answers should surely give a correct result within finite time.

In other words, almost surely is not enough. PRNG's are assumed to be truly random.

  • While a program could give an answer with probability of 1 ('almost surely'), the expected runtime is then arbitrarily long (possibly even infinite).
  • Interesting challenges could be trivialized; for example, when verifying the correct solution out of randomly generated candidates is trivial compared to generating the correct result.

This view allows for non-determinism (like @ais523's answer), but excludes hope-for-the-best approaches (as in @ymbirtt's answer). For example, bogosort is not OK, but listing all permutations of the list in random order and selecting the first one that is sorted is OK.

\$\endgroup\$
  • \$\begingroup\$ The biggest problem I see is 'reasonable' depends on the problem. Who is the one that decides which problems can have infinitely long solutions, and which problems can't? If it's up to the OP, then it should be in the post already (and no default required). If its up to the voters, then how are we supposed to decide? \$\endgroup\$ – Nathan Merrill May 30 '17 at 15:08
  • \$\begingroup\$ @NathanMerrill that's a whole other discussion. But I do not think that a possibly infinite runtime is considered "reasonable" for problems that can be solved deterministically, so I feel that's​ safe to exclude \$\endgroup\$ – Sanchises May 30 '17 at 17:36
  • \$\begingroup\$ As far as I understand, you're trying to set a time limit on every submission by default. This is new, and you need to provide how that time limit is derived, or post a new question looking for suggestions. Either way, I can't support this answer until we have more guidelines on how reasonable is different from problem to problem. \$\endgroup\$ – Nathan Merrill May 30 '17 at 17:52
  • 2
    \$\begingroup\$ Though I disagree with this answer, I don't think that this actually sets a hard time limit on solutions. The difference between my proposal and this one is that this approach requires all solutions to terminate after some finite amount of time, but there's no actual limit on what that finite time is. My proposal does not require solutions to guarantee termination within any time limit, so long as we know that it'll happen "eventually" \$\endgroup\$ – ymbirtt May 31 '17 at 8:43
  • 1
    \$\begingroup\$ @ymbirtt Exactly! (Although I changed your edit a little bit, because "some arbitrary finite time bound" could be interpreted as "I'm advocating we should set the time limit to 2*pi*sqrt(2) minutes" instead of the mathematical concept of "finite but arbitrarily large".) \$\endgroup\$ – Sanchises May 31 '17 at 9:40

You must log in to answer this question.

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