3,094
个编辑
更改
→从"递归定义的函数"说起
: <math>\phi = \Psi(\phi)</math>
: <math>\phi = \Psi(\phi)</math>
其中 '''<math>\Psi</math> 是一个"函数变换规则"'''（输入一个函数 <math>\phi</math>，输出一个新函数 <math>\Psi(\phi)</math>；术语叫'''[[算子]]'''，operator）。例如阶乘定义对应的 <math>\Psi</math> 是：给定任意函数 <math>\phi</math>，输出新函数 <math>\phi'</math>，其中 <math>\phi'(0) = 1</math>，<math>\phi'(n) = n\cdot\phi(n−1)</math>。
其中 '''<math>\Psi</math> 是一个"函数变换规则"'''（输入一个函数 <math>\phi</math>，输出一个新函数 <math>\Psi(\phi)</math>；术语叫'''[[算子]]'''，operator）。例如阶乘定义对应的 <math>\Psi</math> 是：给定任意函数 <math>\phi</math>，输出新函数 <math>\phi'</math>，其中 <math>\phi'(0) = 1</math>，
: <math>\phi'(n) = n\cdot\phi(n−1)</math>。
第一递归定理问的是：'''什么样的 <math>\Psi</math> 能保证方程 <math>\phi = \Psi(\phi)</math> 有解，而且解是[[可计算的]]？'''
第一递归定理问的是：'''什么样的 <math>\Psi</math> 能保证方程 <math>\phi = \Psi(\phi)</math> 有解，而且解是[[可计算的]]？'''