[Solved]: If the universe were predetermined, would non-deterministic automata still make sense?

Problem Detail: 

If the universe were governed by predeterminism (i.e. some deity decided in advance how everything, ever, would play out), would the notion of non-deterministic automata make sense? Or would it not, but we wouldn't know it?

Asked By : JesseTG

Answered By : phs

It makes perfect sense. Non-deterministic automata and non-deterministic algorithms in general are useful in many situations. The best known situation is when one designs algorithms (or strategies or recipes or ..) and analyzes them.

For example, an algorithm for computing the maximum element of a set of numbers will have a loop of the form "as long as the set is not empty, take out an element and compare it with the current max value". This algorithm is non-deterministic because I did not explain how one chooses what element to pick. I did not explain it because it is not important for the correctness of the method (and because deciding in advance how to pick an element would blur the issues and limit the scope of my algorithm).

Note that, in all likelihood, all actual implementations of the algorithm will run deterministic code. But it is useful for me to think in term of the more abstract, more generic, non-deterministic algorithms. You may give it a different name but non-determinism is an essential concept.

Here is another way to see that non-determinism in mathematical models is not related to non-determinism in the actual world : your question is similar to me asking if the universe is governed by predeterminism, does the $P\not=NP$ question make sense?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49487