fundamental of Turing machine. For a Turing machine, given a particular input, there is no guarantee that the Turing machine will ever halt. A non-deterministic Turing machine is that the state/input transition is a multi-valued function, which means for a given input and a state, the next state is not one state but a set of states, the Turing machine picks one of the state out from the set, and that picking is non deterministic. Even non-deterministic Turing machine may generate the same output for a given input, otherwise the Turing machine (algorithm) is not very useful in general cases.