What is determinism in computer science?

Question

I was asked if my computer program (in Java) was deterministic. I'm wondering how could it be not? There is no such thing as a non-deterministic Java program right? Even if I use a random number generator to make branching unpredictable, it is still really non-deterministic (but harder to prove so).

Answer 1

I'd like to expand on @jmite's mention of non-determinism due to threading. "Is your program deterministic?" is a question that might well be asked in a parallel programming class, and the answer with many multi-threaded programs is often "no."

In most multi-threaded programs the exact interleaving of instructions from different threads is indeterminate. We can't determine the order in which instructions are interleaved just by using the program and its input. To actually figure out what order the instructions would interleave would require us to know the exact state of the caches and branch predictors and tlbs on every core, when all the external interrupts occur to the picosecond (mouse movements, external network traffic, timer interrupts) the exact position of the disk drive heads with respect to the spinning platter, the temperatures of every transistor (at least the transistors that drive the asynchronous busses) and the small fluctuations in voltage coming from the wall socket or battery.

Given that every time you run your multithreaded program the exact instruction interleaving is different, we are really interested in:

can the multi-threaded program's output be exactly determined knowing only the input and the code?

For example, the following multithreaded program is non-deterministic:

thread A                    thread B
acquire mutex m             acquire mutex m
x = 0                       x = 1
release mutex m             release mutex m
print x

This program will sometimes print "0" and sometimes print "1".

The following multithreaded program is determinisitic

thread A
x = 0
fork thread B               thread B
acquire mutex m             acquire mutex m
x = x + 1                   x = x + 2
release mutex m             release mutex m
join with thread B          finished
print x

This program would usually be considered deterministic. It always prints "3", although we don't know if the sequence of values of x was 0, 1, 3 or 0, 2, 3.

Things get even more interesting when we are talking about data structures like binary trees. In a binary tree the exact shape of the tree usually depends on the exact order in which nodes were added. But often you are using the binary tree to represent some abstract data type (like an ordered sequence) in which many different tree shapes represent the same abstract value.

For example, the binary trees

  0          1          2
   \        / \        /
    1      0   2      1
     \               /
      2             0

all represent the same ordered sequence "0, 1, 2". So most people would still call this ordered-sequence type deterministic although if you have to debug the program (and thus deal with different runs having different actual representations of the data structure) you might also call it annoying.

Answer 2

You can create true randomness in a computer by measuring the decay of a radioactive source and using that as the basis for a random number generator. So yes, there is such a thing as a non-deterministic computational automaton.

Even if there weren't, you can still simulate the appearance of actual randomness in a computer. That's what makes things like Monte Carlo simulations possible. The quality of such randomness can be measured with statistical techniques.

A deterministic program would behave the same way each time it is executed, or would behave in a manner consistent with its logical design. That is, given the same input over multiple executions, the same output will always occur. This is also true of programs that employ pseudo-random number generators; given the same seed and the same user input, the program will behave the same way each time.

Note that there are ways to randomize a pseudo-random number generator so that you cannot predict its output. One common way is to take the six or so least significant digits of a high-resolution clock when the user presses a key, and use that as the seed to the pseudo-random number generator.

Answer 3

So, here's the problem. There are two different and competing meanings for deterministic in Computer Science.

• Deterministic = uniquely defined. This is the definition used mostly in automata theory, complexity theory, theory of computation. A deterministic computer/Turing Machine/automaton is one for which, given the current input and state, there is only one action that can be taken.

This is defined in contrast to non-deterministic machines, where, in a given state, the machine has multiple possible actions/transitions that can be taken. A machine accepts some input if there is exists some accepting computation. Alternately, you can view non-deterministic machines as having some magic decision procedure which tells them which action to choose, or as a machine that has infinite parallelism and tries multiple options simultaneously.

Real computers are deterministic in this sense, but can simulate non-determinism, usually through some sort of backtracking search.

Note that there is NOT any randomness occurring in this situation. Either we assume some magic choose which path to take, or we assume we're trying them all in parallel.

• Determinism = Non-random. This is the case that Robert Harvey describes. This definition of determinism is usually what's used in math, statistics, or physics (i.e. quantum physics is non-deterministic).

In computing science, something which is non-deterministic in this sense is usually referred to as stochastic, or randomized. However, the term deterministic/non-deterministic is often used in systems programming to describe threaded programs.

A program that uses random numbers is inherently non-deterministic in this sense, since its output might change for a given input. However, if you view the random seed as input, or view the RNG as input as an infinite stream of numbers, then you could argue that your program is deterministic, since its output is fixed given its input.

Things become complicated when you add threading. Poorly-written multi-threaded programs can be non-deterministic, if their output changes depending on how threads are scheduled. Mutexes, semaphores, etc. all have the goal of making multithreaded programs deterministic, i.e. they give the same result, regardless of how threads are scheduled.

• Conclusion:

Which definition is being used where depends on the context. If you're talking $P =? NP$, then $NP$ is the class of problems solved by a non-deterministic Turing Machine, in the first sense of non-deterministic (infinite parallelism). Likewise, non-deterministic finite automata (NFAs) are non-deterministic in the first sense.

Answer 4

A philosophical (but perhaps less useful answer than those given) is that non-determinism occurs only when your accuracy of measurement falls below the threshold required to be able to be sure of the outcome.

The 'non deterministic' program listed above i.e.

thread A                    thread B
acquire mutex m             acquire mutex m
x = 0                       x = 1
release mutex m             release mutex m
print x

is only non-deterministic in that there are things happening at a low enough level in the computer stack that you can't measure them (or, in this example, you could measure them if you had the right tools but you would normally not expect to do so as part of your code development). There's nothing actually 'random' here, the events leading to one thread/process gaining the mutex over another aren't random but you just don't measure the things affecting which one wins out.