A Turing machine is a simple theoretical computer.  Click several times on the step button below and try to figure out what is going on.  A particular Turing machine will depend on a finite set of states, Q, a finite set of tape symbols, T, and a finite set of rules.  One of the states is denoted the initial state.  The rules are of the form (A B C D) where A and D are states and B is a tape symbol and C is either R or L or a tape symbol.  R and L are neither states nor tape symbols.  Q and T have no elements in common.  We think of a Turing machine as a box with some memory connected to a read-write head that can read one cell of an infinite tape.  This read-write head can also write in the cell it is looking at, and it can move one cell at a time to the right or left.  The rule (p _ 1 q) below means that if the machine is in state p and looking at a blank cell, the read-write head will write a 1 in the cell and the machine will transition to state q.  The rule (q 0 R q) means that if the machine is in state q and looking at a 0, the read-write head will move right one cell and the machine will stay in state q.  The rule (r 0 L p) means that if the machine is in state r and looking at a 0, the read-write head will move left one cell and the machine will transition to state p.  When the read-write head writes a symbol in a cell, there is no trace of the previous symbol.

A Turing machine is as powerful as any computer.  That is, any function that a computer can compute can be computed by a Turing machine.  Below is a simple almost Turing machine that counts.  I wrote "almost" because a Turing machine's tape is infinite, but the tape below (like all computer memories) is finite.  That means that a Turing machine is more powerful than any computer.  I heard someone counter the previous statement by saying that Turing machines are much slower than real computers.  That person made an unnecessary assumption about how much time it takes a Turing machine to make a move.  We can imagine a Turing machine that takes half as much time to make move m + 1 than it takes to make move m.

Alan Turing, student of Alonzo Church, devised the computational model of Turing machines.  It was a memorable moment when I was taking a Mathematical Logic course taught by Wayne Richter at the University of Minnesota and he said he believed the Church-Turing thesis was true because Church was his thesis advisor.  The Church-Turing thesis states that everything that can be computed can be computed by a lambda expression (something like a Lisp program) or a Turing machine.