更改

注意，加粗的代码部分就是在上一个代码的基础上添加的。这样，此程序不仅包含了S(x)，而且还包含了一个附加的程序F(x)的定义，并且这个附加函数F(x)的源代码也需要被包含到之前F()之中和q的赋值语句之中。运行这个程序，它就会在屏幕上打印出自己源代码的长度。

注意，加粗的代码部分就是在上一个代码的基础上添加的。这样，此程序不仅包含了S(x)，而且还包含了一个附加的程序F(x)的定义，并且这个附加函数F(x)的源代码也需要被包含到之前F()之中和q的赋值语句之中。运行这个程序，它就会在屏幕上打印出自己源代码的长度。

也就是说源代码4这段代码实现了如下的功能：Print(length(c))，其中c就是源代码4。按照同样的方法，我们可以在自打印程序后面附加任意复杂的程序F，只要在相应的位置添加更长的字符串就行了。

也就是说源代码4这段代码实现了如下的功能：Print(length(c))，其中c就是源代码4。按照同样的方法，我们可以在自打印程序后面附加任意复杂的程序F，只要在相应的位置添加更长的字符串就行了。

不难发现，因为F可以任意地定义，所以形如代码4的计算机程序不仅可以将自己的源代码打印出来，而且还能对自己的源代码进行任意地操作F。

不难发现，因为F可以任意地定义，所以形如代码4的计算机程序不仅可以将自己的源代码打印出来，而且还能对自己的源代码进行任意地操作F。

实际上，我们可以把上述代码总结成计算理论、递归函数论中重要的数学定理：递归定理(可以参看《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》一书)。在正式写出递归定理之前，我们必须先引入一些记号。

实际上，我们可以把上述代码总结成计算理论、递归函数论中重要的数学定理：递归定理(可以参看《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》一书)。在正式写出递归定理之前，我们必须先引入一些记号。

我们记<math>\phi_c</math>为以<math>c</math>为其源代码的程序，那么如果源代码为<math>c=''x+1''</math>，那么相应的计算机程序就是<math>\phi_{''x+1''}</math>。注意，区别计算机程序的源代码和计算机程序本身还是很重要的，这是因为源代码仅仅是一个字符串，而程序本身则是将源代码字符串进行编译后的可以完成某种运算的实体。另外，我们记<math>''F(x)''</math>为将程序<math>F</math>作用到数据<math>x</math>这件事的源代码。例如<math>F(x)</math>定义为<math>Print(x+1)</math>，那么<math>''F(x)''</math>就是(在屏幕上打印出数字2的程序)的源代码：<math>''Print(1+1)''</math>。

我们记<math>\phi_c</math>为以<math>c</math>为其源代码的程序，那么如果源代码为<math>c=''x+1''</math>，那么相应的计算机程序就是<math>\phi_{''x+1''}</math>。注意，区别计算机程序的源代码和计算机程序本身还是很重要的，这是因为源代码仅仅是一个字符串，而程序本身则是将源代码字符串进行编译后的可以完成某种运算的实体。另外，我们记<math>''F(x)''</math>为将程序<math>F</math>作用到数据<math>x</math>这件事的源代码。例如<math>F(x)</math>定义为<math>Print(x+1)</math>，那么<math>''F(x)''</math>就是(在屏幕上打印出数字2的程序)的源代码：<math>''Print(1+1)''</math>。

有了这样一种表示方法，递归定理就可以表述为：

有了这样一种表示方法，递归定理就可以表述为：

'''递归定理'''（也被称为Kleene第二递归定理）：假设F是任意的计算机程序，那么总存在一个字符串c，使得下列等式成立¹：

'''递归定理'''（也被称为Kleene第二递归定理）：假设F是任意的计算机程序，那么总存在一个字符串c，使得下列等式成立¹：

<math>\phi_c = \phi_{''F(c)''}</math>            (1)

