Turing Machine

定义 Definition

图灵机：一种由阿兰·图灵提出的抽象计算模型，用来形式化“可计算性”的概念。它通过一条可无限延伸的纸带、读写头和一组状态与规则来执行计算，是理论计算机科学中的基础模型。（在不同语境下也可指“通用图灵机”等更具体变体。）

发音 Pronunciation

/ˈtjʊərɪŋ məˈʃiːn/

例句 Examples

A Turing machine can simulate any algorithm in principle.
原则上，图灵机可以模拟任何算法。

Although a Turing machine is simple, it helps define what problems are computable and which are not.
尽管图灵机很简单，它却有助于界定哪些问题是可计算的、哪些不是。

词源 Etymology

Turing 来自提出者英国数学家 Alan Turing（阿兰·图灵） 的姓氏；machine 表示“机器/装置”。该术语源于图灵在 1936 年关于可计算数的论文中提出的模型，用以刻画“机械化计算”的边界。

相关词 Related Words

• Algorithm
• Automaton
• Computation
• Computability
• Decidability
• Formal Language
• Halting Problem
• State
• Tape
• Universal Turing Machine

文学与著作中的用例 Literary Works

• Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem（1936）：提出并系统化图灵机概念。
• Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid（《哥德尔、艾舍尔、巴赫》）：以图灵机相关思想讨论形式系统与计算。
• Michael Sipser, Introduction to the Theory of Computation：用图灵机作为计算理论的核心框架。
• Roger Penrose, The Emperor’s New Mind（《皇帝新脑》）：讨论计算、心智与图灵机等模型的关系。