5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If you really want to blow your mind, imagine the entire universe as a computer simulation, essentially a very complex (and large) finite state machine. Is the entire universe deterministic? $\endgroup$ – user16765 Feb 9 '15 at 4:15
  • $\begingroup$ Randomisation and non-determinism are different things but if an algorithm has either it's no longer deterministic. $\endgroup$ – Raphael Feb 9 '15 at 8:42
  • $\begingroup$ Sure, it can easily be non-deterministic if you run it twice and don't reliably get the same result for the same input. If you were asked this question in a conversation about testing it, then you need to make sure that any random number generators are consistently seeded and that your output won't vary based on timing happenstance. As long as the observable output and timing do not matter, it can be multi-threaded and deterministic (with respect to output) as well. $\endgroup$ – Rob Feb 10 '15 at 1:55
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Behave" is a litte weak here; you can build programs that are not deterministic but "behave" (in the black box sense) just like a deterministic one. The computation trace of deterministic programs is exactly the same every time. $\endgroup$ – Raphael Feb 9 '15 at 8:43
  • $\begingroup$ Nondeterminism isn't the same as randomness! Nondeterminism just means that some choices must be made that aren't determined by the input. $\endgroup$ – reinierpost Feb 9 '15 at 10:18
  • 1
    $\begingroup$ Robert and reinerpost both give different definitions of deterministic, both of which are used in different circumstances. $\endgroup$ – jmite Feb 9 '15 at 10:40
  • $\begingroup$ @reinierpost: I never said that. $\endgroup$ – Robert Harvey Feb 9 '15 at 16:27
  • 2
    $\begingroup$ @Raphael: This question originated on Programmers.SE, where very likely the level of linguistic rigor is a bit looser. $\endgroup$ – Robert Harvey Feb 9 '15 at 16:28
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Random is a not really the dual of deterministic. Random suggests some notion of probability. $\endgroup$ – Dave Clarke Feb 9 '15 at 11:44
  • 1
    $\begingroup$ And in other fields, deterministic means non random. That's the whole point of specifying two definitions. $\endgroup$ – jmite Feb 9 '15 at 11:47
  • $\begingroup$ I don't think the interpretation of your second definition is used by anyone. I've never seen it in computer science, anyway. $\endgroup$ – reinierpost Feb 10 '15 at 10:14
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.