3,094
个编辑
更改
→定理表述
直觉地说，第二条就是"机器在任何时刻只能查看有限多的已有计算结果"——这是"机械可执行"的数学化。[[阶乘]]、[[斐波那契数列]]、以及绝大多数程序语言中的递归定义都满足这两条<ref name="rogers1967" />.
直觉地说，第二条就是"机器在任何时刻只能查看有限多的已有计算结果"——这是"机械可执行"的数学化。[[阶乘]]、[[斐波那契数列]]、以及绝大多数程序语言中的递归定义都满足这两条<ref name="rogers1967" />.
'''第一递归定理'''：设 <math>\Psi</math> 是递归算子，则存在函数 <math>\phi</math> 使得：
# <math>\Psi(\phi) = \phi</math>（<math>\phi</math> 是方程的解，即 <math>\Psi</math> 的不动点）；
# <math>\Psi(\phi) = \phi</math>（<math>\phi</math> 是方程的解，即 <math>\Psi</math> 的不动点）；