Classic Turing Machine with Tape Erasure

turingFull560

Alan Turing designed a mathematical structure to capture the essence of computation with the fewest number of elements, but so that universal computation would be possible. The result is usually referred to as the Turing Machine, and the study if this particular automaton along with many others forms the basis of automata theory taken by every computer science student. The subject is taught either in that theory class, or also sometimes in the broader area of discrete mathematics. If you are seeking to know computational thinking and the core conceptual basis for computer science, this is where you will find it.

The above physical model is by Mike Davey and is a beautiful piece of machinery. Turing Machines, in their core capability are amazingly simple devices: think of a machine having a read/write memory (you can store stuff in memory and then retrieve it later), a register (which stores the "state" of the machine), and a program that is composed of instructions to move around memory. The tape metaphor represents a linear motion along a tape (that is infinite in length). Make sure to play the video on Davey's site for a good explanation of the device and its operation. I found the erasing mechanism simple and yet elegant. Some model Turing machines use replacement of a physical artifact rather than erasure as with some Lego-based models where a small object is used to denote a bit and then "read" using an sensor capable of distinguishing between black and white objects.