博文

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

已有 16037 次阅读 2010-3-9 13:18 |个人分类:基础数学-逻辑-物理|系统分类:科研笔记| Godel, Chaitin, 哥德尔不完全性定理, 柴廷定理

逻辑方法的局限性：Gödel incompleteness theorem和Chaitin theorem

现代科学科学的2个方法：逻辑和实验（怎么翻译爱因斯坦谈科学起源，http://www.sciencenet.cn/m/user_content.aspx?id=216696）。但实验的能力高于逻辑的能力（实践是检验真理的唯一标准）。

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).

哥德尔，K. 在《中国大百科全书(卷名：数学)》

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.

见：Gregory J. Chaitin. Information-Theoretic Computational Complexity. IEEE Transactions on Information Theory, IT-20 (1974), pp. 10-15.

介绍数学家的一个网站：MacTutor History of Mathematics，网址：http://www-history.mcs.st-and.ac.uk/

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

所以“自然科学有两大传统：博物学传统和数理传统。其中博物学传统中有大量值得提取的积极内容，它强调对人类经验的重视，对生物多样性、对外部自然世界的尊重，一定意义上的非人类中心论，一定程度上对数理模型保持本能的警觉。”（刘华杰，博物学应当在高等教育中站稳脚跟，http://www.sciencenet.cn/m/user_content.aspx?id=298063，《中国社会科学报》，2010.02.25，第11版。）