Turinggép

The Turinggép, known in English as a Turing machine, is a theoretical computing model introduced by the English mathematician and logician Alan Turing in 1936. It formalizes the concept of computation and serves as a cornerstone of theoretical computer science. A Turinggép consists of an infinite tape divided into cells, a tape head that can read and write symbols on the tape and move left or right, and a finite set of states controlling its operations. The machine’s behavior is governed by a transition function that defines, for each combination of current state and tape symbol, the symbol to write, the direction to move, and the next state.

Turing introduced the machine to explore the limits of mechanical computation and to address the Entscheidungsproblem, or decision problem, posed by mathematician David Hilbert. He proved that there exist decision problems that cannot be solved by any algorithmic procedure, thereby establishing the existence of undecidable problems. This result, often summarized as the undecidability of the halting problem, is fundamental to the field of computability theory.

Although purely abstract, the Turinggép model captures the essential properties of real computers. It provides the basis for the Church–Turing thesis, which conjectures that any function computable by an effective method can be computed by a Turing machine. The model has influenced numerous areas, including the design of programming languages, the development of complexity theory, and the analysis of quantum computing. Modern theoretical work continues to examine extensions of the basic machine, such as multi-tape Turing machines, probabilistic and non-deterministic variants, and parallel execution models. The Turinggép remains a central concept for understanding the capabilities and limitations of computation.