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

卢赫：“什么叫自动机？“

艾达否：“自动机就是对信号序列进行判定的数学模型。我嘴里的自动机特质有限状态机，当这个机处于某种状态时，它会读到相应的信号，根据转移函数跳到下一个状态，可以视作一台没有内存结构的计算机。

比如你现在饿了，那你就要去食堂，把晶莹饱满、粘糯有较劲、香到不可思议的新米饭一勺一勺填进嘴里，直到胃被塞满。饥饿感是信号，饿了要吃饭是状态，去食堂是转移函数，饱是执行完转移函数之后的新状态。

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

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

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

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

艾达否：“一个可以执行任何算法的简单模型。它有一个无限长的纸带，纸带被分成一个个相邻的格子，每个格子都可以写上至多一个字符；它还有一个读写头，可以读取、擦除、写入当前格子的内容，也可以每次向左或向右移动一个格子；它有一个字符表，包含纸带上可能出现的所有字符；

它还要有一个状态寄存器，追踪每一步计算过程机器所处的状态直到停机；它还可以包含一个指令集，用来指定读写头的行为，比如你告诉读写头：当你身处编号53的格子并看到其内容为0时，擦除，改写为1，并向右移一格。此外，令下一状态为运行。

举个栗子，如果它的字符集只包含0、1和空白，那么它就是一个包含3个信号的图灵机。如果它的纸带上写了个110，那么你可以让它执行一系列的指令执行位反转算法，把110改写成001。比如：指针遇0写入1纸带右移，遇1写入0纸带右移。

那你要问了，如果指针遇到空字符呢？

你没有告诉它遇到空字符怎么做，所以它只会不断读取空字符，但不操作。这个时候你可以给它加一个状态指令：遇到空字符就停机，它就可以完美执行你的位反算法。它现在可以被视为一个包含3个信号和1个状态的有限状态机。

如果你吃饱了撑着没事干，想要把它设计得复杂一些，比如想让它一做完位反转运算就复原，把110变成001后再复原成110。那么你给它两个状态：当读写头在向右移动的过程中读到空字符时，改为向左移动；当读写头在向左移动的过程中遇到空字符时，停机。这是一个包含3个信号和2个状态的有限状态机.。

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

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

艾达否：“没错，它只能解决可计算的问题。你可以给它一个正整数 n，让它判断n是否是质数，但不能问它今天中午食堂会有什么饭。你可以给它一个逻辑蕴含的命题，要求它求出逆否命题，但不能包含悖论，比如理发师给并且只给那些不给自己理发的人理发，那他给不给自己理发？”

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

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

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

艾达否：“如果一个语言能够实现上述的三种基本函数和基本操作，并且能够据此实现偏递归函数，那么它就是图灵完备的。”

卢赫：“为什么这么说？”

艾达否：“因为只有能实现偏递归，才能够实现无限循环，在没收到停机指令时，永远运行下去[2]。能够实现递归和无限循环是图灵完备的必要条件。”

卢赫：“……我再换一个问题，你凭什么说基因组语言是图灵完备的？”

艾达否：“递归你知道吧，首先是把复杂问题拆解为一系列子问题，直到最低层级的子问题太过简单以至于无法拆分，这是'递'。接下来，一旦最低层级的子问题被解决，上一层的子问题也就解决了，直到最顶层的复杂问题，这是'归'。

复杂问题：要人快快死。最低层级的子问题：基因上要有接口或者被胡乱编辑。某一天，接口来了，最低层子问题被解决，人自然很快就死了。这个过程也许无法用确切的函数来描述，但我愿称之为广义递归。”

卢赫：“让人死有那么难吗？怎么就死得快就是递归了？”

艾达否：“有。从基因突变到第一个癌细胞产生，再到瘤子大到可以被ct扫描出来，平均时间是15年。死很容易，但无外力影响的时候，单靠体内循环死怎样死得这么快，是一个很复杂的问题。”

卢赫：“我假装认为你说得对，但你要告诉我，为什么这个复杂问题非得是“死”？就不能是活吗？对于生命体而言，活才是本能吧？”

