形式陈述

确定性单带图灵机可写为

$$ M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{acc}},q_{\mathrm{rej}}), $$$$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,q_{\mathrm{acc}},q_{\mathrm{rej}}),$$

其中 $Q,\Gamma$$Q,\mathrm{\Gamma }$ 为有限集，$\Sigma\subseteq\Gamma\setminus\{\sqcup\}$$\mathrm{\Sigma }\subseteq \mathrm{\Gamma }\setminus \{\bigsqcup \}$，终止状态互异，且

$$ \delta:(Q\setminus\{q_{\mathrm{acc}},q_{\mathrm{rej}}\})\times\Gamma \to Q\times\Gamma\times\{L,R\}. $$$$\delta :(Q\setminus \{q_{\mathrm{acc}},q_{\mathrm{rej}}\})\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R\}.$$

输入、带内容、读写头位置与当前状态共同构成配置。

直觉

图灵机用有限控制器操作无界但每次只访问一个格子的带，分离“程序有限”与“工作空间可随输入增长”。

例子与边界

判定器对每个输入都停机并接受或拒绝；识别器可在非成员输入上不停止。多带和非确定性变体改变效率或描述便利性，但在可计算语言集合上与标准模型等价。

推论与应用

图灵机定义可判定性、可识别性与时间/空间复杂度。有限集合、形式语言和转移函数是理解其元组定义的直接前置。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013, Chs. 0–10。
• Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 1936, Full paper。