In Plain Language
A machine with a very long paper strip and a tiny head that reads one square at a time. It follows a short list of rules like "if you see a 1, cross it out and move right". That is all it can do. But if you write the rules cleverly enough, this simple thing can work out anything that can be worked out at all.
Turing imagined a machine with an endless tape divided into squares, a head that reads and writes one square at a time, and a small table of rules. Each rule says: given the symbol you are reading and the state you are in, write this symbol, move one square left or right, and switch to that state. Nothing else. The surprise is what that austere setup can do — any procedure you can describe precisely enough to follow by hand, some Turing machine can carry out. This gave the word "computable" a definition that did not depend on any particular machine, and it also marked the edge of the map: Turing showed there are questions no such machine can answer, however long it runs.
Why It Was Important
Alan Turing's mathematical model described a theoretical machine that manipulates symbols on a strip of tape according to a table of rules. This abstract model proved that any computation that can be algorithmically described can be performed by such a machine, establishing the theoretical boundaries of what computers (and ultimately AI) can achieve.
Who Invented It
Alan Turing
British mathematician, logician, and pioneering computer scientist.
Applications
- Computer Science Theory
- Algorithm Design
- Computability Theory
Key Papers
- On Computable Numbers, with an Application to the Entscheidungsproblem
Alan M. Turing · Proceedings of the London Mathematical Society · 1936
Videos
Turing Machines Explained - Computerphile
Computerphile
Turing & The Halting Problem - Computerphile
Computerphile