<math>\phi_c = \phi_{''F(c)''}</math>            (1)

首先，等式的左边是一个计算机程序，这个程序的源代码是c。而等式的右边是另外一个计算机程序，它的源代码是任意函数F对输入变量c进行计算的编码。左边等于右边是说这两个计算机程序虽然源代码不同，但是产生的计算结果却是一模一样的。也就是无论输入给这两个程序的y是什么，<math>\phi_c</math>，<math>\phi_{''F(c)''}</math>都会产生完全相同的计算结果。

首先，等式的左边是一个计算机程序，这个程序的源代码是c。而等式的右边是另外一个计算机程序，它的源代码是任意函数F对输入变量c进行计算的编码。左边等于右边是说这两个计算机程序虽然源代码不同，但是产生的计算结果却是一模一样的。也就是无论输入给这两个程序的y是什么，<math>\phi_c</math>，<math>\phi_{''F(c)''}</math>都会产生完全相同的计算结果。

我们也可以这样来理解递归定理的含义，我们知道c是左边计算机程序的源代码，而F则可以是任意一种对字符串的操作。存在某一个字符串c使得左边等于右边也就意味着'''存在某个计算机程序C，它可以将自己的源代码（c）进行任意地操作，即F(c)'''。注意在这里，我故意使用了一种“因果倒置”的解释。实际上，我们知道源代码c控制了整个计算机程序的运作，所以决定程序能将自己的源代码执行任意操作的关键因素就是c本身而并不是F(c)。但是既然c的效果和F(c)的效果是一模一样的，我们也可以把等式右侧的程序看作是起决定作用的原因而非结果，也就是程序可以对自己的源代码c进行任意的摆弄F(c)，这种因果倒置的解释更容易帮助我们认识递归定理中的不平凡性。关于这种因果互换，我们还会在第8节讨论。

我们也可以这样来理解递归定理的含义，我们知道c是左边计算机程序的源代码，而F则可以是任意一种对字符串的操作。存在某一个字符串c使得左边等于右边也就意味着'''存在某个计算机程序C，它可以将自己的源代码（c）进行任意地操作，即F(c)'''。注意在这里，我故意使用了一种“因果倒置”的解释。实际上，我们知道源代码c控制了整个计算机程序的运作，所以决定程序能将自己的源代码执行任意操作的关键因素就是c本身而并不是F(c)。但是既然c的效果和F(c)的效果是一模一样的，我们也可以把等式右侧的程序看作是起决定作用的原因而非结果，也就是程序可以对自己的源代码c进行任意的摆弄F(c)，这种因果倒置的解释更容易帮助我们认识递归定理中的不平凡性。关于这种因果互换，我们还会在第8节讨论。

实际上，上一节所讲的自打印程序就是这个定理的一个特例。我们不妨设F(c)就是将c原封不动地打印到屏幕上，即Print(c)，那么<math>\phi_c = \phi_{''F(c)''}</math> 的意思就是存在着一个程序c，执行这段c的结果（左边）就是把自己的源程序c打印到了屏幕上（右边）。即：<math>\phi_c = \phi_{''Print(c)''}</math> ，其中c就是上节代码1给出的自打印程序的源代码S(x)。

实际上，上一节所讲的自打印程序就是这个定理的一个特例。我们不妨设F(c)就是将c原封不动地打印到屏幕上，即Print(c)，那么<math>\phi_c = \phi_{''F(c)''}</math> 的意思就是存在着一个程序c，执行这段c的结果（左边）就是把自己的源程序c打印到了屏幕上（右边）。即：<math>\phi_c = \phi_{''Print(c)''}</math> ，其中c就是上节代码1给出的自打印程序的源代码S(x)。

同样的道理，自复制的计算机程序也可以从递归定理中推论出来。只要我们令F(c)为根据代码c构造出实际的程序出来的操作Construct，那么<math>\phi_c = \phi_{''Construct(c)''}</math> 就意味着存在一个程序C，它可以根据自己的源代码再复制出一个程序出来。

