递归函数论

本书为莫绍揆编著的《递归函数论》，1965年11月由上海科学技术出版社第1版第1次印刷，上海市印刷四厂印刷，新华书店上海发行所发行，开本850×1156 1/32，印张10 2/32，排版字数248,000，印数1—1,900册，统一书号13119·674，定价（科六）1.50元。据内容提要，本书阐述递归函数论的最基本内容，计分八章，即五则函数、算子、初等函数集、原始递归函数集、一般递归函数集、递归生成的函数集、谓词与集合、判定问题；第一章之前的绪论介绍预备知识。全书以算子概念贯穿始末，系统总结这方面的理论。内容提要并称全书叙述深入浅出，注意到对基本概念的讲深讲透和基本技巧的训练，每节之末附有足量习题，是递归函数论的较好入门书，只须稍具数理逻辑知识和一定数学训练的读者即可看懂；可供高等院校“递归函数论”课程作为教材或教学参考书，也可供有关人员自学与参考。

作者序进一步说明本书的性质与编写原则：本书基本上只是递归函数论的入门书，对较为高深的部分并未涉及，但比较浅近的内容则力求完备；强调基本概念的澄清与基本技巧的掌握，特别以算子概念作为贯穿全书的一条线索。序中认为，在递归函数论中只当使用算子概念后，对函数的组成、函数集等概念才能较好理解，“参数”概念才获得更好说明，因此本书一开始便引进一套既有系统又很方便的有关算子的符号。序中还说明本书未包括Turing机器论、递归算术、递归分析，Turing机器宜在算法论中讨论；并大略介绍递归函数论的应用，包括递归过程研究、电子计算机使用以来的近似计算与程序设计、迭代过程与循环、时序线路内部状态与自动机反馈、能行性研究、数理逻辑、算术、数学分析中的递归分析，以及递归数论与数论的关系。序中并说明作者经几年工作积累若干习题，分列各节之末，有难有易，读者可酌量选做，其余留待进一步研究复习之用。

从目录可见，绪论包括自然数集与数论函数、函数与依变元、可直接定义的函数、迭置、算子、函数的定义过程（组成过程）、谓词与特征函数、数学归纳法等预备知识；第一章“五则函数”讨论五则函数、配对函数、有限数列的表示、迭置的化归；第二章“算子”讨论摹状算子与求逆算子、逆算子、算子分类、算子相互表示及化归、递归生成的函数集、三大函数集；第三章“初等函数集”讨论四个初等函数集、初等函数集的重要性质、最强的初等算子、初基函数集；第四章“原始递归函数”讨论与初等函数的关系、原始递归式的化归与加强、多重递归式、非原始递归函数之一例、递归式与数学归纳法；第五章“一般递归函数”讨论一般递归函数与原始递归函数、一般递归式的化归与加强、一般递归式与超穷递归式、摹状式与一般递归式、利用摹状式作一般递归函数集、一般递归函数的典范式、部分函数与半递归函数、可在有限步骤内计算的函数、可形式计算的函数；第六章“递归生成的函数集”讨论控制函数、递归生成函数集的枚举、一般递归函数集的枚举、自身枚举与主要自身枚举；第七章“谓词与集合”讨论各种谓词、多项式谓词、新初基谓词、半递归谓词、算术谓词、非算术谓词之一例、部分函数与半特征函数、集合；第八章“判定问题”讨论个别问题与大量问题、判定性的初步性质、基本的不能判定问题、半递归函数间的关系和性质之不可完全判定性。本次仅见前20页，后续内容待补。