One step, several possible results
A deterministic program has exactly one next step at every moment. Given the same input, it does the same thing every time. Many unusual systems drop that guarantee. At some point, the program faces a choice, and more than one outcome is allowed.
The word “choice” hides two different ideas, and keeping them apart makes everything else clearer.
Probabilistic: chance picks the path
In a probabilistic program, a step has several outcomes and a random mechanism picks one, often with equal likelihood. The classic esoteric example is the question-mark instruction in the Befunge language, which sends the pointer in a random one of four directions. A pointer reaching it behaves like a die being rolled, and different runs of the same program can take different routes.
You can build useful things from this. A program that must “flip a coin” can send the pointer down one of two paths, and an average over many runs reveals the probabilities. But there is a danger: a program that works in one run may fail in another, so testing needs many runs, and some bugs appear only occasionally. Programs that rely on randomness are also harder to debug because a failing run may never be reproduced. Using a fixed seed for the random number generator is the usual remedy when possible.
Randomness gets its own use as a tool in everyday algorithms, such as shuffling or sampling. In an esoteric language it is more often a way to make a toy world less predictable. Picking a random direction at a junction is a handy way to experiment with this.
Nondeterministic: the machine “guesses”
In the theoretical sense, nondeterminism is not about chance at all. A nondeterministic machine is allowed to follow any of several possible steps, and the question is whether some path leads to success. You can imagine it as exploring all branches at once or as always guessing right.
This idea appears in the study of finite automata, where nondeterministic ones are a convenient way to describe patterns, and in nondeterministic Turing machines, which help define important complexity classes. A famous open question in computer science, whether certain problems that are easy to check are also easy to solve, is phrased in these terms. The question is widely considered unresolved, so treat any confident claim about it with suspicion.
In real software, nondeterminism is simulated. Logic programming languages try a choice, and if the rest of the computation fails, they backtrack and try another. A regular expression engine does something similar when it explores alternatives. The programmer writes down what is allowed, and the system searches.
A small example with two paths
Take a rewriting program with two rules: a becomes x, and b becomes y. The starting text is ab, and either rule may be applied first.
- If the first rule goes first: ab becomes xb, then xy.
- If the second rule goes first: ab becomes ay, then xy.
Both paths end at xy. When every choice order leads to the same final answer, the system is called confluent, and the nondeterminism is harmless. It is a sign that the rules do not interfere.
Now change the rules to a becomes x and a becomes y, starting from the single letter a. One run ends in x, another in y. The program has more than one possible result, and the question “what does it output?” no longer has a single answer. A good specification will say whether this is a bug, a feature or a reason to ask for all possible results.
Reasoning about such programs
Some habits help.
- Think in sets. Ask for the set of possible results, not one result. A property holds if it is true on every path, or on at least one, and you must say which.
- Look for confluence. If order does not matter, you may reason as if there were only one run.
- Measure, don’t guess. For probabilistic code, estimate frequencies by running many times, and describe the result as approximate, never exact.
- Watch for nontermination. Some paths may run forever even when others finish, a reminder of the halting problem.
Why this matters for esoteric design
Adding chance or choice changes the character of a language. Programs become more like simulations or games, and the notion of a correct output becomes statistical or existential. Some designers use that deliberately, for toys, art and music. Others use nondeterminism as a theoretical tool, since it makes certain proofs shorter.
It is also worth noticing what does not change. Adding randomness to a language does not make it able to compute anything new in the sense of what is computable. It can change how efficient a solution is, or how easy it is to write, but not the boundary of the possible.