A decision problem is a program with a one-bit output.  TRUE/FALSE.  YES/NO.  ON/OFF.  ONE/ZERO.

What is the shortest path through this maze?  <== NOT A DECISION PROBLEM

Is there a path through this maze of 10 steps or less?  <== DECISION PROBLEM

Does this grammar accept this string?  <== DECISION PROBLEM

There are some decision problems for a TM to require the Turing Machine to always halt and give an explicit YES or NO answer.  (For example, the recursive languages are this way.)

But there has been a lot of work on a broader class of problems in which YES is signified by the TM halting and NO is signified by the TM infinite looping.  (The recursively enumerable, or r.e. languages, are like this.)

How do you know that the TM has gone into an infinite loop as opposed to just taking a long time?  (You don't, which is why this sort of analysis is tricky).

So, HALT means YES and NOT HALT means NO.  That means some some problems are really easy.

Is such-and-such a number even?  Well, divide it by 2, if the remainder is zero, HALT.  If the remainder is not zero, go into a deliberate infinite loop:  while(1);

But other problems can be expressed in this way:

Does Program P halt on Input X?

Just have your TM emulate P running on input X.  If the emulation ends then HALT.  If the emulation never ends, then keep emulating forever.  The TM halts if and only if P does.

Is there a pair of twin primes larger than n?

Well, just try n+1,n+3; n+2,n+4; n+3,n+5...and so on.  If you find another pair of twin primes, HALT.  If you don't, just keep on trying.  If the answer is no, your TM will infinite loop.

ASIDE:

I designed a processor in college.  The first instruction takes one second.  The next instruction takes half a second.  The next instruction takes a quarter of a second and so on.  The processor doubles in speed with every instruction.

So, if a program takes longer than two seconds to run, it must be in an infinite loop.  If a program terminates, it will terminate before the two second mark.

So, with this in mind, this leads to "nondeterminism" in Turing Machines.

If you recall, nondeterminism in a finite automaton, means that nodes can have more than one valid transition for each character.  An "A" might transition to state 12 and also state 19.  Which one do you choose?  You choose the one that works!  A nondeterministic finite automaton is one that is said to accept a string if there is a path that would accept that string.

Similarly, nondeterministic finite automata allow for states to transition to multiple states depending on what's on the tape.  You can also have different to the tape.

For example, State 7 upon seeing 'X' can write 'Y' and move to state 12.
Or,          State 7 upon seeing 'X' can move LEFT and move to state 113.

The nondeterministic TM on decision problems, is said to accept the input if there is an execution path somewhere that will cause the Turing Machine to halt.

We sometimes call the nondeterministic Turing Machine an NTM.

Is the NTM more powerful than the TM?

No, it is not, because you emulate the NTM with a regular old TM.

We talked about how you can emulate any TM on another TM.

Without going into nitty-gritty detail, look at it like this.

You put the encoding of an NTM on the tape.  Your regular old Turing Machine keeps a queue of states and tapes and tape positions on the tape.  At each step, you pop a state and tape and tape position information, and see what your next states and tapes could possibly and add each possibility to the queue.

If there is a path to the HALT state, this TM will eventually find it.  If there is no path, your TM will infinite loop looking for it.

But it will emulate the NTM and halt whenever the NTM can possibly halt.

Some computer scientists think of the NTM as the "primary" model of computing.

This leads us to the most important unsolved problem in Computer Science.  Does P = NP?  Most "professional" computer scientists believe the answer is no, but a few think it's yes.  A lot of amateurs believe the answer is yes (and believe they can prove it...but they can't).

P is the set of problems that can be solved in Polynomial time on a regular Turing Machine.  In other words, if the answer is YES, the TM will halt before entering more than P(n) states where n is the length of the input and P is some polynomial.

So, if my polynomial P(n) = n^2, and my input takes up 5 squares on the tape, I would expect a YES to occur within 25 steps.

NP is the set of problems that can be solved in Polynomial time on a NTM.  In other words, if the answer is YES, there is a path through the NTM that will halt before entering more than P(n) states.

If a problem is in P, it is certainly in NP.  Every TM is already an NTM so it runs in polynomial time on a TM, it will run in the exact same on an NTM identical to itself!

If a problem is NP...well.  We know that it halt eventually on an TM if it halts on the NTM.  But it could take a while on the TM, exponential time and not polynomial time.

A lot of these decision problems can be solved very quickly on NTM's by "trying every combination simultaneously."  Try every possible solution nondeterministically and if one of them proves to work, HALT.  However, on a regular Turing Machine, trying every possible combination is likely to take a fair bit of time.

Imagine that you have a n-character string.  One permutation of this string will indicate a correct answer to some problem (HALT).

A NTM will just have different branches trying every permutation.  So, the NTM will halt quickly because there is a branch that will halt (if the answer is yes).

However, the regular TM would have to try every permutation of the string until it tries them all.  That would be n! attempts, and n! is not polynomial.