关于广义递归论介绍

[拼音]：guangyi diguilun

[外文]：generalized recursion theory

把自然数集上定义的递归论推广到其他数学结构上去而得到的数学理论。常见的有有穷类型对象上的递归论和序数上的递归论。

有穷类型对象如下定义：自然数称为0型对象。由n型对象到自然数集的全函数称为n+1型对象。一型对象φ的计算相当于有一个执行机械过程的机器M，对M输入数n后可得到输出m=φ(n)。二型对象F(ƒ，n)的计算相当于上述机器M外加上一个外部信息源即ƒ 的图形。对输入ƒ，n，M对输入n的计算时，常要问机外信息源ƒ对某个变目的值，根据值的不同而依不同的步骤进行计算，最后给出输出m=F(ƒ，n)。上述两类计算都是有穷步内完成的计算。三型对象F(F，ƒ，n)的计算相当于上述机器M外加上两个外部信息源即ƒ的图形(基数为堗0)和F 的图形（基数为2）。M对输入n 的计算时要问到ƒ对某变元的值，和问到F对某变元的值。在问到F对变元g的值时要计算g的图形，因此此时M的计算不再是有穷步内可停止的计算了。相仿地可有更高类型对象的计算。

还可以把递归论推广到序数上去。最初是用集合论的工具，如降S-L定理，推广到一切序数上去。后来发展为推广到序数的某些前节上去。最主要的是推广到可允许序数上去，称为α－递归论。当α>ω后出现了许多ω-递归论中不存在的现象，例如有界和有穷不再是相同的概念了，这就使α-递归论的证明大大地复杂了。

ω-递归论的某些结果可以推广到一切可允许序数α上去，例如波斯特问题的解决。有些结果只在某些可允许序数上成立，而在另一些可允许序数上不成立，如极大集的存在性定理。再如当α>ω后，O′以下ω-度的结构和O′以α-度的结构不同构。