Turing's Machine

In the 1930's, an English mathematician had an idea that would change the world. His name was Alan Turing. The question he was trying to answer is this: could there exist, at least in principle, any definite method or process by which all mathematical questions could be decided? His answer has implications far beyond the realm of theoretical mathematics.

See the Best Turing Website!

Biographer, Andrew Hodges

Turing imagined a machine. It would perform certain simple operations with symbols on a paper tape. The Turing Machine could read a symbol, write a new symbol, and move in either direction on the tape. The decisions for whether or not to change a symbol and which direction to move are made using a finite set of exact instructions. Turing reasoned that any problem that could be expressed correctly in terms of a set of instructions for this machine could be solved, given an infinite length of paper tape, and an infinite amount of time.

Turing Machine
on the Web!

Link to a Turing machine simulation

Each place on the tape needs only to ever represent two quantities: zero or one. It is often represented as a series of ones and zeros, or as a long line of switches that are either on or off. Binary is the term used to indicate numbers written using only two digits (or base two numbers). Turning said that any problem that is computable could be done as a set of simple operations on a binary code.

The Turing Machine was not actually a mechanical instrument, only a theoretical construct, like a formula or an algorithm. There was not technology in the 1930's to make an electric computer. Turing did realize that his idea had practical applications: he went on to build machines that helped the allies break Nazi codes, and boldly speculated that the human mind might function like his theoretical machine. His ideas are seminal in the fields of computer science and artificial intelligence.