Do algorithms always produce the same output given a certain input?

Question

In the context of this exercise, do algorithms always produce the same output given a certain input?

Answer

No, sometimes an algorithm might produce a different output when given the same input.

This relates to the area of deterministic and non-deterministic algorithms.

A deterministic algorithm will always produce the same output given a certain input. For example, an algorithm to return the largest number of a list will always return the same value given the same input list.

For instance,
greatest_value([1, 2, 3, 4])
will always give us 4 as the output value.

Non-deterministic algorithms can produce a different output given the same input, each time you run such an algorithm. This is usually due to some level of probability or randomness.

20 Likes

Please give examples of a non deterministic algorithm like you did for the deterministic one.

1 Like

The concept of “non deterministic algorithm” is most frequently encountered in computational complexity theory (big - O and all that), as an algorithm run on a non-deterministic Turing machine (computer), a purely theoretical counterpart to a deterministic Turing machine (the kind you and I are using right now.) Pursuing the theory leads into considerations of whether there are problems whose solutions cannot be determined in “reasonable” time, despite the fact that any candidate solution could easily be tested once found: P != NP and beyond. For more, contact Dr. Google.

In a more practical realm, more-or-less non-deterministic algorithms are used when there inputs we cannot predict. A common example is running a multicore process, where, due to physical constraints, you do not know which processor will finish first. You can argue that if you only had enough information, the process would be deterministic, and, indeed, that consideration is an important part of the deterministic and non-deterministic Turing machine dichotomy.

5 Likes

I think I get the concept of a non deterministic algorithm, but just to confirm my simple understanding. Are non deterministic algorithms also used in game programming?

3 Likes

Yes, they are used in game programming. But there is limit to the outcomes that shows, but all possible outcomes are also coded and the prgram only choose among those options at random.