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

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

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

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

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

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

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

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

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

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

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

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

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

艾达否：“有。从基因突变到