Turing Machines - Tutorials 
How the first Turing machine was born

All about Turing Machines:

This simple introduction to Turing machines covers the basic concepts in a narrative form, and has some good links at the bottom of the page that point to more detailed information.

More programming-oriented detail about the operation of a Turing machine can be found in this excerpt for Ivars Peterson's The Mathematical Tourist.  Peterson's article provides the necessary background for this article by Jack Copeland, which includes a little theory.  Dr. Copeland is the Director of the Turing Archive for the History of Computing, University of Canterbury in New Zealand.  Another resource which covers some of the same ground is available here.

A more rigorous description of a Turing machine can be found at Wikipedia.  If it's mathematical rigor you need, take a look at Wolfram's MathWorld site.


Universal Turing Machines:

The Universal Turing machine is the basis of the von Neumann architecture, the principle architecture that most CPUs use today.  (The distant second award goes to the Harvard architecture.)  Of course, MathWorld also has a description.


Church-Turing thesis:

In 1900, David Hilbert proposed a series of 23 mathematical problems.  The second problem--"Prove that the axioms of arithmetic are consistent" was partly addressed by Kurt Gödel, who showed that no proof was possible within the domain of arithmetic itself.  Turing extended Gödel's work and showed that even if something could be expressed as an algorithm, there is no positive proof that the algorithm will be able to compute a solution in a finite period of time.  For instance, no positive proof that an algorithm to compute the exact value of π  in a finite amount of time can be found.  Hilbert's problem is callled the "Entscheidungsproblem."  

Turing's thesis:  Turing machines can do anything that can be described as "rule of thumb" or "purely mechanical."

Church's thesis:  A function of positive integers is effectively calculable only if recursive.

At first glance, it may be hard to see why these are similar statements.  To see why they are, read this article first.  A more comprehensive discussion of the Church-Turing thesis (and why it's hyphenated!) is here.  Jack Copeland, a leading Turing scholar, wrote a very good article on the Church-Turing thesis.


Halting problem:

The halting problem can be defined as:  Given a finite algorithm with finite input, can we prove if the program will run in a finite time?  This was the problem that Turing addressed.  (The answer is no.)

How would anyone go about writing a program to prove or disprove the halting problem?  There's a clear explanation here as to why such a program can't be written.


Busy Beaver problem:

The busy beaver problem is an example of the halting problem.  It only stops when it runs out of resources such as tape or the patience of the person running the program, neither of which are infinite.  Wikipedia gives a more rigorous definition; additional articles about the busy beaver problem are here:  [ 1 | 2 | 3 | 4 ].

     Home   |   Overview   |   History    |   Tutorials   |   Multimedia and Lectures    
Examples and Simulations   
|   Advanced Topics