同样的道理，自复制的计算机程序也可以从递归定理中推论出来。只要我们令F(c)为根据代码c构造出实际的程序出来的操作Construct，那么<math>\phi_c = \phi_{''Construct(c)''}</math> 就意味着存在一个程序C，它可以根据自己的源代码再复制出一个程序出来。

我们人类拥有的自由意识最可贵之处就在于意识可以反作用于自己，并时刻知道自己正在干什么。我们说意识具有自我反省的能力。那么，计算机程序能不能具有自我反省的能力呢？对于常见的程序来说，答案是否定的。然而，如果利用递归定理，我们便能创造出知道“自己正在干什么”的程序（具体关于自反省的程序，可以参看《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》一书）。

我们人类拥有的自由意识最可贵之处就在于意识可以反作用于自己，并时刻知道自己正在干什么。我们说意识具有自我反省的能力。那么，计算机程序能不能具有自我反省的能力呢？对于常见的程序来说，答案是否定的。然而，如果利用递归定理，我们便能创造出知道“自己正在干什么”的程序（具体关于自反省的程序，可以参看《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》一书）。

对于递归定理来说，这几乎就是小菜一碟。因为存在着这样一种计算机程序Ft(x)，它的作用就是计算任意的源代码为x的程序在经过t时间步的运算后的结果以及所有中间状态（例如完成这个计算内存以及寄存器中存储的任何中间数值）。我们知道通用计算程序U（通用图灵机，参见《[[图灵机与计算理论|图灵机与计算理论]]》或者《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》）的工作原理就与这个Ft(x)类似，因为U可以模拟任意的程序X作用到任意的数据y上的结果。所以，Ft(x)的确是一个可计算的程序。

对于递归定理来说，这几乎就是小菜一碟。因为存在着这样一种计算机程序Ft(x)，它的作用就是计算任意的源代码为x的程序在经过t时间步的运算后的结果以及所有中间状态（例如完成这个计算内存以及寄存器中存储的任何中间数值）。我们知道通用计算程序U（通用图灵机，参见《[[图灵机与计算理论|图灵机与计算理论]]》或者《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》）的工作原理就与这个Ft(x)类似，因为U可以模拟任意的程序X作用到任意的数据y上的结果。所以，Ft(x)的确是一个可计算的程序。

<math>\phi_c = \phi_{''F_t(c)''}</math>            (2)

<math>\phi_c = \phi_{''F_t(c)''}</math>            (2)

即c所对应的程序C所作的事情就是：把自己的源代码拿出来，然后在自己的虚拟机上模拟自己运算t时间步后的结果，以及当时的所有中间状态（包括内存和寄存器中的各个变量的取值）。

即c所对应的程序C所作的事情就是：把自己的源代码拿出来，然后在自己的虚拟机上模拟自己运算t时间步后的结果，以及当时的所有中间状态（包括内存和寄存器中的各个变量的取值）。

既然这个程序C已经清楚地了解到它自己在经过t步运算后的所有结果和中间状态了，那么我们不能说这个程序是自省的吗？所以程序也能做到知道自己正在做什么。

既然这个程序C已经清楚地了解到它自己在经过t步运算后的所有结果和中间状态了，那么我们不能说这个程序是自省的吗？所以程序也能做到知道自己正在做什么。

