图灵机
图灵机（汉语拼音：Tulingji；英语：Turing machines），一种抽象的计算模型。因英国数学家A.M.图灵于1936年提出而得名。研究图灵机的主要目的是对“算法”、“有效过程”这样的直观概念给出精确的数学定义，从而精确刻画可计算性与可判定性等基本概念。由于图灵机在计算能力上等价于数字计算机，故利用图灵机可以研究计算机的能力和局限性。对图灵机的研究集中在两个方面：第一，研究图灵机所定义的语言类，该语言类称为递归可枚举集合。第二，研究图灵机所计算的函数类，该函数类称为部分递归函数。
作为有效过程或算法的形式模型，图灵机的每个动作过程都应该是有穷可描述的。其次，每个过程应该由离散的步骤组成，每一步都能够机械地实现。图灵机有多种模型，如非确定型，多维型，多带多头型等，它们在计算能力上是等价的，且都是图灵机基本模型的变种。
基本模型
图灵机基本模型有一个有穷控制器，一条输入带和一个带头，带被分成许多单元，带头在每个时刻扫视带上的一个单元。该带有一个最左单元，向右则是无限的。带的每个单元正好可容纳有穷个带符号中的一个。开始时，最左边n个单元（n≥0，是一有穷数）放着输入，它是取自带符集的一个字符串，其余无穷多单元放空自符。空自符是特殊带符号，但不是输入符号。基本模型可图示如下：
在一个动作中，图灵机根据带头扫视的符号和有穷控制器的状态，执行如下操作：①改变状态。②在被扫视的带单元上打印一个符号，以代替原有的符号。③将带头向左或向右移动一个单元。形式上，一个图灵机（TM）记成一个七元组：
M＝（Q，Σ，Γ，δ，q0，B，F），其中：Q是状态的有穷集合；Γ是允许使用的带符号的有穷集合；B是空白符，B∈Γ；Σ是输入符号集，Σ
Γ-｛B｝；δ是下一动作函数，它是从Q×T到Q×Γ×｛L，R｝的映射，δ对某些自变量可没有定义。q0是初始状态，q0∈Q；FQ是终结状态的集合。
在每一时刻，机器所处状态，带子上已写符号的所有格子以及机器当前扫视的格子位置，统称为机器的格局。图灵机从初始格局出发，按程序一步步把初始格局改造为格局的序列。此过程可能无限制继续下去，也可能遇到指令表中没有列出的状态、符号组合或进入结束状态而停机。在结束状态下停机所达到的格局是最终格局，此最终格局就包含机器的计算结果。
其他模型
对图灵机的基本模型进行修改或扩充，可以得到多种其他类型的图灵机：①双向无限带图灵机。其带子向左向右都是无限长的，与基本模型不同的是，它的带子没有左端、带头永远不会走出两端。②多带多头图灵机具有一个有穷控制器，k个带头和k条带子，每条带子都是双向无穷的，并且各带头在操作时相互独立，除改写带符左右移动外，还可以保持不动。双带多头图灵机是单带图灵机的直接推广。③非确定型图灵机。具有一个有限控制器和一条单向无限带，对于一个给定的状态和被带头扫视的带符号，机器对下一动作可有有穷多个选择，每个选择包括一个新状态，一个要打印的带符号和一个带头移动方向。如果存在一个动作选择序列导致一个接受状态，则称该非确定型图灵机接受它的输入。④多维图灵机。具有通常的有穷控制器，但带子由k维单元阵列组成，并且在所有2k个方向上都是无限扩展的，这里的k是一固定的数。根据当前状态和被扫视的符号，多维图灵机的下一动作包括：改变状态；打印一个新符号；在2k个方向之一上移动它的带头。
除极个别情形外，上述图灵机的变种并未扩展图灵机的计算能力，它们计算的函数类与基本图灵机是相同的，但对研究不同类型的问题提供了方便的理论模型。
用途
作为研究计算的一般性质的抽象工具，图灵机主要有3种用途，也可以认为是研究图灵机的3种观点。
①作为语言接受器。被M接受的语言记作L（M），它是Σ*中的这样一些字符串的集合，当把这些字符串放在M的带子上，M处于q0状态且M的带头处在最左单元时，这些字符串可以使M进入一个终结状态而停机。给定一个识别语言L的图灵机M，一般假定，当输入被接受时，M为停机，即没有下一动作。然而对于不被接受的字符串，M可能永不停机。被图灵机接受的语言称为递归可枚举语言。递归集合是递归可枚举集合的子类，递归集合总能被对所有输入都能停机的图灵机所接受。
②作为整数函数计算机。被图灵机计算的函数称为部分递归函数。在某种意义上，部分递归函数类似于递归可枚举语言，因为计算它的图灵机在给定的输入上可能不停机。完全递归函数对应于递归语言，因为它能被总能停机的图灵机计算。
③作为语言产生器。设M是一个多带图灵机，它用一条带作为输出带，在这条带上，符号一经写上就不能再改写，输出带的带头也不能左移。假定在输出带上，M写出某个字母表Σ上的一些字符串，并用分隔符分开，则最终打印在输出带上的字符串的集合就称为由M生成的语言，记为G（M）,G(M)Σ*。如果L是某个图灵机生成的语言，则L是递归可枚举集合，反之亦然。
