# 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?

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