更改
跳到导航
跳到搜索
第288行:
第288行:
− +
→递归定理
实际上,我们可以把上述代码总结成计算理论、递归函数论中重要的数学定理:递归定理(可以参看《[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>。
有了这样一种表示方法,递归定理就可以表述为:
有了这样一种表示方法,递归定理就可以表述为: