Turing machine en · NOUN
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. Turing called it an a-machine; the term "Turing machine" was coined by his doctoral advisor Alonzo Church.
Meanings
-
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.
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.
2017, Arlindo Oliveira, The Digital Mind: How Science Is Redefining Humanity, MIT Press, →ISBN, page 81:
Forms
| Spelling | Features | Labels | Source |
|---|---|---|---|
| Turing machines | Number=Plur | lexicographic |
Relateds
Synonyms
Translations (21)
fa ماشین تورینگ (abstract machine) · sh Turingova mašina (abstract machine) · cs Turingův stroj (abstract machine) · he מכונת טיורינג (abstract machine) · pt máquina de Turing (abstract machine) · ro mașină Turing (abstract machine) · de Turingmaschine (abstract machine) · sh Turingov stroj (abstract machine) · hu Turing-gép (abstract machine) · cmn 圖靈機 /图灵机 (abstract machine) · ar آلَة تورنج (abstract machine) · is Turing vél (abstract machine) · es máquina de Turing (abstract machine) · cmn 確定型圖靈機 /确定型图灵机 (abstract machine) · fi Turingin kone (abstract machine) · fr machine de Turing (abstract machine) · ru маши́на Тью́ринга (abstract machine) · it macchina di Turing (abstract machine) · tr Turing makinesi (abstract machine) · is Turing-vél (abstract machine) · pl maszyna Turinga (abstract machine)