Determinism and non-determinism

These are lecture notes from my Computer Science course. For learning about formal specifications of systems, I recommend Software Abstractions: Logic, Language, and Analysis.

This is fairly obvious but:

Determinism – given a pre-state and a collection of inputs there is at most one post-state and collection of outputs allowed by the system. It rarely makes a good description of what the system is to do. This is a function basically. Non-determinism is more common.

Non-determinism – ‘it’s allowable’ that for some pre-states and collections of inputs, there may be more than one post-state and/or collection of outputs allowed. This is a relation basically. Of course, non-determinism is hard to test because you can run a test multiple times and each time it comes out different.


Non-determinism allows ‘Don’t care’ conditions, such as:

  • “Return either square root”
  • “Establish a connection with any printer in the room that can print colour.”
  • “Serve any pending requests”

Sometimes, a non-deterministic system is identical (code-wise) to a deterministic system, it’s just different by convention (e.g. instead of specifying an input, ask the system to provide that input as an output).

This entry was posted in fss, lecture. Bookmark the permalink.