Turing machines
Abstract computational models consisting of infinite tape, read-write head, finite control, and state transitions. Turing machines define computability—a function is computable if a Turing machine calculates it. Turing completeness means a language can compute anything a Turing machine can. Fundamental to understanding computation limits.
Real World
Alan Turing's 1936 paper introduced the Turing machine concept, which directly inspired John von Neumann's architecture used in virtually every modern computer, from iPhones to NASA's Mars rovers.
Exam Focus
When tracing a Turing machine, draw a clear table showing state, tape contents, head position, and action at each step.
How well did you know this?