# 逻辑方法的局限性：Godel incompleteness theorem和Cha

1931年的Gödel incompleteness theorem（哥德尔不完全性定理）和1966-1974年的Chaitin theorem（柴廷定理），就是这样说的。

Gödel incompleteness theorem 在《Encyclopaedia of Mathematics, Edited by Michiel Hazewinkel》

http://eom.springer.de/G/g044530.htm

A common name given to two theorems established by K. Gödel [1]. Gödel's first incompleteness theorem states that in any consistent formal system containing a minimum of arithmetic ( +, ·, the symbols , and the usual rules for handling them) a formally-undecidable proposition can be found, i.e. a closed formula such that neither nor can be deduced within the system. Gödel's second incompleteness theorem states that if certain natural completeness conditions are met, one can take this formula to be the formula which expresses the consistency of the system. These theorems indicated the failure of Hilbert's program on the foundations of mathematics, which expected a full formalization of all existing mathematics, or at least of a substantial part of it (Gödel's first incompleteness theorem proved that this is not possible), and attempted to justify the resulting formal system by a finite demonstration of its consistency (Gödel's second incompleteness theorem showed that even if all the tools of formalized arithmetic are considered to be finitary, this is still insufficient to prove the consistency of arithmetic).

http://202.112.118.40:918/web/index.htm

“1931年的讲师论文证明了：一个包括初等数论的形式系统P，如果是相容的则它是不完全的（即在本系统中必存在不可证明的真命题）。同一论文还证明：这样系统的相容性在本系统中不能证明，更不能用有穷方法证明。”

Chaitin theorem:

It is also possible to make a similar analysis of the deductive method, that is to say, of formal axiom systems. This is accomplished by analyzing more carefully the new version of Berry's paradox that was presented. Here we only sketch the three basic results that are obtained in this manner. (See the Appendix).

In a formal system with n bits of axioms it is impossible to prove that a particular binary string is of complexity greater than n+c. Contrariwise, there are formal systems with n+c bits of axioms in which it is possible to determine each string of complexity less than n and the complexity of each of these strings, and it is also possible to exhibit each string of complexity greater than or equal to n, but without being able to know by how much the complexity of each of these strings exceeds n. Unfortunately, any formal system in which it is possible to determine each string of complexity less than n has either one grave problem or another. Either it has few bits of axioms and needs incredibly long proofs, or it has short proofs but an incredibly great number of bits of axioms. We say “incredibly”' because these quantities increase more quickly than any computable function of n.

Kurt Gödel（1906 – 1978）在MacTutor History of Mathematics：

http://www-history.mcs.st-and.ac.uk/Biographies/Godel.html

Kurt Gödel（1906 – 1978）照片在MacTutor History of Mathematics：http://www-history.mcs.st-and.ac.uk/PictDisplay/Godel.html

Gregory J. Chaitin：http://www.umcs.maine.edu/~chaitin/

Gregory J. Chaitin的照片：http://www.cs.auckland.ac.nz/~chaitin/bio.html

Gregory J. Chaitin, Visit to Cornell University, Winter 1973-1974, Photo by Terry Fine

（1）逻辑方法的局限性：元知识、乌龟塔与盲人摸象

http://www.sciencenet.cn/m/user_content.aspx?id=301534

（2）逻辑方法的局限性：Godel incompleteness theorem和Chaitin theorem

http://www.sciencenet.cn/m/user_content.aspx?id=301287

（3）爱因斯坦与教育

http://www.sciencenet.cn/m/user_content.aspx?id=288903

（4）什么是“证明” The definition of Proof

http://www.sciencenet.cn/m/user_content.aspx?id=221874

（5）怎么翻译爱因斯坦谈科学起源

http://www.sciencenet.cn/m/user_content.aspx?id=216696