Turing Machine

A Turing machine is an abstract mathematical model of computation: a machine that reads and writes symbols on an endless strip of tape, one cell at a time, moving left or right and changing its own internal state according to a fixed table of rules. Alan Turing devised it in 1936, originally calling it an automatic machine, and used it to prove that certain well-defined mathematical questions, including the decision problem for logic known as the Entscheidungsproblem, can never be settled by any mechanical procedure at all. Despite its simplicity, a Turing machine can carry out any computation that any actual computer algorithm can, a claim known as the Church-Turing thesis, and a system able to simulate a Turing machine is said to be Turing complete. Real computers run far faster than a Turing machine's own step-by-step tape operations, but they are no more powerful in terms of what they can, in principle, compute.