Turing Machines

A theoretical (or "paper") model of computing.  There is a two-way infinite tape.  Each machine has a finite set of states.  Based on the current state, what's currently written on the cell of tape where the head is, you can move to another state, write a different character on the tape, and/or move the tape head left or right.  In this way, you can write crude computer programs.

Church's thesis says that no actual computer in the real world will be able to solve a problem that a Turing machine cannot.  Because of its precise mathematical nature, Turing Machines are often used to model algorithms.  When normal people think of algorithms, they think of a "RAM model".  RAM model:  memory access takes constant time, you never run out of memory.  There is no maximum integer, memory allocation always works, but other than that, things work like pretty much any programming language.

It has been demonstrated that the RAM model and the Turing Machine solve the exact same class of problems.  And have the exact same set of problems:  "infinite loops" "halting problem" etc.

Not only this, but the set of algorithms that run in polynomial time on both models are the same.  If an algorithm runs in O(f(n)) on a Turing Machine, it can also run in O(f(n)) on the RAM Model.

If it run in O(f(n)) time on the RAM model, then it can run in O((f(n))^3) time on the Turing Machine.
we can
And so, while all the major theorems are computability are done (historically) on the Turing Machine, they could be worked as well in the RAM Model.

The Universal Turing Machine.  This is a machine that accepts on tape an encoded representation of another turing machine, and the input for that other TM, and the UTM will then give the same output that the other TM would have given (or infinite loop if that's what the other TM would have done).

So, with the Turing Machine model, we can design other "paper" machines that solve other classes of problems beyond what TM can do; however, we do not any means of realizing these machines physically.

Specifically, the Nondeterministic Turing Machine (NTM).

A deterministic machine is one in which at any point in the process you have only one course of action.  So, you're in any specific state, looking at any specific cell on the tape, there is exactly one course of action.  You move right, left, or write a new character on the tape, and you move to a specific other state.

But with a NTM, you may have many courses of action at any given time.  The NTM just chooses the correct one out of all the options available.  If the problem can be solved, it'll solve it by choosing the correct one.

One way to look at it, we say a NTM solves the problem if there is a way for it to solve the problem (and that there is no way for it to halt on anything other than the correct answer.)

Another way to look at it, we have an infinite number of machines running all choices available for it.  If one of them halts, it yells at all the other ones to halt, and then we have our answer.

It turns out that TM can solve all the same sorts of problems that a NTM can.  They are equal in power.  And you can think of it like this.  The NTM still has a finite number of states and a finite number of characters that can be written on the tape.  So, at each step, the NTM may have a large number of possibilities for the next step, but that large number is still finite.  So, a TM can model this by meticulously trying all paths (in a breadth-first-search sort of way).

But, of course, when the TM emulates the NTM, by meticulously working through all paths, it takes the TM an inordinately long time to do this.  They have the computing "power" in that they can solve the same set of problems, but one runs a whole lot faster than the other.

So, this where we get the most important unsolved problem in the theory of computing.

A decision problem is a problem whose output is YES or NO, or alternatively, the output is a single bit.  In the nondeterministic world, the answer is YES if there is a path that leads to YES.  In the world of decision problems there is a definite YES/NO answer and everything halts.

So, looking at decision problems, we say that P is the collection of decision problems that can be solved in polynomial time on a TM.  (the number of states visited prior to halting has an upper bound of a specific polynomal over the length of the input.)

For example, given a list of numbers, is it sorted, yes or no?  Very easy to solve in polynomial time.

NP is the collection of decision problems that can be solved in polynomal time on a NTM.

The major unsolved problem in theoretical computer science is:  Does P = NP?  Obviously, P is a subset of NP.  But can every problem in NP be solved in polynomial time on a TM?  (or in the RAM model).

Traveling Salesman Problem:

You have a list of cities and the distances between them.  (All pairs).
Is it possible for a traveling salesman to visit every city on the list exactly one, returning to his starting position, without traveling more than m miles (and m is part of the input to the problem).

Easy for NTM.  You just have different branches try every possible route and see whether m is exceeded or not.  If m is met, halt with YES, otherwise halt with NO.

But how would you do it for a TM?  The best known algorithm is trial and error.