Grzegorczyk分层的一种延伸  

AN EXTENSION OF Grzegorczyk's HIERARCHY

作　　者：郑锡忠[1] 钱磊[1] 

机构地区：[1]南京大学,南京航空学院

出　　处：《软件学报》1994年第3期55-64,共10页Journal of Software

基　　金：国家自然科学基金

摘　　要：本文讨论某些递归函数类的分层问题．首先给出的是原始的Ｇｏｒｚｅｇｏｒｃｚｙｋ分层的一种较为简单的等价定义．然后，作为对Ａｃｋｅｒｍａｎｎ函数的一种推广，定义了一个递归函数序列｛Ａｎ｝ｎ∈ω．并以此作为分层函数列定义了一种新的递归分层｛Ｚｎ｝ｎ∈ω（即Ｚ—分层），这种分层涉及了比原始递归函数类更大的一个违归函数类．实际上，原始递归函数类仅是Ｚ—分层的第一层Ｚ０．而且这种分层的任意的第ｎ＋１层都含有前面一层的通用函数．最后还定义了Ｚ—分层的一种加细｛Ｚ｝ｎ，ｉ∈ω，使得｛Ｚ｝ｉ∈ω构成Ｚｎ的一种合理分层，并且在Ｚ０上的加细｛Ｚ｝ｉ∈ω刚好就是原始的Ｇｒｚｅｇｏｒｃｚｙｋ分层．这表明Ｚ—分层及其加细确为Ｇｒｚｅｇｏｒｃｚｙｋ分层的自然延伸．This paper discusses the hierarchies of some classes of recursive functions. A simple equivalent definition of original Grzegorczyk's hierarchy is presented at first. Then the authors define by the generalization of Ackermann's function a sequence of recursive functions {An}n∈ω, based on which they define hierarchy, {Zn}n∈ω(the Z-hierarchy)of a class of recursive functions which is much larger than the class of primitive recursive functions.The first level Z0 of this hierarchy is just the class of primitive recursive functions.For all n, Zn+1 contains the universal function of its predecessor Zn. A refinement {Z}n, i∈ωof Z-hierarchy is defined at last by the natural hierarchy of each Zn. The refinement on Z0 is same as the original Grzegorczyk's hierarchy. This shows that their Z-hierarchy and its refinement are really a natural extension of Grzegorczyk's hierarchy.

关 键 词：递归函数 G-分层 分层 Z-分层 

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]