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?
$\begingroup$
$\endgroup$
7
-
4$\begingroup$ This is a philosophical question that doesn't have much to do with computer science. $\endgroup$– Yuval FilmusNov 14, 2015 at 17:22
-
1$\begingroup$ Where would you suggest I ask it if not here, then? $\endgroup$– JesseTGNov 14, 2015 at 17:24
-
3$\begingroup$ Nobody expects to be able to build a non-deterministic machine. They are a theoretical construct, independent of how the real world works. $\endgroup$– Raphael ♦Nov 14, 2015 at 17:45
-
6$\begingroup$ I think this is a computer science question: it hinges on a misunderstanding of what nondeterminism means in computer science. $\endgroup$– David RicherbyNov 14, 2015 at 18:46
-
2$\begingroup$ True, @DavidRicherby. The problem is probably that non-determinism is often explain via ill-advised "intuitive" crutches such as "the automaton always guesses right" or "the automaton executes all computations in parallel". Vain attempts to match nondeterminism with the implicit desire for an operational semantics. $\endgroup$– Raphael ♦Nov 15, 2015 at 9:50
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
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?
$\begingroup$
$\endgroup$
Nondeterministic automata would make perfect sense in a predetermined universe, because, in the sense it is used in computer science, "nondeterministic" does not mean "not predetermined."
In particular, the acceptance criterion of nondeterministic machines is defined in terms of the existence of a path of a particular kind through the state transition graph. The definition of the state transition graph doesn't depend on whether or not the universe is predetermined and nor doest the existence of any particular path through it. So the definition of nondeterministic computation doesn't depend on whether or not the universe is predetermined.
phs mentiones the P-vs-NP question and that's a good example. Again, regardless of whether the universe really is predetermined, it makes perfectly good sense to ask, "Are there problems where it's easier to check an answer than to produce one?" That question doesn't mention nondeterminism explicity but it turns out that nondeterminism, in the sense that the term is used in computer science, is central to it.
answered Nov 14, 2015 at 18:48