Jump to content

Turing machine

From Wiktionary, the free dictionary

English

[edit]

Etymology

[edit]

Named after English mathematician, logician, and cryptographer Alan Turing (1912–1954), who introduced the concept in 1936 to give a mathematically precise definition of computability.

Noun

[edit]

Turing machine (plural Turing machines)

  1. (computing theory) An abstract computing machine that has a finite number of possible internal states and operates on an infinite memory tape by first reading a symbol from a cell in the tape, and then, deterministically, based on that symbol and the machine’s state, writing a symbol in that cell, moving to a neighboring cell, and/or changing state.
    • 2017, Arlindo Oliveira, The Digital Mind: How Science Is Redefining Humanity, MIT Press, →ISBN, page 81:
      Another class, P, is a subset of NP, and includes all decision problems that can be solved by a (deterministic) Turing machine in polynomial time.
[edit]

Translations

[edit]

See also

[edit]

Further reading

[edit]
Retrieved from "https://en.wiktionary.org/w/index.php?title=Turing_machine&oldid=78907124"