How do we define "deterministic", and is it required by default?

Question

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.

Answer 1

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.)

Answer 2

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.

Answer 3

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. king-of-the-hill challenges often involve randomness, so it should be allowed by default for those.

Answer 4

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.