更改
跳到导航
跳到搜索
第288行：
第288行： − + 第294行：
第294行： − + − + − + − +
→递归定理
实际上，我们可以把上述代码总结成计算理论、递归函数论中重要的数学定理：递归定理(可以参看《[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，使得下列等式成立<sup>1</sup>：
'''递归定理'''（也被称为Kleene第二递归定理）：假设F是任意的计算机程序，那么总存在一个字符串c，使得下列等式成立<sup>1</sup>：
<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，它可以根据自己的源代码再复制出一个程序出来。
====未开采的金矿====
====未开采的金矿====