递归函数理论以及有效可计算性

Theory of Recursive Functions and Effective Computability

Hartley ROGERS, Jr. 著 眭跃飞 译

McGraw-Hill Book Company, 1967

序

在1944年对美国数学协会的演讲中, E.L.Post总结说, “的确, 如果一般递归函数是有效可计算性的形式等价, 

它的形式化可以在组合数学的历史上起着仅次于自然数概念的形式化的作用."

    这书可以看着是一个进展报告Post论文中表示的一些想法和希望. 递归函数的主题先于1944被许多研究者研究过. 特别地,   Church, Kleene和Turing, 也包括Post他本人, 已经做主要的贡献. 尽管Post的论文只关注于一个更大主题的

一个部分, 它标记着这个主题的一个时代, 不仅对它呈现的特别的问题和方法, 也对它置于直观自然性于基本

概念的强调.

    Post的注释, 上面引用的, 毫无疑问地铺张的; 并且一个问题是是否这种表示为一般递归函数的可计算性将

具有一个很实际有用的理论. (我们进一步讨论这个于第1中.) 尽管如此, 这书企图是一个部分辩解Post的注释

以及他的态度. 这书呈现它的主题问题以半形式术语, 带有一个直观强调这是,希望地, 适当的和指导性的. 递归函数理论中半形式过程的使用类似于在其他数学部分中使用还没有完全形式

化的集合论讨论.

    对那些具有掌握简单的原始的想法于我们的理论来做研究是可能的, 就像对学校中的一个基础代数的学生

做自然数理论的研究是可能的.

    从1944, 特别是从1950开始, 递归函数理论的主题快速地增长. 许多研究者已经很活跃. 目前这书不是企图

是可理解的或确定的. 并且,它的非形式的和直观的强调将证明, 在某些方面, 是一个限制. 一些理论的重要部分(e.g., 研究各种一般递归

函数的真子类)以及一些有意义的应用(e.g., 确定数学其他部分的递归非可解问题)不能, 由他们的自然, 处理

如果没有更扩展的和仔细的形式化. 几个工作早已存在来提供这个缺陷, 并且读者要求使用他们作为一个

更形式的补充于目前的文本. 这些的一个是Kleene的Introduction to metamathematics,

D. Van Nostrand Company, Inc., Princeton, N.J., 1952; 另一个是Davis 的

Computability and unsolvability, McGraw-Hill Book Company, New York,

1958. 这些工作, 作为一个补充是有价值的, 不是这书的一个基础.

    这书有16章. 第1和2章呈现部分递归函数的基本概念并给出简单的不可解现象的例子. 第3和4章概括和刻画

要发展的理论. 第5章给出进一步基本概念. 第6至10章呈现不可解性的可归约性和度(Post的1944论文中强调

的概念). 第11章呈现递归定理, 一个该理论中的基础工具. 第12至16章呈现当前研究活跃的一些主要领域. 一个

更详细的概览于这书在第3章给出.

    在大部分章中, 最后一节给出练习. 练习出现的次序平行于主题出现在该章中的次序. 他们归为3个范畴: 无

标记的, 标记为一个三角($\triangle$), 以及(很少地)标记为一个实三角($\blacktriangle$). 第一范畴可以在

真正理解文本的情况下一个直接的方式可以解决. 第二范畴的练习有点困难. 第三范畴的练习更困难或要求, 

为容易解决, 还没有呈现的结果和方法的知识. 提示对许多练习提供(一个三角或实三角用于练习而没有提示).

实三角和更困难的三角的练习可以在一个后来点的文本中讨论. 特别主题, 增加文本, 有时覆盖在练习中并且

可以(尽管很少地)在文本的以后部分提及.

    恳请读者更努力地做无标记的和标记三角的练习. 如果一个练习有提示, 他应该做一个第一个尝试来解练习

而不读提示. 类似地, 在文本中他应该企图证明定理, 只要可能, 而不第一阅读文本中的证明. 如其他数学, 没有

更好的办法来发展洞察, 研究能力以及欣赏真正新的和富有成果的想法的差别, 并且例行的,

尽管有意思的, 扩展老的想法于另一个.

    递归函数理论的文献近年来快速增加. 这书给出的参考文献远没有完全. 只有很少的形式引用于1965及其

之后, 尽管这个期间的结果描述于文本中.

    这书的一个材料首先呈现在Massachusetts Institute of Technology 的讲座中和研讨会上. 我特别感谢

Noam Chomsky和Burton Dreben为他们耐心的鼓励以及这些讲座和研讨会的其他成员为各种我不能希望

详细地承认的帮助和建议. 我特别感谢Mary Marto和Marsha Scherr为耐心的和忠实的工作于打印和准备文

本, 并且Katharine Kumar 为帮助索引和证明的最后步骤. 我也感谢Ann

Singleterry, James Geiser和Leslie Tharp为帮助文本以及Patrick Fischer, Carl Jockusch, Donald Kreider

和Warren Teitelman为一个特别耐心的阅读文本的部分. 其他提供评价，建议和有价值的帮助的包括:

J. Addison, Y. Bar-Hillel, D. Bobrow, M. Blum, J. Conger, J. Denton,

H. Enderton, R. Friedberg, L. Hodes, C. Kent, D. Knutson, A. Levy,

D. Luckham, J. Lukas, J. MacIntyre, D. Martin, T. McLaughlin, M. Min-

sky, Y. Moschovakis, R. Parikh, D. Park, R. Putnam, W. Quine, IVI. Rabin,

H. Rice, W. Ritter, J. Rosenthal, G. Sacks, C. Shannon, J. Shoenfield,

C. Spector, J. Stillwell, J. Ullian, H. Wang, C. Yates以及P. Young.

    许多其他同仁和学生给出重要的帮助. 这些人, 有名字和没有名字, 提供许多想法, 但他们没有机会批评

最后文本.

    我欠一个特别的智力债于James Dekker, John MyhillNorman Shapiro. Shapiro引我到递归函数理论.    Dekker和Myhill的方法和态度已经对目前的工作有很大的影响.

    目前文本中的一部分材料, 以有点不同的次序和形式, 出现在Theory of recursive functions and effective computability, volume I, 由Massachusetts Institute of Technology数学系于1957年以影印的形式出版.

    这书将不会存在如果没有National Science Foundation通过MassachusettsInstitute of Technology数学系提供的资助G-19992, GP-379, GP-2496以及GP-6982. 我深深地感谢这期间这个资助使得可能.

                                                                                                                                                                         Hartley Rogers, Jr.

目录

注: 如果需要全文的, 请email我: yfsui@ict.ac.cn.