[科普 + 备课] Chaitin定理（1966年）

   今年春节，心情是复杂的。有时“也拟哭途穷”，也快“死灰吹不起。”更多的是“中间多少真傻泪”，“江晚正愁予，山深闻鹧鸪。”

一、Chaitin定理（1974年版）

Gregory John Chaitin, 1947-06-25 ~ 

   汉语介绍“Chaitin定理”的资料似乎不多。1974年 Chaitin 自己原汁原味对Chaitin定理的介绍如下：

https://ieeexplore.ieee.org/document/1055172

Gregory John Chaitin. Information-theoretic computation complexity [J]. IEEE Transactions on Information Theory, 1974, 20(1): 10-15. DOI: 10.1109/TIT.1974.1055172

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

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

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

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

二、爱因斯坦论“实验与逻辑“

   详见2015年《科学网》博文专题：爱因斯坦的回信。

https://news.sciencenet.cn/news/sub26.aspx?id=2201

   1953年4月23日爱因斯坦写给斯威泽（J.S. Switzer）的回信里说：“西方科学的发展是建立在两项重大成就的基础上的：希腊哲学家们（在欧几里德几何学中）发明的形式逻辑体系，和（文艺复兴时期）发现的通过系统实验找到因果关系的可能性。”

   所以，

   我们总得学点逻辑吧？

   据说莱布尼兹将形式逻辑发展到数理逻辑。在我们使用具体的逻辑时，注意到逻辑方法自身的局限性应该不是坏事。

   但愿没有吓死人！

三、1931年开始的演绎逻辑新进展

   （1）1931年的哥德尔不完全性定理，

   （2）1966年的Chaitin定理。

   （3）感谢您指出更新的进展。

   逻辑（logic）是思维的规律和规则。

   逻辑包括形式逻辑和数理逻辑（符号逻辑）。形式逻辑包括归纳逻辑与演绎逻辑。

   概念的内涵和外延：往往内涵越丰富，外延就越小；反之，内涵越简单，外延就越大。

   演绎逻辑受到哥德尔不完全性定理和Chaitin定理的限制。

   据说哥德尔说：“没有一个在特定分辨率层次上形成的知识系统，能够完全解释那个层次，必须具有一个高层元知识才能完全解释它。然而，当我们着手去构造这个更一般的元知识时，它也要求更高一层的元-元知识去解释它。”[求原文的出处]

   《论语·卫灵公》里孔子老师说：“工欲善其事，必先利其器。”

   这和 1966年的Chaitin定理很类似：强调具体的“能行”与“不能行”，与采用的具体工具有关。

   老子《道德经》第五十四章：“故以身观身，以家观家，以乡观乡，以国观国，以天下观天下。吾何以知天下然哉？以此”。

   和哥德尔上面的观点以及1966年的Chaitin定理也很类似：工具能力强了，“能行”的也就多了。

权威链接：

[1] 2015，《科学网》博文专题：爱因斯坦的回信

https://news.sciencenet.cn/news/sub26.aspx?id=2201

https://blog.sciencenet.cn/blog.php?mod=subject&id=223

介绍 Gregory John Chaitin 的网页：

[1] Gregory J Chaitin

IBM Thomas J. Watson Research CenterIBM ResearchIBM, ArgentinaCity University of New York

https://dl.acm.org/profile/81100554188

[2] Gregory Chaitin - CodeDocs

https://codedocs.org/what-is/gregory-chaitin

   Gregory John Chaitin (/ˈtʃaɪtɪn/ CHY-tin; born 25 June 1947) is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-theoretic result equivalent to Gödel's incompleteness theorem.[2] He is considered to be one of the founders of what is today known as algorithmic (Solomonoff–Kolmogorov–Chaitin, Kolmogorov or program-size) complexity together with Andrei Kolmogorov and Ray Solomonoff. 

参考资料：

[1] Gregory John Chaitin. Information-theoretic computation complexity [J]. IEEE Transactions on Information Theory, 1974, 20(1): 10-15.

DOI: 10.1109/TIT.1974.1055172

https://ieeexplore.ieee.org/document/1055172

https://dl.acm.org/doi/10.1109/TIT.1974.1055172

[2] Gregory J. Chaitin. On the length of programs for computing finite binary sequences [J]. Journal of the ACM, 1966, 13(4):  547-569.

doi：10.1145/321356.321363

https://dl.acm.org/doi/10.1145/321356.321363

[3] 杨东屏. 哥德尔不完全性定理剖析[J]. 曲阜师范大学学报：自然科学版,1993,19(1):31-36.

https://kns.cnki.net/KCMS/detail/detail.aspx?dbcode=CJFD&filename=QFSF199301005

[4] 逻辑(思维的规律和规则) - 百度百科

https://baike.baidu.com/item/%E9%80%BB%E8%BE%91/543

[5] 王宪钧. 数理逻辑引论[M]. 北京：北京大学出版社，1982.

相关链接：

[1] 2011-08-21，俗解Chaitin定理

https://blog.sciencenet.cn/blog-107667-478066.html

[2] 2022-02-19，[科普 + 备课] 哥德尔不完全性定理（1931年）

https://blog.sciencenet.cn/blog-107667-1326086.html

[3] 2010-03-09，逻辑方法的局限性：Gödel incompleteness theorem和Chaitin theorem

https://blog.sciencenet.cn/blog-107667-301287.html

[4] 2015-03-30，[求助] 哥德尔（Kurt Gödel ）一句话的英文原文

https://blog.sciencenet.cn/blog-107667-878552.html

[5] 2010-03-10，逻辑方法的局限性：元知识、乌龟塔与盲人摸象

https://blog.sciencenet.cn/blog-107667-301534.html

[6] 2013-06-30，因果性与逻辑

https://blog.sciencenet.cn/blog-107667-703983.html

[7] 2013-09-07，逻辑能力与数理科学创新小议

https://blog.sciencenet.cn/blog-107667-738568.html

[7-2] 逻辑能力与数理科学创新小议[J]. 科技导报, 2014, 32(1): 88-88.

http://www.kjdb.org/CN/abstract/abstract11234.shtml

[8] 2021-05-05，[老照片] 哥德尔和爱因斯坦在普林斯顿散步，1954年

https://blog.sciencenet.cn/blog-107667-1285132.html

[9] 2009-02-23，怎么翻译爱因斯坦谈科学起源

https://blog.sciencenet.cn/blog-107667-216696.html

[10] 2021-08-05，[备课] 电容、电感、电阻的电路模型（“场”是“路”的基础）

http://blog.sciencenet.cn/blog-107667-1298456.html

[11] 2021-12-07，[备课？答疑？笔记？] 结点电压法里的电压和电流方向

https://blog.sciencenet.cn/blog-107667-1315545.html

[12] 2021-03-05，[备课的随想] 模糊控制为什么成功？

https://blog.sciencenet.cn/blog-107667-1275148.html

[13] 2020-03-19，[讨论] 两种真正实用的自动控制技术：PID、模糊控制

https://blog.sciencenet.cn/blog-107667-1224280.html

感谢您的指教！

感谢您指正以上任何错误！

感谢您提供更多的相关资料！