⏾ Concept Map

Turing Machine ○꠹ Entries

↩ 🔵 🔵 🔵

Primary

၊၊||၊|။

Turing Machine ○꠹｜Definition｜1st｜20251119205401-00-⌔

Turing machine - Wikipedia

Turing machine

🖼️ ➺ 🖼️ ➺ 🖼️ ➺

Classes of automata

A Turing machine is a mathematical model of computation describing an abstract machine1 that manipulates symbols on a strip of tape according to a table of rules.2 Despite the model’s simplicity, it is capable of implementing any computer algorithm.3

The machine operates on an infinite4 memory tape divided into discrete cells,5 each of which can hold a single symbol drawn from a finite set of symbols called the alphabet of the machine. It has a “head” that, at any point in the machine’s operation, is positioned over one of these cells, and a “state” selected from a finite set of states. At each step of its operation, the head reads the symbol in its cell. Then, based on the symbol and the machine’s own present state, the machine writes a symbol into the same cell, and moves the head one step to the left or the right,6 or halts the computation. The choice of which replacement symbol to write, which direction to move the head, and whether to halt is based on a finite table that specifies what to do for each combination of the current state and the symbol that is read. As with a real computer program, it is possible for a Turing machine to go into an infinite loop which will never halt.

The Turing machine was invented in 1936 by Alan Turing,78 who called it an “a-machine” (automatic machine).9 It was Turing’s doctoral advisor, Alonzo Church, who later coined the term “Turing machine” in a review.10 With this model, Turing was able to answer two questions in the negative:

  • 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)?
  • Does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol?1112

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, or ‘decision problem’ (whether every mathematical statement is provable or disprovable).13

Turing machines proved the existence of fundamental limitations on the power of mechanical computation.3

While they can express arbitrary computations, their minimalist design makes them too slow 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 model of computation or 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.

Printed 2026-06-28.

(echo:: @ ᯤ)

Footnotes

  1. Minsky (1967, p. 107) “In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment—its tape—in which it can store (and later recover) sequences of symbols”, also Stone (1972, p. 8) where the word”machine” is in quotation marks. ↩

  2. Stone (1972, p. 8) states: “This ‘machine’ is an abstract mathematical model”, also cf. Sipser (2012, p. 165ff) that describes the “Turing machine model”. Rogers (1987, p. 13) refers to “Turing’s characterization”, Boolos, Burgess & Jeffrey (2002, p. 25) refers to a “specific kind of idealized machine”. ↩

  3. Sipser (2012, p. 165) observes that “[a] Turing machine can do everything that a real computer can do. Nonetheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation.” ↩ ↩2

  4. Cf. Sipser (2012, p. 165). Also, Rogers (1987, p. 13) describes “a paper tape of infinite length in both directions”. Minsky (1967, p. 118) states “The tape is regarded as infinite in both directions”. Boolos, Burgess & Jeffrey (2002, p. 25) include the possibility that “there is someone stationed at each end to add extra blank squares as needed”. ↩

  5. Cf. Rogers (1987, p. 13). Other authors use the word “square” e.g. Boolos, Burgess & Jeffrey (2002, p. 35), Minsky (1967, p. 117), Penrose (1989, p. 37). ↩

  6. Boolos, Burgess & Jeffrey (2002, p. 25) illustrate the machine as moving along the tape. Penrose (1989, pp. 36–37) describes himself as “uncomfortable” with an infinite tape observing that it “might be hard to shift!”; he “prefer[s] to think of the tape as representing some external environment through which our finite device can move” and after observing that the “‘movement’ is a convenient way of picturing things” and then suggests that “the device receives all its input from this environment. Some variations of the Turing machine model also allow the head to stay in the same position instead of moving or halting. ↩

  7. Hodges 2012. ↩

  8. The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by M. H. A. Newman in his lectures: “Was there a definite method, or as Newman put it, a ‘mechanical process’ which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable”. Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its Proceedings, but it was published in early 1937 and offprints were available in February 1937. ↩

  9. See footnote in Davis (2000, p. 151). ↩

  10. See note in forward Tyler & Emderton (2019) harvtxt error: no target: CITEREFTylerEmderton2019 (help). ↩

  11. Turing 1936 in Davis (2004, pp. 132–134); Turing’s definition of “circular” is found on page 119. ↩

  12. Turing 1936, pp. 230–265. ↩

  13. Turing 1936 in Davis (2004, p. 145) ↩

Link to original

Secondary

• • •