Turing machine

  • automata theory.svg
    about this image
    classes of automata
    (clicking on each layer gets an article on that subject)

    a turing machine is a mathematical model of computation that defines an abstract machine,[1] which manipulates symbols on a strip of tape according to a table of rules.[2] despite the model's simplicity, given any computer algorithm, a turing machine capable of simulating that algorithm's logic can be constructed.[3]

    the machine operates on an infinite[4] memory tape divided into discrete "cells".[5] the machine positions its "head" over a cell and "reads" or "scans"[6] the symbol there. then, as per the symbol and its present place in a "finite table"[7] of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing),[8] then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head),[9] then (iii) (as determined by the observed symbol and the machine's place in the table) either proceeds to a subsequent instruction or halts the computation.[10]

    the turing machine was invented in 1936 by alan turing,[11][12] who called it an "a-machine" (automatic machine).[13] with this model, turing was able to answer two questions in the negative: (1) does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task); similarly, (2) does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol.[14] thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the entscheidungsproblem ('decision problem').[15]

    thus, turing machines prove fundamental limitations on the power of mechanical computation.[16] while they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world computers are based on different designs that, unlike turing machines, use random-access memory.

    turing completeness is the ability for a system of instructions to simulate a turing machine. a programming language that is turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are turing complete if the limitations of finite memory are ignored.

  • overview
  • description
  • formal definition
  • additional details required to visualize or implement turing machines
  • models equivalent to the turing machine model
  • choice c-machines, oracle o-machines
  • universal turing machines
  • comparison with real machines
  • history
  • see also
  • notes
  • references
  • external links

Combinational logicFinite-state machinePushdown automatonTuring machineAutomata theoryAutomata theory.svg
About this image
Classes of automata
(Clicking on each layer gets an article on that subject)

A Turing machine is a mathematical model of computation that defines an abstract machine,[1] which manipulates symbols on a strip of tape according to a table of rules.[2] Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.[3]

The machine operates on an infinite[4] memory tape divided into discrete "cells".[5] The machine positions its "head" over a cell and "reads" or "scans"[6] the symbol there. Then, as per the symbol and its present place in a "finite table"[7] of user-specified instructions, the machine (i) writes a symbol (e.g., a digit or a letter from a finite alphabet) in the cell (some models allow symbol erasure or no writing),[8] then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head),[9] then (iii) (as determined by the observed symbol and the machine's place in the table) either proceeds to a subsequent instruction or halts the computation.[10]

The Turing machine was invented in 1936 by Alan Turing,[11][12] who called it an "a-machine" (automatic machine).[13] With this model, Turing was able to answer two questions in the negative: (1) does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task); similarly, (2) does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol.[14] Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the Entscheidungsproblem ('decision problem').[15]

Thus, Turing machines prove fundamental limitations on the power of mechanical computation.[16] While they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory.

Turing completeness is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete if the limitations of finite memory are ignored.