递归定理


什么是递归定理?

   

在百度和维基百科中都没有关于递归定理的定义,都有在关于递归的定义:

  • 百度百科:程序调用自身的编程技巧称为递归。
  • 维基百科:在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。

在英文的Wikipedia里面取得是后者的意思,即如图所示的例子。


递归是一件很神奇的事情,这里有一个关于生命的悖论,是关于制造一个机器,这个机器能够复制它自已:悖论的主要叙述如下:

  1. 生物是基种意义上的机器,是通过有机体构成的,通过输入能量进行运转的整体。
  2. 生物能够通过各种手段进行自我繁殖和再生。
  3. 机器不能够自我繁复和再生。

这个悖论在于第三点:我们考察一个制造机器的机器,例如工厂里面的汽车自动生产线,原料或半成器从输入以后,自动生产线根据指令进行运行,完整汽车从另一端出来。一般来说,生产线肯定要比它制造的机器要更复杂,因为生产线除了包含汽车的设计以外,还有关于它自已本身的设计。因此它比汽车本身的设计要复杂,包含的内容要更多,因此生产线要比汽车要复杂,直觉上我们是不太可能制造一台汽车,这台汽车能够自身成为生产线,然后再制造更多的汽车和生产线,这就是第三点的意义。

但是如果把这个机器换成生物体的话,实际上第三点是错误的,制造能够生产自已的机器人是可能的。

递归定理 就是要说明如何做到这一点。