- Word
Turing machine
- Image
- Description
The British mathematician Alan Turing devised a hypothetical machine to carry out mathematical "algorithms". This construct is now termed a "Turing Machine". A given Turing machine consists of a linear "tape" containing readable/writable "cells", a "tape head" that can either read or write a symbol on the current tape cell or move to the left or the right on the tape, a set of "states" that the machine can be in at a given time, a initial state that the machine starts in, and a set of rules that map the current state and contents of the current tape symbol into an action for the tape head to take. The machine proceeds over a series of time steps until it reaches the "halt" state (if it is a "halting" machine). Turing's goal in devising this construct was to formalize the notion of "definite procedure" (or "algorithm"). A given Turing machine corresponds to what we would now call a "program" or "algorithm".
A universal Turing machine is a Turing machine that can emulate the operation of any other Turing machine on a given input. The universal Turing machine, designed by British mathematician Alan Turing, gave an early blueprint for programmable computers.
- Topics
- Computation, Computer Science
- Difficulty
- 1