A simple Turing machine

 How do you make it run? With this animation you can see a simple Turing machine at work. Just press 'Start' and the machine starts running. If the speed is not as you want it, then press '<' to slow it down or press '>' to make it run faster. After some time it has done his job. Can you figure out what his job is? If it isn't immediately clea, just try it again by pressing 'Replay'.
Alan Mathison Turing, UK, 1912-1954
What is a Turing machine? It has a tape of individual cells of infinite length (to both sides). Each cell may contain a single symbol. In the case of our machine here these are the a's and b's. Furthermore on the tape there is a read/write-head which can read a single cell at a time. This cell is indicated by a yellow background in the animation.
The internal structure consists of labeled transitions between different possible internal states -- the numbered nodes -- of which one of those states is designated the initial state, which is here node number 1.
The labeled transitions tell the machine what to to do. The label consists of two parts:

(symbol, instruction)

The machine performs the action instruction when it reads symbol on the tape, and modifies its internal state by following the arrow that carries the label (symbol,instruction). For empty cells we use the symbol '_'. The instruction may be a symbol which tells the head to put this symbol in its current position. The instruction may also be '<' or '>' which tells the machine to move its read/write-head to move left or right respectively.

Turing's thesis and computability Initially Turing invented his machines in the early thirties of the twentieth century to give a precise definition of what it means that a problem is or is not computable. The thesis of Turing says that for every computable problem there exists a Turingmachine that solves it. Alonzo Church (1903-1995), an American mathematical logician gave an equivalent (a bit earlier than Turing) definition in terms of so-called recursive functions (much harder to understand for outsiders). That's why the thesis is also known as the Church-Turing thesis. It still stands today, that is, there is no problem known to be computable by means of some other mechanical device which cannot be solved by a Turing machine. Turing himself found several `realistic' problems for which he was able to prove that they are not computable in terms of his definition.

Alonzo Church, USA, 1903-1995