Grzegorczyk分层的一种延伸
DOI:
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金


AN EXTENSION OF Grzegorczyk's HIERARCHY
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    本文讨论某些递归函数类的分层问题.首先给出的是原始的Gorzegorczyk分层的一种较为简单的等价定义.然后,作为对Ackermann函数的一种推广,定义了一个递归函数序列{An∈ω.并以此作为分层函数列定义了一种新的递归分层{Zn∈ω(即Z—分层),这种分层涉及了比原始递归函数类更大的一个违归函数类.实际上,原始递归函数类仅是Z—分层的第一层Z.而且这种分层的任意的第n+1层都含

    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 {An∈ω, based on which they define hierarchy, {Zn∈ω(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 {Zin,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.

    参考文献
    相似文献
    引证文献
引用本文

郑锡忠,钱磊. Grzegorczyk分层的一种延伸.软件学报,1994,5(3):55-64

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:1991-07-22
  • 最后修改日期:1991-12-21
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号