4
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ This is a philosophical question that doesn't have much to do with computer science. $\endgroup$ – Yuval Filmus Nov 14 '15 at 17:22
  • 1
    $\begingroup$ Where would you suggest I ask it if not here, then? $\endgroup$ – JesseTG Nov 14 '15 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 '15 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 Richerby Nov 14 '15 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 '15 at 9:50
8
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.