关于Grzegorczyk第九问题  

On the Ninth Grzegorczyk's Problem

作　　者：卢殿臣[1] 郑锡忠[2] 

机构地区：[1]江苏工学院 [2]南京大学

出　　处：《江苏大学学报（自然科学版）》1992年第3期94-101,共8页Journal of Jiangsu University：Natural Science Edition

基　　金：国家自然科学基金资助

摘　　要：本文通过引进二重递归函数类的一种分层{Y_n}_(n∈∞),证明了借助于本原函数(后继函数、零函数和投影函数)以及原始递归和复合运算,如果仅增加有限多个二重递归函数作为开始函数,则不足以产生全体二重递归函数。This paper introduces a proper hierarchy {Yn}n of the class of all double recursive functions and proves that the class of all double recursive functions cannot be generated from the basic functions (i. e Successor, Zero and Projection functions) and any finite double recursive functions by the operations of composition and primitive recursion.

关 键 词：递归论 递归函数 分层/Grzegorczyk问题 

分 类 号：N55[自然科学总论]