display | more...
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, qstart, qaccept, qreject), where:

1. Q is the set of states
2. E is the input alphabet, not containing the symbols '_' (space) and ">" (beginning of the tape).
3. L is the tape alphabet, so L = E U {_} U {>}.
4. 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}.
5. qstart, qaccept and qreject are memebers of Q
The NDTM accepts the input if one of the pathways it can follow will lead it to qaccept. 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.