Turing machine

Definitions

1. A theoretical mathematical model of computation defined by Alan Turing in 1936, consisting of an infinite tape, a read/write head, and a finite set of states. Despite its simplicity, a Turing machine can compute anything that any computer can compute, making it the foundation of computability theory and the formal definition of an algorithm.

   In plain English: An imaginary simple machine invented by Alan Turing that mathematically defines what a computer can and cannot do — every real computer is just a fancy version of it.

   Example: Your fancy quantum computer is still, at its core, equivalent to a Turing machine — it just gets to the answer faster for certain problems.

Related Terms

• von Neumann architecture
• Lambda Calculus
• Church-Turing Thesis
• Computability
• Turing Completeness
• Halting Problem
• Lambda Calculus
• Finite State Machine
• Church-Turing Thesis
• Dunbar's Number