递归论基本内容

发布网友 发布时间：2024-12-26 13:53

我来回答

共1个回答

热心网友 时间：4分钟前

递归论的基本内容主要围绕函数的概念、构造与分类展开。函数分为全函数与半函数或部分函数。全函数在所有定义域内均有所定义，而半函数或部分函数则在部分定义域内不被定义。

三个最基本的函数包括零函数、广义幺函数或射影函数以及后继函数。这三个函数的总和构成了本原函数集。递归论利用各种算子与叠置来构造新函数，其中叠置是构造新函数最简单且最重要的方法，形式为由一个m元函数f与m个n元函数g1、g2、…、gm复合而成的新函数。

原始递归式是构造新函数的关键方法之一。它需要通过依次计算函数值来确定，只要初始函数为全函数且可计算，那么构造出的新函数也是全函数且可计算。原始递归函数通过有限次的叠置与原始递归式构造，由于本原函数的性质，原始递归函数也是全函数且可计算。在数论中广泛应用的数论函数均属于原始递归函数范畴。

除了原始递归式外，递归论还探讨了半递归式，即构造函数时不再直接化归于原始递归式，而是先化归于更高级的函数，直至化归到一个函数值为0的点。这使得构建出的函数可能成为半函数，但只要函数在定义域内存在值，该函数是可计算的。

在递归论中，递归半函数与递归全函数的区分主要在于函数是否在所有定义域内均有值。递归全函数的定义域内所有点均有值且可计算，而递归半函数在某些点上可能无定义，但只要存在定义，函数值是可计算的。

构造新函数的方法还包括逆函数的构建，通过逆函数可以解决给定函数的逆运算问题。逆函数的解方程过程可以视为对求根算子或摹状算子的使用。摹状算子用于解方程f(u,t,x)=0，得到最小x根。然而，即使初始函数是可计算的，使用摹状算子后的结果可能成为半函数，但在定义域内总是可计算的。

可摹状函数是通过有限次叠置原始递归式与摹状式构造的函数，其性质与递归半函数类似。无论是否全函数，可摹状函数在定义域内总是可计算的。已经证明，可摹状函数与递归半函数是等价的，且可摹状的全函数与一般递归函数也具有相同的性质。

递归论的结论受到数理逻辑学界的广泛认同，递归函数、递归半函数与递归全函数成为能行性理论的基础。递归函数的概念表明，即使存在与性质截然不同的函数类，它们仍然能够与递归函数等价，从而确立了递归函数作为可计算函数的重要地位。

递归论研究的函数主要包括本原函数、原始递归函数、递归半函数和递归全函数或称一般递归函数、可摹状函数等等。