更改
跳到导航
跳到搜索
第286行：
第286行： − + − + + − 递归定理（也被称为Kleene第二递归定理）：假设F是任意的计算机程序，那么总存在一个字符串c，使得下列等式成立1：+ + + − 首先，等式的左边是一个计算机程序，这个程序的源代码是c。而等式的右边是另外一个计算机程序，它的源代码是任意函数F对输入变量c进行计算的编码。左边等于右边是说这两个计算机程序虽然源代码不同，但是产生的计算结果却是一模一样的。也就是无论输入给这两个程序的y是什么，c,"F(c)"都会产生完全相同的计算结果。+ − 我们也可以这样来理解递归定理的含义，我们知道c是左边计算机程序的源代码，而F则可以是任意一种对字符串的操作。存在某一个字符串c使得左边等于右边也就意味着存在某个计算机程序C，它可以将自己的源代码（c）进行任意地操作，即F(c)。注意在这里，我故意使用了一种“因果倒置”的解释。实际上，我们知道源代码c控制了整个计算机程序的运作，所以决定程序能将自己的源代码执行任意操作的关键因素就是c本身而并不是F(c)。但是既然c的效果和F(c)的效果是一模一样的，我们也可以把等式右侧的程序看作是起决定作用的原因而非结果，也就是程序可以对自己的源代码c进行任意的摆弄F(c)，这种因果倒置的解释更容易帮助我们认识递归定理中的不平凡性。关于这种因果互换，我们还会在第8节讨论。+ − + − + 第306行：
第309行： − + − 我们人类拥有的自由意识最可贵之处就在于意识可以反作用于自己，并时刻知道自己正在干什么。我们说意识具有自我反省的能力。那么，计算机程序能不能具有自我反省的能力呢？对于常见的程序来说，答案是否定的。然而，如果利用递归定理，我们便能创造出知道“自己正在干什么”的程序（具体关于自反省的程序，可以参看《Computability:anintroductiontorecursivefunctiontheory》一书）。+ − + + + 第318行：
第323行： − + − 冯诺依曼也许是最早地看到递归定理与自然进化之间存在着深刻联系的人。在他的著作《自复制自动机理论（TheoryofSelf-reproducingAutomata）》之中，他专门探讨了由递归定理引起的自复制，以及由小的热力学涨落而作用到自复制过程中，从而可能引起的进化。+ − + − 假如，我们将程序F进行一定的修改，让它不是Construct，而是具有随机扰动的Construct，我们记为F’。F’作用到代码c上的时候，可能不会精确地制作出原始的自复制机器：λ(CopyоConstructоControl)о(CopyоConstructоControl)，而是它的某种变异体。+ − + − + 第335行：
第340行： − + 第348行：
第353行： − 我们已经领教了构建性自指所创造的奇迹，下面我们会乘胜追击，继续领教破坏性自指的威力。在数理逻辑及其计算理论中，人们通常用毁灭性的自指语句（计算机程序或者字符+ − 串），也就是说谎者悖论的变种来证明某种理论的无效性。例如，最早的罗素悖论就是利用集合论的语言构造出了一种特殊的集合悖论：“不包含自己的集合”，从而反过来证明了集合论本身存在缺陷；哥德尔则通过元数学技巧构造了一个特殊的哥德尔句子“本句子在系统中不可证明”从而破灭了希尔伯特的让数学公理系统自身可以保证“完备一致性”的梦想；图灵则构造了一个特殊的程序，反驳了能够判别图灵停机问题的可能性。本小节就利用图灵停机问题和哥德尔定理为例，来说明这种毁灭性的自指是如何工作的。最后，我们将指出存在于这两种不同问题之中的共同特征。+ + − (1)图灵停机问题 第362行：
第367行： + − + − + − + − + − + − + − + − − − − − − − − − + − + 第393行：
第391行： − 我们将一个程序X作用到它自身的源代码x这个特殊的事件编码为”X(x)”，并定义一个叫做蒯恩的计算机程序产生这样的编码，也就是定义：+ − + 第401行：
第399行： − (2) 哥德尔定理+ − 现在让我们进入数理逻辑的领域，去领略另外一个利用破坏性自指进行的完美推理：哥德尔定理（参见：《哥德尔、艾舍尔、巴赫——集异璧之大成》和《哥德尔证明》）。+
无编辑摘要
不难发现，因为F可以任意地定义，所以形如代码4的计算机程序不仅可以将自己的源代码打印出来，而且还能对自己的源代码进行任意地操作F。
不难发现，因为F可以任意地定义，所以形如代码4的计算机程序不仅可以将自己的源代码打印出来，而且还能对自己的源代码进行任意地操作F。
实际上，我们可以把上述代码总结成计算理论、递归函数论中重要的数学定理：递归定理(可以参看《Computability:anintroductiontorecursivefunctiontheory》一书)。在正式写出递归定理之前，我们必须先引入一些记号。我们记c为以c为其源代码的程序，那么如果源代码为c=”x+1”，那么相应的计算机程序就是"x"。注意，区别计算机程序的源代码和计算机程序本身还是很重要的，这是因为源代码仅仅是一个字符串，而程序本身则是将源代码字符串进行编译后的可以完成某种运算的实体。另外，我们记”F(x)”为将程序F作用到数据x这件事的源代码。例如F(x)定义为
实际上，我们可以把上述代码总结成计算理论、递归函数论中重要的数学定理：递归定理(可以参看《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》一书)。在正式写出递归定理之前，我们必须先引入一些记号。
Print(x+1)，那么”F(x)”就是(在屏幕上打印出数字2的程序)的源代码：”Print(1+1)”。
我们记<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，使得下列等式成立<sup>1</sup>：
<math>\phi_c = \phi_{"F(c)"}</math> (1)
首先，等式的左边是一个计算机程序，这个程序的源代码是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节讨论。
实际上，上一节所讲的自打印程序就是这个定理的一个特例。我们不妨设F(c)就是将c原封不动地打印到屏幕上，即Print(c)，那么c"F(c)"的意思就是存在着一个程序c，执行这段c的结果（左边）就是把自己的源程序c打印到了屏幕上（右边）。即：c"Print(c)"，其中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，那么c"Construct(c)"就意味着存在一个程序C，它可以根据自己的源代码再复制出一个程序出来。
同样的道理，自复制的计算机程序也可以从递归定理中推论出来。只要我们令F(c)为根据代码c构造出实际的程序出来的操作Construct，那么<math>\phi_c = \phi_{"Construct(c)"}</math> 就意味着存在一个程序C，它可以根据自己的源代码再复制出一个程序出来。
====未开采的金矿====
====未开采的金矿====
就来简单挖掘一下这个金矿。
就来简单挖掘一下这个金矿。
1、自我反省的程序（Self-introspectiveprogram）
'''1、自我反省的程序（Self-introspective program）'''
我们人类拥有的自由意识最可贵之处就在于意识可以反作用于自己，并时刻知道自己正在干什么。我们说意识具有自我反省的能力。那么，计算机程序能不能具有自我反省的能力呢？对于常见的程序来说，答案是否定的。然而，如果利用递归定理，我们便能创造出知道“自己正在干什么”的程序（具体关于自反省的程序，可以参看《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》一书）。
对于递归定理来说，这几乎就是小菜一碟。因为存在着这样一种计算机程序Ft(x)，它的作用就是计算任意的源代码为x的程序在经过t时间步的运算后的结果以及所有中间状态（例如完成这个计算内存以及寄存器中存储的任何中间数值）。我们知道通用计算程序U（通用图灵机，参见《图灵机与计算理论》或者《Computability:anintroductiontorecursivefunctiontheory》）的工作原理就与这个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)的确是一个可计算的程序。
这里的t可以看作是给定的参数，因此Ft仅仅具有一个自变量，这就是源代码x。于是根据递归定理，我们便知道，存在着一个源程序c使得：
这里的t可以看作是给定的参数，因此Ft仅仅具有一个自变量，这就是源代码x。于是根据递归定理，我们便知道，存在着一个源程序c使得：
<math>\phi_c = \phi_{"F_t(c)"}</math> (2)
即c所对应的程序C所作的事情就是：把自己的源代码拿出来，然后在自己的虚拟机上模拟自己运算t时间步后的结果，以及当时的所有中间状态（包括内存和寄存器中的各个变量的取值）。
即c所对应的程序C所作的事情就是：把自己的源代码拿出来，然后在自己的虚拟机上模拟自己运算t时间步后的结果，以及当时的所有中间状态（包括内存和寄存器中的各个变量的取值）。
既然这个程序C已经清楚地了解到它自己在经过t步运算后的所有结果和中间状态了，那么我们不能说这个程序是自省的吗？所以程序也能做到知道自己正在做什么。
既然这个程序C已经清楚地了解到它自己在经过t步运算后的所有结果和中间状态了，那么我们不能说这个程序是自省的吗？所以程序也能做到知道自己正在做什么。
2、进化
'''2、进化'''
冯诺依曼也许是最早地看到递归定理与自然进化之间存在着深刻联系的人。在他的著作《自复制自动机理论（[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<sub>о</sub> Construct<sub>о</sub> Control)<sub>о</sub> (Copy<sub>о</sub> Construct<sub>о</sub> Control))的源代码c，使得程序运行以后，就能将自身复制。
假如，我们将程序F进行一定的修改，让它不是Construct，而是具有随机扰动的Construct，我们记为F'。F'作用到代码c上的时候，可能不会精确地制作出原始的自复制机器：λ(Copy<sub>о</sub> Construct<sub>о</sub> Control)<sub>о</sub> (Copy<sub>о</sub> Construct<sub>о</sub> Control)，而是它的某种变异体。
如果这个随机变异发生在(CopyоConstructоControl)上面，那么新生成的机器就不再会有生产的功能了，因为我们已经破坏了复制的逻辑。如果变异发生在数据λ(CopyоConstructоControl)上，那么得到的新机器还具有复制的功能，但是复制的不再是它自己，而是某种变异的机器了。进一步，我们可以假设变异的可能性是在λ(CopyоConstructоControl)上面增加了一些无害的数据，例如λ(CopyоConstructоControlоMutation)，那么这段数据会被(CopyоConstructоControl)执行，而形成新的机器：λ(CopyоConstructоControlоMutation)о(CopyоConstructоControlоMutation)。我们看到，这个新机器不仅没有丧失自我复制的能力，还在原来机器的基础上增加了新的功能：Mutation。如果继续运行这个变异的机器，它不仅能够自复制，而且还能将变异出来的新功能Mutation一直保持下去，直到新的变异产生。这不正是大自然的进化吗？
如果这个随机变异发生在(Copy<sub>о</sub> Construct<sub>о</sub> Control)上面，那么新生成的机器就不再会有生产的功能了，因为我们已经破坏了复制的逻辑。如果变异发生在数据λ(Copy<sub>о</sub> Construct<sub>о</sub> Control)上，那么得到的新机器还具有复制的功能，但是复制的不再是它自己，而是某种变异的机器了。进一步，我们可以假设变异的可能性是在λ(Copy<sub>о</sub> Construct<sub>о</sub> Control)上面增加了一些无害的数据，例如λ(Copy<sub>о</sub> Construct<sub>о</sub> Control)，那么这段数据会被(Copy<sub>о</sub> Construct<sub>о</sub> Control)执行，而形成新的机器：λ(Copy<sub>о</sub> Construct<sub>о</sub> Control<sub>о</sub> Mutation)<sub>о</sub> (Copy<sub>о</sub> Construct<sub>о</sub> Control<sub>о</sub> Mutation)。我们看到，这个新机器不仅没有丧失自我复制的能力，还在原来机器的基础上增加了新的功能：Mutation。如果继续运行这个变异的机器，它不仅能够自复制，而且还能将变异出来的新功能Mutation一直保持下去，直到新的变异产生。这不正是大自然的进化吗？
3、无穷上升的虚拟层
'''3、无穷上升的虚拟层'''
在上一章中我们讨论了一种可能性，就是一个计算机程序在接收外界输入的同时能够不停地构建越来越深的虚拟层次，并将自己的拷贝在这些虚拟层中不断地改造、变异。这种改造和变异可能具有非常大的任意性，从而让玩家完全不能分辨出与自己交互的究竟是原来的程序还是一个完全不同的新程序了。所以，他也就不能再分辨自己究竟是玩家还是程序员了。
在上一章中我们讨论了一种可能性，就是一个计算机程序在接收外界输入的同时能够不停地构建越来越深的虚拟层次，并将自己的拷贝在这些虚拟层中不断地改造、变异。这种改造和变异可能具有非常大的任意性，从而让玩家完全不能分辨出与自己交互的究竟是原来的程序还是一个完全不同的新程序了。所以，他也就不能再分辨自己究竟是玩家还是程序员了。
我们可以这样来的定义递归定理中的F：
我们可以这样来的定义递归定理中的F：
F=(AcceptInputоMutationоUniversalComputationоControl)
F=(AcceptInputConstruct<sub>о</sub> MutationоUniversalComputationConstruct<sub>о</sub> Control)
也就是说这个程序F由四个部分组成，第一个部分AcceptInput可以接受外界（玩家）的输入信息；第二个部分Mutation使它可以对源代码数据进行随机变异（仿照可变异的自复制程序）；第三部分UniversalComputation为一个通用计算程序（通用图灵机）；第四部分Control表示为了让计算能够按照指定方式顺利运行而进行的一些控制操作。
也就是说这个程序F由四个部分组成，第一个部分AcceptInput可以接受外界（玩家）的输入信息；第二个部分Mutation使它可以对源代码数据进行随机变异（仿照可变异的自复制程序）；第三部分UniversalComputation为一个通用计算程序（通用图灵机）；第四部分Control表示为了让计算能够按照指定方式顺利运行而进行的一些控制操作。
===破坏性的自指===
===破坏性的自指===
我们已经领教了构建性自指所创造的奇迹，下面我们会乘胜追击，继续领教破坏性自指的威力。在数理逻辑及其计算理论中，人们通常用毁灭性的自指语句（计算机程序或者字符串），也就是说谎者悖论的变种来证明某种理论的无效性。例如，最早的罗素悖论就是利用集合论的语言构造出了一种特殊的集合悖论：“不包含自己的集合”，从而反过来证明了集合论本身存在缺陷；哥德尔则通过元数学技巧构造了一个特殊的哥德尔句子“本句子在系统中不可证明”从而破灭了希尔伯特的让数学公理系统自身可以保证“完备一致性”的梦想；图灵则构造了一个特殊的程序，反驳了能够判别图灵停机问题的可能性。本小节就利用图灵停机问题和哥德尔定理为例，来说明这种毁灭性的自指是如何工作的。最后，我们将指出存在于这两种不同问题之中的共同特征。
====图灵停机问题====
首先，图灵停机问题的背景是来源于下列问题：我们能不能开发一个聪明的程序H，使得该程序可以读入任何一个程序X的源代码x，并判断出当程序X作用到输入字符串y上时
首先，图灵停机问题的背景是来源于下列问题：我们能不能开发一个聪明的程序H，使得该程序可以读入任何一个程序X的源代码x，并判断出当程序X作用到输入字符串y上时
是否会停下来？我们可以形象地把这写程序之间的关系表达为图：
是否会停下来？我们可以形象地把这写程序之间的关系表达为图：
那么，我们就可以根据H构造一个破坏性的程序D，D的定义如下：
那么，我们就可以根据H构造一个破坏性的程序D，D的定义如下：
<pre>
D(z){
D(z){
y=H(z,z);
y=H(z,z);
If y=yes then
Do while true
If y=yes then
Loop
Else
Do while true
return
Endif
Loop
Else
return
Endif
}
}
</pre>
源代码5：破坏停机程序H的程序D
<div style="text-align: center;">源代码5：破坏停机程序H的程序D</div>
我们来分析一下D，它有一个输入参数z。D首先会调用H这个函数，并让H判断当源代码为z的程序Z作用到它自己源程序的字符串上是否会停下来。如果H(z,z)的返回为Yes，
我们来分析一下D，它有一个输入参数z。D首先会调用H这个函数，并让H判断当源代码为z的程序Z作用到它自己源程序的字符串上是否会停下来。如果H(z,z)的返回为Yes，
让我们再回过头来分析一下D这个函数，它其实包含了两部分，第一部分是计算H(z,z)的结果，也就是判断将函数Z作用到它自身的源代码z上的时候，即Z(z)是否会停机。如果
让我们再回过头来分析一下D这个函数，它其实包含了两部分，第一部分是计算H(z,z)的结果，也就是判断将函数Z作用到它自身的源代码z上的时候，即Z(z)是否会停机。如果
我们将一个程序X作用到它自身的源代码x这个特殊的事件编码为"X(x)"，并定义一个叫做蒯恩的计算机程序产生这样的编码，也就是定义：
Q(x):=”X(x)”;
<math>Q(x):="X(x)"</math>;
那么，最终的判断H(z,z)又可以写成：H(Q(z))。所以实际上，D程序的第一部分就是将判断停机的函数H和蒯恩函数Q放到一起并同时作用到代码z上面。
那么，最终的判断H(z,z)又可以写成：H(Q(z))。所以实际上，D程序的第一部分就是将判断停机的函数H和蒯恩函数Q放到一起并同时作用到代码z上面。
程序的第二部分则是一个取反的操作，也就是如果H(z,z)判断为yes，程序就进入死循环，如果判断为no，程序就退出。而在证明的最后一步，将D作用到它的源代码d上面会产生什么情景？这个D(d)的操作恰恰能够实现自指悖论。有关图灵停机问题的详细解释请参看：图灵机与计算理论。我们将在下一小节看出这些自指技术的共同之处。
程序的第二部分则是一个取反的操作，也就是如果H(z,z)判断为yes，程序就进入死循环，如果判断为no，程序就退出。而在证明的最后一步，将D作用到它的源代码d上面会产生什么情景？这个D(d)的操作恰恰能够实现自指悖论。有关图灵停机问题的详细解释请参看：图灵机与计算理论。我们将在下一小节看出这些自指技术的共同之处。
====哥德尔定理====
现在让我们进入数理逻辑的领域，去领略另外一个利用破坏性自指进行的完美推理：哥德尔定理（参见：《[https://book.douban.com/subject/1291204/ 哥德尔、艾舍尔、巴赫——集异璧之大成]》和《[https://book.douban.com/subject/3029210/ 哥德尔证明]》）。
首先，我们需要简单介绍一下哥德尔定理的背景。哥德尔定理所讨论的对象是关于自然数的一套公理系统。此公理系统是由关于自然数性质的命题构成的（我们可以把这些命题简单地理解为一些合法的字符串）。例如：
首先，我们需要简单介绍一下哥德尔定理的背景。哥德尔定理所讨论的对象是关于自然数的一套公理系统。此公理系统是由关于自然数性质的命题构成的（我们可以把这些命题简单地理解为一些合法的字符串）。例如：