Editing Nondeterministic Turing machine (section)

==Description==
[[Image:Difference_between_deterministic_and_Nondeterministic.svg|thumb|350px|right| Comparison of deterministic and nondeterministic computation]]
In contrast to a deterministic Turing machine, in a '''nondeterministic Turing machine''' ('''NTM''') the set of rules may prescribe more than one action to be performed for any given situation. For example, an X on the tape in state 3 might allow the NTM to:
* Write a Y, move right, and switch to state 5
'''or'''
* Write an X, move left, and stay in state 3.

Because there can be multiple actions that can follow from a given situation, there can be multiple possible sequences of steps that the NTM can take starting from a given input.  If at least one of these possible sequences leads to an "accept" state, the NTM is said to accept the input. While a DTM has a single "computation path" that it follows, an NTM has a "computation [[Tree_(abstract_data_type)|tree]]".