In 1936 English mathematician and computer theorist Alan Turing (1912-1954), while studying at Cambridge University, began work in predicate logic. His studies led in 1937 to a proof that certain mathematical problems could be solved by automation. Turing postulated a universal machine--the Turing machine, which would function by passing through a series of discrete states or steps, assuming only one of a possibly infinite list of internal states at any given moment.

Turing described his machine in the paper On Computable Numbers with an Application to the Entscheidungsproblem ("decidability problem"). The Turing Machine consists of the following components: (1) An infinitely long input/output tape stretched like a scroll between rollers so it can be wound forwards and backwards. The tape is marked off into squares, each marked with a 0 or 1. (2) A read/write head that sits above the tape, scanning one symbol at a time, and is always...