Michael Perkins

Alan Turing was a brilliant mathematician and logician whose work in the first half of the 20th century was seminal in the development of computer science. In his famous 1936 paper, "On Computable Numbers, with an Application to the Entscheidungsproblem," he introduced the notion of what is now called a Turing machine. Turing machines are imaginary computing devices that provide a useful formalism for investigating the notion of computability.

A Turing machine is a very simple device that uses a tape for storing and manipulating symbols. The machine can read or write a symbol at the current location of the tape, and it can move the tape one position either left or right. The machine contains a single register for recording the current state of the machine. At any point in its execution, the state of the machine together with the symbol read at the current tape position determines the machine's actions.
Despite its simplicity, the concept of a Turing machine adequately captures the general idea of computability. According to the Church-Turing thesis, anything that is computable is computable by a Turing machine. This means, for instance, that even the operation of an extremely complex modern digital computer system could be realized using the simple operations of a Turing machine.

Though Turing machines are interesting primarily for their theoretical properties, Mike Davey has built a physical Turing machine. The video below shows Davey's machine in action. You can find more information about this beautiful device at Davey's website.



In the following video, Davey's machine uses a typical Turing machine strategy to solve a simple subtraction problem.



Related:
Bertrand Russell