冯诺依曼也许是最早地看到递归定理与自然进化之间存在着深刻联系的人。在他的著作《自复制自动机理论（[https://book.douban.com/subject/2982694/ Theory of Self-reproducing Automata]）》之中，他专门探讨了由递归定理引起的自复制，以及由小的热力学涨落而作用到自复制过程中，从而可能引起的进化。

冯诺依曼也许是最早地看到递归定理与自然进化之间存在着深刻联系的人。在他的著作《自复制自动机理论（[https://book.douban.com/subject/2982694/ Theory of Self-reproducing Automata]）》之中，他专门探讨了由递归定理引起的自复制，以及由小的热力学涨落而作用到自复制过程中，从而可能引起的进化。

如果我们将递归定理中的程序F定义为函数Construct，即根据源代码x，构造出相应的机器Construct(x)出来，那么应用递归定理，就可以得到一个可以进行自我复制机器的源代码：λ(λ(Copy_о Construct_о Control)_о (Copy_о Construct_о Control))的源代码c，使得程序运行以后，就能将自身复制。

如果我们将递归定理中的程序F定义为函数Construct，即根据源代码x，构造出相应的机器Construct(x)出来，那么应用递归定理，就可以得到一个可以进行自我复制机器的源代码：λ(λ(Copy_о Construct_о Control)_о (Copy_о Construct_о Control))的源代码c，使得程序运行以后，就能将自身复制。

假如，我们将程序F进行一定的修改，让它不是Construct，而是具有随机扰动的Construct，我们记为F'。F'作用到代码c上的时候，可能不会精确地制作出原始的自复制机器：λ(Copy_о Construct_о Control)_о (Copy_о Construct_о Control)，而是它的某种变异体。

假如，我们将程序F进行一定的修改，让它不是Construct，而是具有随机扰动的Construct，我们记为F'。F'作用到代码c上的时候，可能不会精确地制作出原始的自复制机器：λ(Copy_о Construct_о Control)_о (Copy_о Construct_о Control)，而是它的某种变异体。

如果这个随机变异发生在(Copy_о Construct_о Control)上面，那么新生成的机器就不再会有生产的功能了，因为我们已经破坏了复制的逻辑。如果变异发生在数据λ(Copy_о Construct_о Control)上，那么得到的新机器还具有复制的功能，但是复制的不再是它自己，而是某种变异的机器了。进一步，我们可以假设变异的可能性是在λ(Copy_о Construct_о Control)上面增加了一些无害的数据，例如λ(Copy_о Construct_о Control)，那么这段数据会被(Copy_о Construct_о Control)执行，而形成新的机器：λ(Copy_о Construct_о Control_о Mutation)_о (Copy_о Construct_о Control_о Mutation)。我们看到，这个新机器不仅没有丧失自我复制的能力，还在原来机器的基础上增加了新的功能：Mutation。如果继续运行这个变异的机器，它不仅能够自复制，而且还能将变异出来的新功能Mutation一直保持下去，直到新的变异产生。这不正是大自然的进化吗？

如果这个随机变异发生在(Copy_о Construct_о Control)上面，那么新生成的机器就不再会有生产的功能了，因为我们已经破坏了复制的逻辑。如果变异发生在数据λ(Copy_о Construct_о Control)上，那么得到的新机器还具有复制的功能，但是复制的不再是它自己，而是某种变异的机器了。进一步，我们可以假设变异的可能性是在λ(Copy_о Construct_о Control)上面增加了一些无害的数据，例如λ(Copy_о Construct_о Control)，那么这段数据会被(Copy_о Construct_о Control)执行，而形成新的机器：λ(Copy_о Construct_о Control_о Mutation)_о (Copy_о Construct_о Control_о Mutation)。我们看到，这个新机器不仅没有丧失自我复制的能力，还在原来机器的基础上增加了新的功能：Mutation。如果继续运行这个变异的机器，它不仅能够自复制，而且还能将变异出来的新功能Mutation一直保持下去，直到新的变异产生。这不正是大自然的进化吗？

=====无穷上升的虚拟层=====

=====无穷上升的虚拟层=====

在上一章中我们讨论了一种可能性，就是一个计算机程序在接收外界输入的同时能够不停地构建越来越深的虚拟层次，并将自己的拷贝在这些虚拟层中不断地改造、变异。这种改造和变异可能具有非常大的任意性，从而让玩家完全不能分辨出与自己交互的究竟是原来的程序还是一个完全不同的新程序了。所以，他也就不能再分辨自己究竟是玩家还是程序员了。

在上一章中我们讨论了一种可能性，就是一个计算机程序在接收外界输入的同时能够不停地构建越来越深的虚拟层次，并将自己的拷贝在这些虚拟层中不断地改造、变异。这种改造和变异可能具有非常大的任意性，从而让玩家完全不能分辨出与自己交互的究竟是原来的程序还是一个完全不同的新程序了。所以，他也就不能再分辨自己究竟是玩家还是程序员了。

也许在读上一章的时候你还对此类怪异的程序将信将疑，但是有了递归定理，我们便会看到能够产生无穷多个虚拟层，并能在每个虚拟层保持自身，同时还能根据玩家的输入而变异的程序的确是可能的。

也许在读上一章的时候你还对此类怪异的程序将信将疑，但是有了递归定理，我们便会看到能够产生无穷多个虚拟层，并能在每个虚拟层保持自身，同时还能根据玩家的输入而变异的程序的确是可能的。

我们可以这样来的定义递归定理中的F：

我们可以这样来的定义递归定理中的F：

F=(AcceptInputConstruct_о MutationоUniversalComputationConstruct_о Control)

F=(AcceptInputConstruct_о MutationоUniversalComputationConstruct_о Control)

也就是说这个程序F由四个部分组成，第一个部分AcceptInput可以接受外界（玩家）的输入信息；第二个部分Mutation使它可以对源代码数据进行随机变异（仿照可变异的自复制程序）；第三部分UniversalComputation为一个通用计算程序（通用图灵机）；第四部分Control表示为了让计算能够按照指定方式顺利运行而进行的一些控制操作。

也就是说这个程序F由四个部分组成，第一个部分AcceptInput可以接受外界（玩家）的输入信息；第二个部分Mutation使它可以对源代码数据进行随机变异（仿照可变异的自复制程序）；第三部分UniversalComputation为一个通用计算程序（通用图灵机）；第四部分Control表示为了让计算能够按照指定方式顺利运行而进行的一些控制操作。

我们看到，这个程序就能完成我们所要求的功能。首先，根据递归定理，存在着某个源程序c，使得程序C运行起来之后，它的效果等价于F这个函数作用到它自己的源代码c

我们看到，这个程序就能完成我们所要求的功能。首先，根据递归定理，存在着某个源程序c，使得程序C运行起来之后，它的效果等价于F这个函数作用到它自己的源代码c

上面的结果。

上面的结果。

F将怎样作用于c呢？首先，F会调用通用计算UniversalComputation部分在运行中模拟它自己的源代码c。这也就是说程序将自己的一份源代码拷贝放置到了更深一层次的虚拟机上。同时，在每一层运行的时候，F都可以调用Mutation和AcceptInput等程序，这样系统就可以在接受玩家输入的同时不断地更改自己的源程序，从而使得输入者既是玩家又是程序员了。

F将怎样作用于c呢？首先，F会调用通用计算UniversalComputation部分在运行中模拟它自己的源代码c。这也就是说程序将自己的一份源代码拷贝放置到了更深一层次的虚拟机上。同时，在每一层运行的时候，F都可以调用Mutation和AcceptInput等程序，这样系统就可以在接受玩家输入的同时不断地更改自己的源程序，从而使得输入者既是玩家又是程序员了。

总之，一旦程序可以掌握了自己的源代码，它便可以做更多的事情，而且这些事情大部分都是“自”（Self）字打头的，例如自我修复、自我调控等等。所以，递归定理可以为程序赋予真正的自我。

总之，一旦程序可以掌握了自己的源代码，它便可以做更多的事情，而且这些事情大部分都是“自”（Self）字打头的，例如自我修复、自我调控等等。所以，递归定理可以为程序赋予真正的自我。