格格党

手机浏览器扫描二维码访问

第一百四十四章 图灵完备100％（第1页）

卢赫：“什么叫自动机？“艾达否：“自动机就是对信号序列进行判定的数学模型。

我嘴里的自动机特质有限状态机，当这个机处于某种状态时，它会读到相应的信号，根据转移函数跳到下一个状态，可以视作一台没有内存结构的计算机。

比如你现在饿了，那你就要去食堂，把晶莹饱满、粘糯有较劲、香到不可思议的新米饭一勺一勺填进嘴里，直到胃被塞满。

饥饿感是信号，饿了要吃饭是状态，去食堂是转移函数，饱是执行完转移函数之后的新状态。

你每时每刻都在处理各种各样的状态，直到停机，或者说死掉。”

卢赫：“那什么叫图灵完备？”

艾达否：“能模拟图灵机的自动机称作图灵完备。”

卢赫：“什么叫图灵机？”

艾达否：“一个可以执行任何算法的简单模型。

它有一个无限长的纸带，纸带被分成一个个相邻的格子，每个格子都可以写上至多一个字符；它还有一个读写头，可以读取、擦除、写入当前格子的内容，也可以每次向左或向右移动一个格子；它有一个字符表，包含纸带上可能出现的所有字符；它还要有一个状态寄存器，追踪每一步计算过程机器所处的状态直到停机；它还可以包含一个指令集，用来指定读写头的行为，比如你告诉读写头：当你身处编号53的格子并看到其内容为0时，擦除，改写为1，并向右移一格。

此外，令下一状态为运行。

举个栗子，如果它的字符集只包含0、1和空白，那么它就是一个包含3个信号的图灵机。

如果它的纸带上写了个110，那么你可以让它执行一系列的指令执行位反转算法，把110改写成001。

比如：指针遇0写入1纸带右移，遇1写入0纸带右移。

那你要问了，如果指针遇到空字符呢？你没有告诉它遇到空字符怎么做，所以它只会不断读取空字符，但不操作。

这个时候你可以给它加一个状态指令：遇到空字符就停机，它就可以完美执行你的位反算法。

它现在可以被视为一个包含3个信号和1个状态的有限状态机。

如果你吃饱了撑着没事干，想要把它设计得复杂一些，比如想让它一做完位反转运算就复原，把110变成001后再复原成110。

那么你给它两个状态：当读写头在向右移动的过程中读到空字符时，改为向左移动；当读写头在向左移动的过程中遇到空字符时，停机。

这是一个包含3个信号和2个状态的有限状态机。

只要你给它添加足够多的状态，并把这个假想模型物理实现，就能够让它执行一切复杂算法，只要这个算法是可计算的。”

卢赫：“你在这里做了限定，只能执行可计算的算法。”

艾达否：“没错，它只能解决可计算的问题。

你可以给它一个正整数n，让它判断n是否是质数，但不能问它今天中午食堂会有什么饭。

你可以给它一个逻辑蕴含的命题，要求它求出逆否命题，但不能包含悖论，比如理发师给并且只给那些不给自己理发的人理发，那他给不给自己理发？”

卢赫：“这么简单的结构，对于复杂算法它是如何算的呢？”

艾达否：“它算起来也很简单。

三种基本函数：零函数、后继函数、投影函数，外加三种基本操作：函数组合、原始函数递归以及极小化，就能够解决一切可计算问题[1]。”

卢赫：“……我换个我能听懂的问题吧，怎样判断一个语言是图灵完备的？”