What is a deterministic and non-deterministic algorithm?

Question:

What is a deterministic and non-deterministic algorithm?

  • What are the characteristics of both?
  • Is it possible to implement both in any language?

NOTE: if possible, exemplify with some implementation

Answer:

Deterministic algorithm is one that always produces the same result given certain data inputs.

Most algorithms are deterministic. Fortunately 🙂

That's why algorithms don't always reproduce the world's problems well, the real problems tend to be indeterministic, any attempt to reproduce the real world borders on insanity. It is possible to make a simplified representation of the real problem. Hence the definition of OOP as being a tool to reproduce the real world is fundamentally wrong.

A non-deterministic algorithm is one that can produce different results even with the same input data.

This is common because any algorithm that relies on external data, such as time, concurrency, or hardware failure for example, will possibly or certainly produce a different result.

The most obvious examples are those that take the computer's time at runtime, those that use random number generators, those that have inherently probabilistic characteristics.

But there are less obvious cases, such as those that depend on data that cannot be classified well. As the name says, when it is not possible to determine what to do, the result may be different. Should a sorting algorithm that runs on a roll of data that has exact duplicates sort them how? Is there a way to determine this? There are algorithms that cannot.

An algorithm that reads files, networks or other forms (at low level) are indeterministic, it is not known what will come of this reading, since what will be done with the data read (higher level) will possibly be deterministic, as they become an input of new algorithms. These algorithms don't know what they're going to find there, it's external data, they may have been modified by other sources. So looking at a higher level the reading algorithm will be deterministic.

Garbage collector tracing is one of the most famous indeterminisms in computing. As much as the rules are well established, it is not known when it will be triggered, it is not known when the algorithm will produce a result that triggers it. It depends on many factors, some of which are not under the application's control.

Note that indeterminism is not the same as random. This is not to say that anything will necessarily happen, just that it cannot be determined in advance.

Yes, it is possible to implement them in any language. A few avoid, or at least try to isolate, the use of indeterministics. But there's no getting away from them in most problems.

Scroll to Top