2
$\begingroup$

I'm studying the didactic programming language Oz, following the book "Concepts, Techniques, and Models of Computer Programming".

In the book, the nondeterminism is introduced through the concept of choice, as it's explained here. However, in the Oz language if the programmer calls a choice between alternatives A, B, C it happens that the alternative A is always travelled first, and consequently (in case of backtracking) first B and then C. So the choice happens to be deterministically, since I know a priori how the choices' tree will be constructed. So what's the link between choice and nondeterminism?

I also have another question. In the book, the authors state that if I want to introduce the choice concept in my computation model I am obliged to use a stateful (non-declarative) computation model. Why?

$\endgroup$
2
$\begingroup$

Nondeterminism is an inherently unphysical concept. If you think about the various definitions of nondeterministic computation, they always say something like one of the following:

  • the computation is structured as a tree and, if any of the paths through the tree succeeds, the computation succeeds, regardless of how many failures there are on other paths;

  • the computer "magically" considers all the options in parallel, even though there might be exponentially many of them;

  • the computer only considers one option but it "magically" knows which one will lead to success, if any of them will, and chooses that one.

In principle, the "choice" operator achieves nondeterminism – at least, it would, if we could implement it using one of the above schemes. Unfortunately, in the real world, we don't know how to do that, so we have to pick an option, see if it works out, and backtrack if it doesn't. Maybe we could do something a bit smarter than just trying the options in order but, at the end of the day, we don't know any efficient way of implementing nondeterminism on a real, deterministic, computer (which is why we don't know that $\mathrm{P}=\mathrm{NP}$).

$\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.