图灵机

图灵机是一种更加精密的通用计算机模型，能够模拟实际计算机的所有计算行为。

自然语言表达

图灵机可以描述为具有以下配件和功能的机器：

• 一根无线长的纸带作为存储
• 一个读写头，能够在纸带上左右移动并执行读取和写入操作
• 一个内部存储，用于记录图灵机的当前状态
• 一个程序表，用来表达机器计算的逻辑
• 两个特殊的预置状态，接受或停止，当图灵机进入这两个状态之一就会停止运行

形式化表达

图灵机是一个 7 元组 $(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{accept},q_{reject})$，参数具体含义如下：

参数	含义
$Q$	状态集，有限集，存储图灵机所有可能的内部状态
$\Sigma$	输入字符表，有限集，在机器启动之前确定
$\Gamma$	图灵机存储中的字符表，有限集，$\Sigma \subseteq \Gamma$
$\delta$	转移函数，图灵机的核心
$q_0$	初始状态，$q_0\in Q$
$q_{accept}$	接受状态，$q_{accept}\in Q$
$q_{reject}$	拒绝状态，$q_{reject}\in Q$

其他概念

格局：在图灵机的计算过程中，当前内部状态、当前存储中的所有内容，当前读写头的位置组合在一起，构成当前图灵机的格局(configuration)，常用符号 $C$ 表示

判定器：图灵机处理输入时只有三种结果：接受、拒绝、循环计算；对于任意输入都不产生循环的图灵机我们称为判定器

语言：由一个有限字符表产生的符合某种特殊性质的字符串的集合；事实上这也的确是我们日常生活中所谓的“语言”的精确定义

注意

这里提到的”符合某种特殊性质”这个修饰语并不是可有可无的，它决定了这个语言是否是可数集，同时也意味着语言的补集的存在

图灵可判定：如果一个语言能够被某一个图灵机判定，表示对于这个语言内的字符串，图灵机能在有限时间内接受，对于不在这个语言内的字符串，图灵机能在有限时间内拒绝，总之不会进入无限循环，则这个语言是图灵可判定的(Turing decidable)

图灵可识别：图灵可判定性质的弱化，若某个语言是图灵可识别的，则表示对于这个语言内的字符串，图灵机能在有限时间内接受，对于不在这个语言内的字符串，图灵机可能会在有限时间内拒绝，也可能会进入无限循环

图灵机的变形

上面讨论的都是经典的图灵机，而图灵机还有很多其他的形式（例如增加纸带的个数等），但是他们识别语言的能力都是相同的；

像这种在形式上发生变化但是在功能上保持不变的性质称为稳健性(robustness)；而图灵机具有惊人的稳健性，似乎在某种程度上也表示了图灵机的通用计算能力

下面是两个图灵机的经典变形：

• 多带图灵机：能够同时处理多条纸带的图灵机
• 非确定型图灵机：在计算过程中，机器可以在多种可能性动作中选择一种继续进行，其计算图是树形结构

思考🤔

这两个图灵机变形从形式上来看比经典图灵机要更加强大，但它们在能力上都是一样的；如今花样繁多的 AI 算法从能力上来说会不会也是等价的？