艾达否：“你知道为什么常见的碱基是4种吗？2、6、8、10……？”

卢赫：“你继续。”

艾达否：“根据遗传信息可复制性要求，碱基数N必须为偶数，N\/2为嘌呤型，N\/2为嘧啶型。简化假设单碱基突变是主要突变形式，但碱基突变造成错对，错对有转换，比如A变c，和癫换，比如A变G两种形式，它们发生的机率也不同。

假设a、b分别为两种错对的突变常数，K为一个密码子内的碱基数，可以给出突变总频率m：

m=aK(N\/2-1)+bK(N\/2-1)

当N为2时，m为0，没有突变就完全没有进化，不符合现实，排除。

当N为4时，m为K(a+b)。N越大，m越大。

为什么生命体里总是存在基因修复机制？因为它要稳定，不能被奇奇怪怪的突变给搞死。要稳定，碱基就不能有那么多，好几十亿年了，常用碱基还是4个，因为这样最稳定。”

卢赫：“所以呢？生命要稳定，要活，那为什么遇到大幅编辑，不是努力修复，而是想尽办法快点死？”

艾达否：“修复速度和能力是有限的，遭难的快点死绝，没遭难的就能继续活。我们每个个体都是一个复杂系统，组合起来的群体也是一个复杂系统。有句话我觉得很有道理：一切有死之物都希望通过生育繁衍这个唯一可能的方式达到永生，个体永生不了，但群体可以。”

卢赫：“我不明白。群体怎样判断出大幅编辑的个体不利于群体的延续的？且不说群体智慧究竟是否在生物种群中存在，这群体怎么就这么自信？”

艾达否：“因为它知道。也许是死是活是一个可计算的问题，它提前算出来了。”

卢赫：“？？”

艾达否：“也许，它是一台非确定图灵机吧。”

卢赫：“？？？”

艾达否：“理论上，它与标准图灵机计算能力相同，但不同的是，它拥有两个转移函数，每一步计算可以选择两个转移函数中的任何一个。它的每一步计算，就相当于是将一个线程分成了两个，两个不同的转移函数选择各自对应一个子线程。

依据这种结构，有时候一个看起来不知道可否计算的问题，可以被它轻松解决。比如，判定一个数独的题目是否合法。它只要在每一个分支上填不同答案，看看是否有其中一个分支的答案合法就好了。

对于一个规模为n^2的数独来说，每一条分支的时间复杂度是o(n^2)，所以我可以说判定一个数独是否合法，这对于非确定图灵机来说，是一个Np完全问题。

Np完全问题的另一种定义是能被非确定图灵机计算的问题。”

卢赫：“照你这么说，生命体智慧宇宙最强，那我们还造什么高性能计算机？只要是可计算的问题，自己悟悟总能悟出来？”

艾达否：“这不矛盾。计算机是生命体造的，是一个复杂问题的子问题而已，只是有点舍本逐莫了。总之，我的想法是，物种进化等于基因突变加自然选择，现在只有基因突变但没有自然环境压力，群体却依然做出了如此决绝的选择，一定有重要原因在里面，我们应该相信自己给出的这个最优解。”

卢赫：“先不管你的理论靠不靠谱，你的意思是，基因编辑行不通，一大幅编辑就早晚几代人一起死，接口更跟个毒药一样，一沾上就是慢性中毒。明知道那屎山代码里有bug却什么都做不了，眼见着人被折磨？”

凌晨4点半的一切都令人讨厌，不论是咕咕叫的肚子，还是艾达否牛啤哄哄却没有任何应用价值的理论。卢赫的心完全冷了下来。

可对面的人依然神采奕奕的，“你怎么这么死板呢？大幅编辑行不通可以小幅编辑，找到靠谱的界限就行了。接口拿去祸害经济物种，别往自己身上用。

而且，人辛苦进化到生态位最顶端，被自然奴役了几十万年终于可以奴役一下自然了，为什么要对自己动刀子？

在体外使用基因组语言，服务于科技的方方面面，它不香吗？”

—————————————

[1-2]见下章