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.

25 Likes

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

3 Likes

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.

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

Since we’re talking theory, random isn’t truly random. A friend of mine is pursuing a PhD in Chemistry and Physics (using computers as a thesis…long story lol). He’s why I’m studying front-end, and recently we had a discussion about how randomization isn’t truly random even using time as a construct in the random calculation like Random.Range() in .NET/C# in Unity, for the purposes of a game it is seemingly random, but if you want true randomness, you need a Geiger counter, pickup some background radiation and use that for randomness lol.

P.S. I should probably mention my experience is in game development and Android/iOS mobile development, I’m here to learn front-end and polish up gaps in my knowledge to be more competitive in the job market.

1 Like