[音乐] 嗨，欢迎回来，下面我们来介绍图灵机的一些 变种或者叫做变体，就除了这个标准的这个 单纸带，确定性和单向无限的这种图灵机而言， 那么我们实际上很多这个专家发展了不同的这个图灵机的模型。 那么我们来先来看看第一种，第一大类，就是把这个图灵机的设施进行了一些扩展。 我们知道图灵机的设施呢，就包括了纸带和读写头对吧？ 那么单纸带，单读写头，好，我们把它扩展，那么有一种扩展呢就是有 叫做多带图灵机，那么它具有k条纸带。 同时呢，当然每个纸带上都有一个读写头，那有k个读写头。 那么这个纸带和读写头之间，它们是相对是独立的。 读写头 它不会绑定在一起，但是呢整个的机器的状态是唯一的。 状态集是放在一起，那么也就是说在一个状态下，那么我可以同时指定 每条纸带的这个每一个读写头它都采取不同的这种动作。 那么这里呢就会有k条纸带，k个读写头。 那么当然关键的和单纸带的单个读写头的这种 图灵机而言，它的差别呢还是在于这个计算规则上的差别。 我们原来的这个状态转移函数就是每条规则它是一个五元组 那么现在呢它就不再是一个五元组了，它是一个k 嗯k乘以3再加2元这么多个组 也就说它这个，一个是在当前的状态下 每一个读写头都碰到了这个，分别碰到了k 个的这个字符，每一个的字符，然后呢它会转移到一个状态， 然后接下来呢每一个读写头都做重写不同的字符，然后呢每一个读写头 就独立的左移、 右移或者不动，所以呢是Q叉乘上 γ的k次幂，然后呢映射到Q叉乘上γ的k次幂再叉乘上L,R,N的k次幂，这样的 这么一个状态转移函数，那当然，这个k要是很大的话，那么这个 规则一定非常的热闹啊。 那么还有一个就是相对于这个单向 无界，就是说我们原来的纸带呢是模拟这个自然数的。 那么自然数呢都有一个开头，比如从0开始， 0,1,2,3，然后单向，单向无界。 那么原来这个标准的图灵机呢它也是单向无界，它这个 格子呢，它有一个起始的格子，然后另一方面是没有限制的。 那么相对于这个单向无界，那么我们可以做这个双向无界的这个扩展，把这个纸带呢两边 左边也无穷，右边也无穷。 那当然我们其实 我们说不管是k条纸带也好，或者说双向无界也好， 它对于原来的这个单向，单条纸带，单个读写头 单向无限的这种图灵机而言，它其实呢 可以做一个等价的变换，比如说我们可以想象双向无界的这个图灵机， 只要把这个纸带呢，从一个指定的一个格子开始，把它对折一下 诶，那它不就变成单向无界了嘛 所以这个它实际上它是可以相互进行模拟的。 那么这种左边无，右边无限增长，它实际上 把它对折完了以后，就相当于一边是无限增长，这么一个 情况。 这是呢设施进行扩展的图灵机。 第二大类呢，就厉害了，它是非确定性的图灵机，我们在介绍这个计算规则的限制的时候 曾经说过，不能够有两个这个五元组，它的前两个分量相同而后三个不一样。 那那样的话会引起这个规则的不确定，也就是说我当我读写头在这个状态又读到这个字符， 如果你同时叫我做两件事情，我该做哪一样呢？ 那么非确定性的图灵机呢，就是让这个计算规则的前两项可以相同， 然后呢，由机器呢任意选择一个分支来进行。 那么这个任意选择，那么你就可以是，是第一条规则，还是第二条规则，甚至第三条规则， 那么这些规则里头可以任意选一个，那么这里头关键是怎么选的问题。 那当然我们作为具体的解决问题的时候，特别是这个理论上的问题的时候， 这个随机选择它其实并没有说， 我们会涉及到我们解决问题的效率呀，或者说 它会涉及到一些工程上的什么原因。 那么它必然是理论上的原因。 但是呢，非确定 但是也得有一项，有一样东西是确定的。 就是说它的规则呢必须满足一致性，它虽然不满足确定性，但是它要一致。 所谓的一致呢就是说，它禁止这个多个分支，一个分支 导致接受，最终停机接受这个字符串，而另一个分支呢 最终呢会导致拒绝，如果那样的话就称作为不一致 了。 那如果是不一致，那这个，这种非确定型的图灵机也没有什么意义。 是吧，那只是跑着玩而已，所以呢我们要严格 的对有用来说，它必须规则是一致的。 那么我们有这两大类了，一个对设施进行扩展的 图灵机，一个呢是非确定性的这种图灵机。 这个所有的这些图灵机里头，我们最后 呢，人们研究发现，每一个这种变种的图灵机M 实际上都存在着一个单带、 单读写头、 单向 无界的这个图灵机M'而满足L(M)=L(M')， 也就是说它们都能够识别相同的语言， 识别相同的语言，也就是说它们之间的所有的这些变种，不管是 设施增强了很多倍，那么另外一个呢，非确定性的 所有的这些因素加在里头，实际上它们的计算能力都是相同的。 都可以归结到等价的我们的标准的图灵机，也就是确定性的 单纸带的、 单向无界的这些图灵机。
