Turing machine

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

Related terms

• deterministic Turing machine
• nondeterministic Turing machine
• Turing complete
• Turing function
• Turing tape
• Turing test
• turmite
• universal Turing machine

 

Translations

abstract machine

• Arabic: آلَة تورنج f
• Chinese:

  Mandarin: 圖靈機／图灵机 (túlíngjī), 確定型圖靈機／确定型图灵机 (quèdìngxíng túlíngjī)

• Czech: Turingův stroj m
• Finnish: Turingin kone (fi)
• French: machine de Turing (fr) f
• German: Turingmaschine (de) f
• Hebrew: מכונת טיורינג f (mechonát tyúring)
• Hungarian: Turing-gép (hu)
• Icelandic: Turing-vél f, Turing vél f
• Italian: macchina di Turing (it) f
• Persian: ماشین تورینگ
• Portuguese: máquina de Turing
• Romanian: mașină Turing f
• Russian: маши́на Тью́ринга (ru) f (mašína Tʹjúringa)
• Serbo-Croatian: Turingov stroj m
• Spanish: máquina de Turing f
• Turkish: Turing makinesi

See also

• functionally complete

Further reading

• Turing machine on Wikipedia.Wikipedia