图灵机是一种数学计算模型，由有限控制器、划分为单元格的无界纸带，以及读写符号的读写头组成。艾伦·图灵于1936年提出这一模型，为研究算法能够计算什么提供了精确的框架。尽管图灵机的基本操作十分简单，只要有足够的时间和存储空间，它就能模拟通用计算。这一模型是计算机科学、可计算性理论和计算复杂性的基础。(theory.stanford.edu)
历史起源
图灵在《论可计算数及其在判定问题中的应用》中提出了这一模型。他的出发点是一个按照明确规则进行计算的人：此人使用书写的符号，并且只有有限种可区分的思维状态。图灵机是对这一活动的抽象，而不是对某种具体电子设备的描述。图灵最初着重讨论生成数字序列的机器，其中包括生成可计算实数表示的机器。(theory.stanford.edu)
这项研究探讨了与大卫·希尔伯特有关的判定问题：是否存在一种通用的有效过程，能够判定一阶逻辑中任意公式的有效性。图灵证明了答案是否定的。他的论文还将机器可计算性与阿隆佐·丘奇独立提出的有效可计算性理论联系起来。(theory.stanford.edu)
结构与运行
纸带提供存储空间。每个单元格存放有限字母表中的一个符号，该字母表包含一个专门的空白符号。输入通常是写在一条其余部分均为空白的纸带上的有限字符串。读写头每次扫描一个单元格；控制器的状态与当前扫描到的符号共同决定下一步操作。每次转移都会写入一个符号、改变状态，并将读写头向左或向右移动一个单元格。(people.csail.mit.edu)
一种常见的确定性图灵机定义包含七个组成部分：
[ M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{accept}},q_{\mathrm{reject}}). ]
其中，(Q) 是有限状态集；(\Sigma) 是输入字母表；(\Gamma) 是纸带字母表，包含 (\Sigma) 和空白符号；(\delta) 是转移规则；其余三个组成部分分别指定初始状态、接受状态和拒绝状态。进入任一终止状态，计算便结束。对于非终止状态，转移规则的形式为
[ \delta(q,a)=(q',b,D),\qquad D\in{L,R}. ]
这表示：在状态 (q) 下读到符号 (a) 时，写入 (b)，进入状态 (q')，并沿方向 (D) 移动。(people.csail.mit.edu)
一个配置记录当前状态、读写头位置和纸带内容。纸带虽然无界，但在任何有限的计算过程中，都只能访问有限个单元格。因此，无限的存储容量并不意味着机器能在一步之内执行无限次操作。(ocw.mit.edu)
计算函数与识别语言
图灵机可以计算函数：它以编码后的自变量作为输入，并在停机时留下编码后的结果。如果它对某些自变量无法停机，那么它计算的是部分函数，而非全函数。数字和其他具有结构的对象，都必须先用有限的符号表示。(live.ocw.mit.edu)
对于判定问题，输入是属于或不属于某个形式语言的字符串。判定器对每个输入都会停机，接受属于该语言的字符串，并拒绝不属于该语言的字符串。识别器必须接受属于该语言的每个字符串，但对于不属于该语言的字符串，它可以拒绝，也可以无限运行下去。因此，识别一种语言的要求弱于判定这种语言：没有接受输入，并不一定意味着能够在有限时间内给出否定答案。(mitp-content-server.mit.edu)
通用性与丘奇—图灵论题
通用图灵机以编码后的机器描述及该机器的输入为输入，模拟其执行过程。因此，单个固定的转移表就能执行许多不同的计算：程序成为纸带上提供的数据。这为通用计算机提供了数学范式。(theory.stanford.edu)
丘奇—图灵论题指出，每个有效可计算的函数都是图灵可计算的。它将按规则进行计算这一非形式化概念与形式模型联系起来，而不是一个根据数学定义证明的普通定理。独立定义的其他模型，包括λ演算和递归函数形式体系，都具有与图灵机等价的计算能力。(ocw.mit.edu)
如果一种编程语言或计算系统在适当的无界资源假设下能够模拟任意图灵机计算，就称其具有图灵完备性。物理计算机的内存是有限的，因此，这一表述指的是它们理想化的计算能力，而不是实际拥有无限的存储空间。(live.ocw.mit.edu)
计算的界限
停机问题询问：给定一台机器和一个输入，这台机器最终是否会停机。不存在能够对所有机器与输入的组合都正确判定这一问题的图灵机。一种标准的反证法先假定这样的判定器存在，再构造一个程序：当该程序以自身的描述为输入时，它的行为与判定器的预测相反。由此产生的自指使两种预测都会导致矛盾。(ocw.mit.edu)
不可判定性不同于运行时间过长。在这一模型中，不可判定问题不存在对所有输入都正确且能够停机的算法；而可判定问题也可能需要实际难以承受的资源。(ocw.mit.edu)
变体与资源度量
多带图灵机具有多条纸带和独立移动的读写头。非确定性图灵机允许存在多个可能的转移，只要有一个计算分支接受输入，机器就接受该输入。这些变体不会扩大可计算问题的范围，但可能改变资源需求。(math.mit.edu)
时间复杂度以输入长度为自变量，衡量计算步骤数；空间复杂度则衡量所使用的存储空间。精确的界限取决于机器模型的具体约定。一种标准模拟方法可以将耗时 (t(n)) 步的多带计算转换为耗时 (O(t(n)^2)) 步的单带计算，前提是 (t(n)\geq n)。这类比较区分了计算能力与计算效率，也说明了为什么分析资源需求时必须明确所采用的模型。(ocw.mit.edu)