# Why “Choice Points” introduce non-determinism in a program?

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?

## 1 Answer

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}$$).