It's nondeterministic in the same sense as the "nondeterministic polynomial" of P = NP. Basically, a normal turing machine would also be a nondeterminisic one if P = NP.