# 何谓“计算”？ -- 可计算性理论简介 精选

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

“给出一个判定过程，它允许人们通过有限次数的运算来判定任意一个给定（一阶谓词– 笔者注）逻辑表达式的普遍有效性(或者其否定的可满足性，希尔伯特和阿克曼把这两个等价的判定问题统称为判定问题 - 笔者注) (It was to give a decision procedure(Entscheidungsverfahren)‘that allows one to decide the validity (respectively satisfiability) of a given logical expression by a finite number of operations’[1,1928(1st Ed.), pp.72-73])”[2]。希尔伯特和阿克曼将此问题称为“数理逻辑基本(主要)问题(the fundamental(main) problem of mathematical logic)”[1,2]。

“希尔伯特判定问题是，发现一种方法，对于任意一个给定一阶谓词逻辑式，它可以通过有限次清晰定义的能行步骤判定该公式是否是普遍有效的(Hilbert’s Entscheidungsproblem was to provide a method that would, given a formula of first-order logic, determine in a finite unmber of well-defined effective steps whether or not that formula is valid) 。”[3]

[1] D. Hilbert and W. Ackermann, “Grundzüge der theoretischen Logik,” 1928(1st Ed.), 1938(2nd Ed.), 1949(3rd Ed.), 1959(6th Ed.), Springer-Verlag (in German).
English translation: “Principles of Mathematical Logic,” AMS Chelsea Publishing, 1950 (translation of the 1938 second edition).

Book review: C. H. Langford, “Hilbert and Ackermann on Mathematical Logic,” Bulletin of the American Mathematical Society, Vol. 36, pp. 22-25, 1930.
Book review: H. B. Curry, “Hilbert and Ackermann on Mathematical Logic,” Bulletin of the American Mathematical Society, Vol. 59, pp. 263-267, 1953.

[2] R. I. Soare, “The History and Concept of Computability,” in E. R. Griffor (Ed.), “Handbook of Computability Theory,” Elsevier, 1999.

[3] M. Davis, “Engines of Logic – Mathematics and the Origin of the Computer,” W.W. Norton, 2000. 中译(张卜天译):“逻辑的引擎”，2005.

[4] D. Hilbert, “Grundlagen der Geometrie,” Teubner, 1899 (in German).

[5] D. Hilbert, “Mathematische Probleme,” Nachrichten von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, Math.-Phys. Klasse, pp. 253–297，1900 (in German) (Lecture Delivered before the International Congress of Mathematicians at Paris in 1900)

[6] D. Hilbert,“über die Grundlagen der Logik und der Arithmetik”, in Verhandlungen des dritten Internationalen Mathematiker-Kongresses in Heidelberg, 1904 (in German).

[7] R. Zach, “Hilbert’s Program,” Stanford Encyclopedia of Philosophy, 2003,2019.

[8] 王宪钧, “数理逻辑引论 第三篇 数理逻辑发展简述”，北京大学出版社，1982, 1998.

[9] K. Gödel, “Uber formal unentscheidbare satze der Principia Mathematica und verwander systeme,” Monatschefte fur Mathematik und Physik, 38, pp. 173-198, 1931 (in German).

[10] S. C. Kleene, “General Recursive Functions of Natural Numbers,” Mathematische Annalen, Vol. 112, pp. 727-742, 1936.

[11] A． Church, “An Unsolvable Problem of Elementary Number Theory,” American Journal of Mathematics, Vol. 58, pp. 345-363, 1936.

[12] A． Church, “A Note on the Entscheidungsproblem,” Journal of Symbolic Logic, Vol.1, pp. 40-41, 1936.

[13] A． Church, “The Calculi of Lambda Conversion,” Princeton University Press, 1941.

[14] E. L. Post, “Finite Combinatory Processes – Formulation 1,” Journal of Symbolic Logic, Vol. 1, pp. 103-105, 1936.

[15] A. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, Series 2, 42, pp. 230-265, 1936, Series 2, 43, pp. 544-546，1937.

https://wap.sciencenet.cn/blog-2371919-1383722.html

## 全部精选博文导读

GMT+8, 2023-10-2 06:17