| 摘要: |
| 本文讨论某些递归函数类的分层问题．首先给出的是原始的Ｇｏｒｚｅｇｏｒｃｚｙｋ分层的一种较为简单的等价定义．然后，作为对Ａｃｋｅｒｍａｎｎ函数的一种推广，定义了一个递归函数序列｛Ａｎ｝ｎ∈ω．并以此作为分层函数列定义了一种新的递归分层｛Ｚｎ｝ｎ∈ω（即Ｚ—分层），这种分层涉及了比原始递归函数类更大的一个违归函数类．实际上，原始递归函数类仅是Ｚ—分层的第一层Ｚ０．而且这种分层的任意的第ｎ＋１层都含 |
| 关键词: 分层，Grzeyorczyk分层，Z—分层 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金 |
|
| AN EXTENSION OF Grzegorczyk's HIERARCHY |
|
Zheng Xizhong,Qian Lei
|
| Abstract: |
| 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 {Aｎ｝ｎ∈ω, based on which they define hierarchy, {Zｎ｝ｎ∈ω(the Z-hierarchy)of a class of recursive functions which is much larger than the class of primitive recursive functions.The first level Z０ 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ｎi｝ｎ,i∈ωof Z-hierarchy is defined at last by the natural hierarchy of each Zn. The refinement on ZO 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. |
| Key words: Hierarchy Grzegorczyk's hierarchy Z-hierarchy. |
