Non Deterministic Turing Machines (

NDTMs) are

Turing Machine that are not

deterministic (surprise, surprise), i.e. that for every

state and

symbol, there are a GROUP of actions the machine can CHOOSE from. They actions can differ by the state the machine moves into, the new symbol the machine writes, the direction of head movement, or any combination. Its

transition function, therefore is not deterministic.

Like a DTM, an NDTM is defined by a 7-tuple:
(Q, E, L, d, q_{start}, q_{accept}, q_{reject}), where:

- Q is the set of states
- E is the input alphabet, not containing the symbols '_' (space) and ">" (beginning of the tape).
- L is the tape alphabet, so L = E U {_} U {>}.
- d is the transition function. d: Q * L -> P(Q * L * {L,R}). P(Q * L * {L,R}) is called a power set. It represents the set of all possibilities of the sets Q, L and {L,R}.
- q
_{start}, q_{accept} and q_{reject} are memebers of Q

The NDTM accepts the input if one of the pathways it can follow will lead it to q

_{accept}. We assume it always chooses the correct path, so that if there IS an accepting state, the machine will get to it. (Notice that the only difference between a DTM and an NDTM lies in d, the transition function.)

NDTMs are no more 'powerful' than DTMs, despite the fact that they appear to be. This is proven by showing that every NDTM can be simulated by a DTM.

See also Deterministic Turing Machine.