[敬请读者注意] 本人保留本文的全部著作权利。如果哪位读者使用本文所描述内容，请务必如实引用并明白注明本文出处。如果本人发现任何人擅自使用本文任何部分内容而不明白注明出处，恕本人在网上广泛公布侵权者姓名。敬请各位读者注意，谢谢！

哥德尔关于可计算性的开创性工作不容忽视

程京德

9月12日，科学网上发表了一篇被“精选”的博客文章，“数理逻辑发展的基本动机”(http://blog.sciencenet.cn/blog-2349385-1075495.html)。此文对所谓“理论计算机科学的诞生”完全是误导读者，必须予以批评。

该文中有这样一段话：“而第二个问题则是现代哲学和计算机科学最关注的问题之一：是否可以解决用这个“普遍语言”所形式化描述的所有问题？这个问题就是所谓“可判定性问题”（Entscheidungsproblem，decision problem）。对这个问题的研究最终导致了理论计算机科学的诞生：阿隆佐·丘奇和阿兰·图灵分别以各自的方式对这个问题做出了否定的回答。他们在研究这个问题时首先对“可判定的”（decidable）这个直觉概念进行了深入研究并给出了形式化定义和解释，进一步把这个问题归结成“可计算的”（computable）问题，并最终将其定义为“可计算函数”（computable function）问题的研究。为此，丘奇和图灵分别提出了关于可计算函数的模型。图灵的模型就是著名的图灵机，它已经成为现代计算机科学的理论基础；而丘奇的模型则是lambda演算，这成为后来计算机语言Lisp和现代函数式程序语言的理论基础。其后图灵证明了这两个模型其实定义了同一类别的可计算函数。可以说，丘奇和图灵对数理逻辑的研究是从传统的解决数学基础问题出发开创了一个崭新的领域：计算科学。”

然而，尽管在说可计算性，该文却通篇未提有关哥德尔及其关于可计算性的开创性工作一个字！

任何不具有专业知识的读者，读了该文上面那段话，必定认为，所谓的“理论计算机科学”或者“计算科学”，是由丘奇和图灵所开创的。但是这完全不是事实！

现今，对哥德尔的工作肆意曲解和夸大的文章到处可见、数不胜数，但是，如此无视哥德尔及其工作之意义的文章，笔者还是第一次见到。

作为对该文对读者之误导的批评，笔者陈述一些基本事实如下：

首先，计算机科学界至今并未对何为“理论计算机科学”有一致认可的范围界定。但是至少可以说，“理论计算机科学”包含“可计算性理论”，而“可计算性理论”并非“理论计算机科学”之全部。

其次，是哥德尔，以其关于PM及相关形式系统不完全性定理（1931年）、原始和一般递归函数（1931年，1934年）的出色工作，开创了可计算性理论这一领域。世界上第一个形式地构造出来的不可判定问题，是哥德尔在其证明不完全性定理时所作出的工作成果。

再次，丘奇和柯林尼关于Lambda演算的工作是在1933年-1935年期间完成的，图灵关于图灵机的工作是在1936年-1937年期间完成的，都分别晚于哥德尔的工作。

最后，上述基本事实都是在计算机科学界和数理逻辑学界所公认的和周知的。

针对有兴趣进一步了解此问题的读者，介绍一下参考文献：哥德尔的原著，可参阅文献1-3，关于哥德尔工作的专业科普著作，可参阅文献7-11中的相关内容，关于数理逻辑史，可参阅专业科普著作4-7及11。

作为结束，笔者想借此机会重申笔者本人的一个看法，“对于一个正派的、有影响力的学者来说，无论在何种媒体上做何种专业的科普工作都应该是一件极其严肃认真的、必须负责的事情；因为许多非专业工作者、青年学生、普通民众将会从科普文章中获取知识，他们未必有专业素养来自己判断是非曲直，往往盲目轻信科普文章中的内容。所以，一篇科普文章如果言过其实甚至瞎编乱造，所造成的恶劣影响远远大于一篇发表在专业媒体上的专业文章。”（程京德；“科普文章作者的责任”, http://blog.sciencenet.cn/blog-2371919-1053444.html）

参考文献

1. K. Gödel, “über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,” Monatshefte für Mathematik  Physik, Vol. 38, pp. 173–198, 1931. (The summary of the results of this work, published in Anzeiger der Akad. D. Wiss. In Wien (math.-naturw. Kl.)1930, No. 19.)
Translation: B. Meltzer (translation) and R. B. Braithwaite (Introduction), K.  Gödel, “On formally undecidable propositions of Principia Mathematica and related systems I,” Basic Books, 1962, Dover  Publications, 1992.

2. K. Gödel (1930b, 1931, and 1930a), “Some metamathematical results on completeness and consistency, On formally undecidable propositions of Principia Mathematica and related systems I, and On completeness and consistency,” in J. Van Heijenoort (Ed.), “Frege and Gödel: Two Fundamental Texts in Mathematical Logic,” pp. 83-108, Harvard University Press, 1970.  

3. K. Gödel, “über formal unentscheidbare Sätze derPrincipia Mathematica und verwandter Systeme I,”“On formally undecidable propositions of Principia Mathematica and related systems I,” in S. Feferman, et al. (Eds.), “Kurt Gödel: CollectedWorks,” VolumeI, Publications 1929-1936, pp. 144-195, Oxford University Press, 1986.

4. W. Kneale and M. Kneale, “The Development of Logic,” Oxford University Press, 1962. 张家龙，洪汉鼎（译），“逻辑学的发展”，商务印书馆，1985.

5. P. H. Nidditch, “The Development of Mathematical Logic,” Routledge Kegan Paul, 1962, Thoemmes Press, 1998.

6. H. DeLong, “A Profile of Mathematical Logic,”Addison-Wesley, 1970, Dover Publications, 1998.

7. 王浩, “数理逻辑通俗讲话”，科学出版社, 1981; “Popular Lectures on Mathematical Logic,” Science Press and Von Nostrand Reinhold, 1981; “Popular Lectures on Mathematical Logic (added apostscript),” Dover Publications, 1993.

8. 王宪钧, “数理逻辑引论”，北京大学出版社, 1982(1998年再版).

9. 黄耀枢, “数学基础引论”， 北京大学出版社, 1987年.

10. 朱水林，“哥德尔不完全性定理”，辽宁教育出版社，1987年.

11. 张家龙，“数理逻辑发展史—从莱布尼茨到哥德尔”，社会科学文献出版社，1993年.