杨正瓴
《中国“科学网大学”逻辑基础研讨中心》活动之三:俗解Chaitin
2011-8-21 22:15
阅读:20202
标签:Theorem, amp, ouml, del, incompleteness
《中国“科学网大学”逻辑基础研讨中心
活动之三:俗解Chaitin定理(长期增加中)
 
请您指正与补充!真正的逻辑学家们!谢谢!  
 
 
一般认为,Chaitin定理是Gödel第一不完全定理在信息论意义下的具体化。

Chaitin定理的内容如下(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).

  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.

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

 
 
       这里真傻给出一个Chaitin定理的俗解,请有关的逻辑学家指点。目的是尽快让研究生理解Chaitin定理的实质。
      以下的俗解完全有可能是不恰当的,期待您的改进与批评!
 
       可以把一个公理系统比做一个洗菜盆,
       (1)如果土豆、西红柿、茄子等比“洗菜盆”小,则可以在该盆里洗;
       (2)显然这个洗菜盆不能洗大冬瓜;但从土豆、西红柿、茄子的个头越来越大的次序看,应该存在大冬瓜;
       (3)不幸的是,洗菜是两难之一:用小洗菜盆洗,则需要多次换水;用另外一个大洗菜盆洗,就可以少换几次水。
 
       逻辑和实验是代科学的两大基础。
       尽管古希腊、我国先秦时期就发现了
(形式)逻辑里面的悖论,但后来的数学家们似乎忘记了这些。直到罗素悖论(Russell's paradox,也称为理发师悖论,1901年提出),数学家们才重新认真看待这些问题。
       1931年Gödel incompleteness theorem是著名的。1974年的前几年,Chaitin定理出现。
       按照一定方式,靠系统自身的反思,不可避免地具有局限性。
 
问题1:“君子博学而日参省乎己”,就一定能保证“则智明而行无过矣”吗?
问题2:为什么毛主席要求我们“批评与自我批评”?
 
从外部获取信息,
是克服“特定系统”自身局限性的主要途径。
 
问题3:真理、规律的“客观性”存在吗?因为我们在有限条件下不能认识“绝对真理”,就必须排除真理的客观性吗?
问题4:我不知道我死了(计算机停机问题)。别人也就不能知道我死了吗?
问题5:语言、视觉都有局限性。不能眼、耳、口直接交流的信息,就不存在吗?
问题6:佛陀释迦摩尼的“若以色见我,以音声求我,是人行邪道,不能见如来。”是什么意思?
 
       “我相,即是非相;人相、众生相、寿者相,即是非相。何以故?离一切诸相,即名诸佛。”
       所以:实践是检验真理的唯一标准。“实验”大于“逻辑”。


以上内容,定有错误。看在真理的份上,请您指正!谢谢!
 
 
——————— 相关汉语成语 ———————

管窥蠡测

       管窥蠡测这个成语源自“以管窥天,以蠡测海”。原话表面的意思是:从竹管的小孔里看天,用瓠瓢量海水。它的引申义是:目光短浅,眼光狭小,对事物的观察和了解都很肤浅。类似“坐井观天”的意思。
       出自:东汉·班固《汉书·东方朔传》:“以管窥天,以蠡测海,以莛撞钟,岂能通其条贯,考其文理,发其音声哉。”
 
http://www.zdic.net/cd/ci/14/ZdicE7ZdicAEZdicA1291484.htm
 
       take a narrow view of sth;look at the sky through a bamboo tube and measure the sea with a calabash——restricted in vision and shallow in understanding.
       管中视天,以瓢量海水,喻眼光狭小,见识不广或不自量力。
 
成語:管窺蠡測
http://bookstrg.com/Readstory.asp?Code=SS205844
 
 
 

相关链接
[1] 《中国“科学网大学”逻辑基础研讨中心》活动之一:逻辑基础资源 
http://bbs.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=430666
[2] 《中国“科学网大学”逻辑基础研讨中心》活动之二:逻辑与数学 
http://bbs.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=440876
[3] 逻辑方法的局限性:Gödel incompleteness theorem和Chaitin theorem
http://blog.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=301287

相关专题:众议“科学网大学”

转载本文请联系原作者获取授权,同时请注明本文来自杨正瓴科学网博客。

链接地址:https://wap.sciencenet.cn/blog-107667-478066.html?mobile=1

收藏

分享到:

当前推荐数:16
推荐到博客首页
网友评论37 条评论
确定删除指定的回复吗?
确定删除本博文吗?