The Turing Machine

In the late 1930's, the British mathematician Alan Turing published a paper in which he proposed what has come to be called the" Turing machine." A Turing machine is not an actual steel-and-rivets machine, it is a theoretical machine. Turing's idea was to imagine the simplest-possible device that could perform the same tasks as any newfangled electronic computer.

A Turing machine is indeed very simple - it has two parts. One part is an infinitely long tape divided into cells. Each cell may or may not contain a symbol (often 0 or 1).The other half of a Turing machine is the "head", which can move along the tape one cell at a time in either direction, reading the symbol in the current cell and perhaps writing a new symbol there. The head may have several different "states" which determine how the head will react to the current symbol. So, the machine reads the symbol at the current location on the tape, and based on this symbol and its current state, it may write a new symbol in the cell, and/or move one cell to the left or right, and/or change its current state.

A Turing machine is certainly a simple device! However, many surprising results have come from the study of Turing machines. Among them:

• There is such a thing as a Universal Turing machine, which is a Turing machine that is capable of emulating any other Turing machine. It "learns" how to do this by first processing instructions on its tape that tell it how to "build" the given Turing machine, and then processing the just-created Turing machine's instructions.
  
  
• A Turing machine is (theoretically) capable of doing anything - performing any calculation - that any "real" computer can do. This is why Turing machines are still studied as theoretical models - if a Turing machine can't do it, then no other computer, no matter how big, how complicated, or how fast, can do it either!

The Shocker:

Why bring up the Turing machine? Besides the fact that it is exteremely interesting, notice that Turing machines have a lot in common with elementary cellular automata. They both have cells, they both have simple rules, they both process one cell at a time, etc. Additionally, it has been shown that some elementary CAs (like rule 110 CAs) are not only logically equivalent to Turing machines - they are equivalent to Universal Turing machines!

Wow! What is going on in an elementary CA can be equivalent to what is going on in the biggest, fastest computer that will ever be built!

last update February 19, 2010 by JL Stanbrough