Concept

Turing machine

Overview

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

The machine operates on an infinite memory tape divided into discrete cells, 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, 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, who called it an "a-machine" (automatic machine). It was Turing's doctoral advisor, Alonzo Church, who later coined the term "Turing machine" in a review. 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?

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).

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

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.

Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).

Possible passages

Found by search and not yet checked by a person; they may only mention the idea in passing.

Any such select set is called the set of postulates, or premises, from which the reasoning proceeds. The reasoning is nothing else than the exhibition of the whole pattern of general conditions involved in the pattern derived from the selected postulates.
Alfred North Whitehead, Science and the modern world
States what Turing machine is.
Read the chapter · Open in the reader
All numbers must be numbers of something: there are no such things as numbers in the abstract. _Ten_ must mean ten bodies, or ten sounds, or ten beatings of the pulse. But though numbers must be numbers of something, they may be numbers of any thing. Propositions, therefore, concerning numbers, have the remarkable peculiarity that they are propositions concerning all things whatever; all objects, all existences of…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Turing machine is.
Read the chapter · Open in the reader
The next century undertook to bring order into the concepts, consistency into the doctrine, and rigor into the reasoning. The dominating trend of this movement was logical rather than methodological. The development was in the interest of the foundations of mathematics rather than in the use of mathematics as a method for solving scientific problems. Of course this has in no way interfered with the freedom of…
John Dewey, Creative Intelligence
Close in meaning to Turing machine; the term itself is not named.
Read the chapter · Open in the reader

Turing machine

Overview

Possible passages

Philosophers who discussed Turing machine

Related ideas

Place in the tradition