Construct · 1 fields · 3 citations

Turing machine: a standalone construct

One name. One construct. A landmark on the map.

● anchor · a standalone construct Nearest construct by meaninghalting problemcompare the meanings
How to read this

Every construct on the map is compared with every other by the meaning of its definitions, and the closest one is surfaced here. The nearest construct to Turing machine is halting problem.

Hold this as a prompt, not a verdict. Two constructs sitting close in meaning is a reason to read them side by side and decide for yourself whether they are one idea under two names. It is not proof that they are. Compare the meanings in the Collider.

Turingmachine1 CONSTRUCTTuring machineTURING · COMPUTABILITY

A single standalone construct; nearby constructs are located against it in the Collider. Tap a field for its definition, unit, and measures.

Computability theory

The abstract model that defines what is computable

Alan Turing's 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem (the decision problem) introduced the abstract device now called the Turing machine: a control unit that is always in one of a finite set of internal states, together with a head that scans an endless tape divided into cells, so that at each step the machine reads the symbol under the head, writes a symbol, moves one cell left or right, and changes state according to a fixed table of rules. Turing defined a number or function as computable exactly when some such machine, following its finite table, eventually produces the answer, which gave mathematics its first precise account of what an algorithm is and what any mechanical procedure can in principle do. The standard modern presentation, as in Michael Sipser's textbook, specifies the machine as a finite tuple of states, a tape alphabet, a transition function, a start state, and accepting and rejecting states, and the same model was carried into complexity theory by Juris Hartmanis and Richard Stearns in 1965, who used machines with several tapes to define how a computation's running time and memory grow with the size of the input. What makes the Turing machine a landmark is its generality: every other reasonable model of computation proposed since, from the lambda calculus to ordinary programming languages, has turned out to compute exactly the same class of functions, so the Turing machine now serves as the reference definition of the word computable and as the yardstick against which the difficulty of problems is measured.[1][2][3]

Unit
A single abstract machine, given as a finite table of state-and-symbol rules acting on an unbounded tape, that either halts with an output or runs forever
Recovery means
Not applicable
Measured by
Specified formally as a tuple of states, tape alphabet, and transition function; a problem is classified by whether some Turing machine decides it and, if it does, by the time and memory the computation requires

Next

Run it through the Collider, or take the citations with you.

See how Turing machine sits against neighbouring constructs in the Collider, or export every reference on this page in one click.

Open in ColliderExport BibTeXReport this entry

Nearby constructs

complexity4 fields · 7 citationsjingle · one word, four constructsrecursion4 fields · 8 citationsjingle · one word, four self-referring constructshead3 fields · 4 citationsjingle · one word, three constructs

References

  1. Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42(1), 230–265. https://doi.org/10.1112/plms/s2-42.1.230
  2. Sipser, M. (2013). Introduction to the theory of computation (3rd ed.). Cengage Learning.
  3. Hartmanis, J., & Stearns, R. E. (1965). On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117, 285–306. https://doi.org/10.1090/s0002-9947-1965-0170805-7

Cited on this page?

Confirm your construct, or correct us.

If your work is cited behind one of these entries, you know better than we do whether we captured the meaning right. Confirm it, suggest an edit, or dispute it, and your name goes on the entry as an author who has checked it, linked to your ORCID.

Claim your construct