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.

See also Deterministic Turing Machine.

Another way to view nondeterministic computation is to consider a NDTM which manages to accept input as incredibly lucky: it "just happened" to make the right choice at each step along the way. If some guardian angel sat beside the machine and guided it, this would be easy. The nice bit is that a NDTM can distinguish between its guardian angel and a misleading devil. For suppose some misleading devil sits beside our NDTM and misguides it, giving it a wrong path. Then the machine might be unable to accept, but at least it will never accept an input that it shouldn't.

While deterministic Turing machines are equivalent with regard to computable functions to non deterministic Turing machines, the proof of this fact relies on a simulation that is incredibly slow. In fact, the simulation merely checks every possible computational path the NDTM could take, and accepts input if one of these paths accepts. Since the number of paths is exponential in the number of steps the NDTM makes (along the accepting computation), the simulation is exponentially slower than the nondeterministic version.

Of course, it could be that the problem is with our simulation, and that structuring our solution differently would lead to a much faster simulation, one not subject to the exponential slowdown. This is what lies at the heart of solving questions such as P!=NP: how can we prove that the guardian angel really helps?

Log in or register to write something here or to contact authors.