以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 理论计算机科学 』 (http://bbs.xml.org.cn/list.asp?boardid=64) ---- 说谎者悖论与哥德尔不完全性定理[原创] (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=62844) |
-- 作者:chzhuang -- 发布时间:5/19/2008 8:34:00 PM -- 说谎者悖论与哥德尔不完全性定理[原创] 1、说谎者悖论 公元前6世纪希腊时代的一个诗人哲学家 Epimenides 说了一句很有名的话:「所有的克里特岛人都是说谎的。」这句话有名倒不是因为它是真理,正好相反,因为它一定是错的,为什么是错的呢?因为说这句话的人 Epimenides 就是克里特岛人,同样一句话,别人说也可能是对的(希望不致冒犯了克里特岛人),但是由克里特岛人来说,就一定是错的。2、说谎者悖论的其他形式 有人说了一句话:“这句话是假的。”,那么现在问这句话到底是真的还是假的? 如果说这句话是假的,那么“这句话是假的”是假的,也就是说这句话是真的。 如果说这句话是真的,那么“这句话是假的”是真的,也就是说这句话是假的。 因此称为悖论。出现悖论的关键是“自指”,或称“自引用”。在自然语言里,有自指的现象。 3、不完全性定理证明中的应用 (完全性)一阶算术N是不是完全的? (和谐性)一阶算术N的和谐性是不是在N上可以证明的? (完备性)在自然数模型中为真的语句,在一阶算术N是否是可证的? 对于以上性质,哥德尔给出的答案都是否定的。在证明中,主要的线索就是如何在形式语言N中构造出类似说谎者悖论的语句。这里要注意有两个层面:一阶算术N及其要刻划的自然数模型,一阶算术N是语法层面,自然数模型是语义层面。 4、不完全性定理证明中的应用 公式:“这个公式是不可证明的”,那么现在问这个公式可否证明? 如果说这个公式可以证明的话,那么“这个公式是不可证明的”这个公式是可证明的。但是根据前提这个公式是可以证明的,这样就会产生不一致。 故若此系统是一致的,则这个公式不能被证明,不是定理。 如果这个公式不可以被证明,那么“这个公式是不可证明的”是不可证明的,也说是说这个公式是真的,但是不可证明的。 5、哥德尔不完全性定理 要实现这个思路,关键的问题是在一阶算术N中,如何来构造“这个公式是不可证明的”。 以下是主要的思路: 通过哥德尔编码实现把N上的公式和公式序列编码成自然数模型中的自然数。 于是在自然数模型上,我们可以定义Pf(m,n),它成立当且仅当m是数码为n的公式在N中证明的数码。 反过来,自然数模型上的Pf(m,n)能不能在N上表达出来呢?为了做到这一点,哥德尔研究了自然数模型上的什么东西可以在N上表达出来。结果是:自然数模型上的递归函数都可以在N上表达出来。对应于N上的Pf(m,n) ,可以用N上的P(0m,0n)表达。 因为递归可计算等价于图灵可计算,因此检验一个函数是否是递归可计算的问题,等价于检验该函数是否是图灵可计算的,也就是可以用计算机编出程序的。
[此贴子已经被作者于2008-5-20 11:19:36编辑过]
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
2,600.586ms |