基于有限递归和μ-算子的α-递归论

α-RECURSION THEORY ON FINITE RECURSION AND μ-PEATION

根据 Blum,Shub和 Smale定义实数环上的计算模型中将递归和 μ-算子限制在自然数上这一特点 ,提出了基于自然数上的递归定义和μ-算子。研究了在可允许序数α-上定义的可计算函数——弱α-递归函数的弱 α-递归论的基本性质及其与 α-递归论的差别 ,证明了每个弱 α-递归函数是以自然数为参量关于取值 α上的变量的多项式函数 ,并且每个弱

Based on the characteristic of restricting the recursion and μ operation on the natural numbers in the computing model on the real numbers by Blum, Shub and Smale, this paper puts forward the conception of recursion definition and μ operation on natural numbers, and that of computable function on admissible order number α , i.e., weakly α recursive function. It studies the properties of the weakly α recursion theory and proves that every α resursive function is a polynomial function with natural number as its parameters and ranged on α , and that every join set of weakly α resursive set and natural number set is resursive enumerable set.