NONDETERMINISTIC TURING MACHINE

A regular (Deterministic) TM uses the state and character at the tape head to decide its next step:  what to do with the tape, and what to move to next.  In a DTM, this is a function:  the state and character give you a unique tape command and next state.

But if this a relation rather than a function and there are more than one possible next step for a state and character, then this is a NTM.  The usefulness of a NTM may not be as pronounced as people imagine it to be.  In particular, if there is more than one path from the start state to the halt state, there's no guarantee that each path will end up with the same output on the tape.  And so, discussion of NTM algorithms tend more to focus on whether the machine halts or not or under the rule that the output would hold very basic information such as YES or NO.

Much like finite automata, adding nondeterminism to a TM does not give the TM any more power in solvability.  Any problem that can be solved by a NTM can also be solved by a DTM.

(PDA's do not share this property.  NPDA's can recognize all context-free grammars; DPDA's cannot.)

We probe that NTM's are equivalent in power to DTM's by showing how a DTM can emulate an NTM.

You have the NTM on the tape, and then you also have a queue of configurations.  The initial item in the queue is the start state along with the head at the beginning of the input tape.  Whenever you process a configuration, for each possible transition you enqueue the configuration (tape, state) and after doing this you dequeue the configuration you just processsed.  By using a queue for this any configuration you add is guaranteed to make it to the top of the queue sooner or later.  If you transition to the halt state, there's no need to add a configuration to the queue in the situation.

Understanding that NTM's and DTM's can solve the same class of problems...or recognize the same class of languages.  The big big big issue in theoretical computer science concerns the speed at which these problems can be solved or these languages recognized.

Our emulation of an NTM with a DTM described above is ridiculously slow.  But might there be a better faster way that I'm not thinking of?  We don't know, there might well be.

Decision problems:  is a problem for which the output can be reduced to single bit:  Yes/No, true/false, 1/0, whatever you want to call it.

We measure the "time" of an algorithm on a TM as being the number of states visited by the TM.

If a DTM always halts, then it's to define the runtime of an algorithm run on it (ending with either YES or NO).  If the runtime is a polynomial function of the length, we say that this algorithm is in P.  If there exists an algorithm in P that solves the problem, we say the problem is in P.

With a non-deterministic machine, if there is a sequence of configurations that leads to a halt with YES, we say that the NTM gives an answer of YES.  If there's one way to do it with YES, 1206 ways to get a NO, and 10313 ways to get an infinite loop, it's still YES.

If the shortest possible runtime for a YES (or the shortest possible runtime for all NO's if there is no YES) is polymomial with respect to the input length, then the algorithm is in NP, and if an NP algorithm for a problem, the problem is in NP.

NP does not stand for "non polynomial".  It stands for "nondeterministic polynomial".

Does P = NP?  Most important unsolved problem in theoretical computer science.

One way to make headway on the P = NP problem is to define and classify NP-complete problems.  If ANY NP-complete problem can be solved in polynomial on a TM (or a RAM model) than P=NP.  There have hundreds of NP-complete problems, to date, not one has been solved by a polynomial-time algorithm.