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)表达。 因为递归可计算等价于图灵可计算，因此检验一个函数是否是递归可计算的问题，等价于检验该函数是否是图灵可计算的，也就是可以用计算机编出程序的。
进一步地，考虑自然数模型上的W(m,n)，它成立当且仅当m是A(x1)的数码，x在A(x1)中自由出现，而n是公式A(0m)在N中证明的数码。这里已经有“自引用”。
这个公式也是递归的，因此也是在N上可表达的。对应的就有N上公式W(0m,0n)。
基于公式W，就可以构造出我们需要的公式：
设A(x1):Ax2 ～ W(x1,x2) ，对应的编码为p。
则U为A(0p): Ax2 ～ W(0p,x2)即为所求。它在自然数模型上的解释是：对于任意自然数n，n不是U在N上证明的数码。这样U 就体现了自引用性质，可以看作它断言自身是不可证的。
可以证明：U和～ U在N上都是不可证明的。这就是哥德尔不完全性定理。
[此贴子已经被作者于2008-5-20 11:19:36编辑过]
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 理论计算机科学 』 → 说谎者悖论与哥德尔不完全性定理[原创]
(订阅本版)
2008/5/19 20:34:00
顶端 
说谎者悖论与哥德尔不完全性定理[原创](2696字) － chzhuang，2008年5月19日
新浪微博
