A Turing machine is an abstract computational model that manipulates symbols on a tape.Formally, a Turing machine consists of an infinite tape divided into cells, each containing a symbol from a finite alphabet; a control unit with finite state memory; and a head capable of reading, writing, and shifting by one cell. The transition function determines, based on the current state and the read symbol, a new symbol, the direction of head movement (L/R), and a new state. The machine starts with an input word on the tape and may halt in an accepting or rejecting state, or get stuck in an infinite loop. A universal Turing machine can simulate any other machine given its description — anticipating the concept of a programmable computer.
In 1936, Alan Turing, solving David Hilbert's Entscheidungsproblem (decision problem), introduced the notion of an 'a-machine' (automatic machine) in his paper 'On Computable Numbers'. His goal was to formalize the intuitive concept of an algorithm. Independently, Alonzo Church arrived at an equivalent notion via λ-calculus. The Church-Turing thesis asserts that any intuitively computable process can be implemented on a Turing machine. In 1945, John von Neumann used this model in the EDVAC architecture — the prototype of modern computers. In 1985, David Deutsch proposed a quantum Turing machine, paving the way for quantum computing.
A Turing machine computes by manipulating symbol strings. Algorithmically, it is equivalent to a programming language with a single array of infinite length. Key properties: existence of a universal machine (interpreter), undecidability of the halting problem (one cannot algorithmically determine whether an arbitrary machine halts on a given input), the recursion theorem (a machine can obtain its own description). In complexity theory, one considers oracle machines (with extra information) and probabilistic machines (with a random bit source). Quantum Turing machines operate on states in a Hilbert space and use unitary transformations; they do not violate the Church-Turing thesis but may provide exponential speedup for certain problems.
Any computer program — from a calculator to an AI assistant — reduces to instructions that a Turing machine can execute. The entire theory of computation is based on it.
The simplest universal Turing machine, devised by Marvin Minsky, uses only 7 states and 4 symbols — and yet it can compute everything a powerful supercomputer can, albeit incredibly slowly.










