Top Qs
Timeline
Chat
Perspective

Turing machine

From Wiktionary, the free dictionary

Remove ads

English

Etymology

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

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.
    Synonym: a-machine
    • 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.

Translations

See also

Further reading

Remove ads

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads
Remove ads