精华区文章阅读

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: [合集]也谈皇帝新脑（二）
发信站: 哈工大紫丁香 (2003年10月12日13:26:00 星期天), 站内信件

────────────────────────────────────────
rhine (有雨无风)                     于 Fri Sep  8 12:14:53 2000 说道:

────────────────────────────────────────
Mahan (蝙幅)                         于发信站: BBS 水木清华站 (Fri Oct 15 12:33:34 1999)
这个地方我的理解是这样的。因为看了有些时间了，可能记得不对。
P(k)是从现有的这个系统构造出来的，但是是不能从系统中得到证明。
但是，这并不表示P(k)等同与“系统不能证明的命题”这个表述。
因为，按彭的说法，作为认知的人是知道P(k)的真伪的，但是系统不能
知道，如果我们用我们的信息扩充系统，则系统能够认识P(k)；问题
是这个新的系统就必然有不同与P(k)但又无法用系统内的定义证明的
命题出现。
如果存在你提的逻辑谬误，则应该不能扩充系统解决这个命题，而产生
新的不可计算命题。
不知道这样理解对不对，回头再去看看书。

────────────────────────────────────────
rhine (有雨无风)                     于 Fri Sep  8 12:15:01 2000 说道:

────────────────────────────────────────
atfg (一个哭兮兮的思想凝成的幽灵)    于发信站: BBS 水木清华站 (Sat Oct 16 15:40:32 1999)
我想我们有个分歧，我认为Pk(k)就是说它自身不能被系统证明。
另外，关于扩充系统，我觉得即使把位于系统之外的知道命题真伪的人的信息扩充进去
，只要承认了系统的完备性，就不可能得出答案。我前一篇文章里，关于人是怎样知道
命题为真的那一段（其实也是彭的阐述），是由矛盾而否定了系统的完备。反过来
如果承认完备，就只能得出矛盾。这个问题的关键在于命题自身
的逻辑结构，它决定了不管以任何系统来推证，只要承认其完备性，就会得出矛盾。用
形式系统是这样，用人来推也是这样。所以我觉得，这个问题就算证明了形式系统的不
完备，也不能证明
人脑比形式系统更完备，所以不成其为算法局限的论据。

────────────────────────────────────────
rhine (有雨无风)                     于 Fri Sep  8 12:15:02 2000 说道:

────────────────────────────────────────
atfg (一个哭兮兮的思想凝成的幽灵)    于发信站: BBS 水木清华站 (Fri Oct 15 11:44:22 1999)
国庆仔细翻了一下“皇帝新脑”，觉得彭在数理方面确实是不愧名家的称号。
我看完了前四章关于logic和图灵机、算法（可计算性）的部分，本来打算
每一章写一篇自己的感受，结果发现这几章不好割裂开来，只好一块儿写了。
我觉得第二章和第四章其实说的是一个问题：电脑是算法的，或者说是图灵机，
只解决可计算性问题；而人脑是非算法的，思维有不可计算性（即彭所谓
直觉、“与柏拉图世界接触”）。其核心论据是图灵机停机问题和Goedel
证明的Hilbert规划不可实现。彭只简单的解释了一下图灵和哥德尔的论证
过程，因此我在看书的时候发觉有一点问题。我希望能找到图灵和哥德尔的
原著来看一看，但在yahoo上没找到。如果哪位大虾有，或者很熟悉这两个
问题，请不吝赐教。
Turing 的论文名叫On Computable Numbers with an application to the
                 Entscheidungsproblem，1936发表。
Goedel的论文名字我还不知道。
彭是这样解释哥德尔定理的：
哥德尔先用了极大的篇幅建立了一个严谨的
数学形式系统，该系统里所有命题都按“字典顺序”排列，并进行了编号。
其中命题是可以有自变量的。比如“我是人”自变量是我，“你是人”
自变量是你。那么“w是人”就可表示成P(w),假设这是第n号命题，其完整
表示是Pn(w)（n是脚标）。
命题的证明就是从公理开始正确推理得到的一串命题，如果这个命题串中出现
了待证的命题，则表示命题为真。同样，证明也可编号，第n个证明记为Tn。
考虑如下命题：~E x[Tx证明Pw(w)]，其中w为自然数（我用E表示存在符号，
                                                ~表示否定）
如果上述命题是第k号，则可记为Pk(w)。则当w=k时，得到命题Pk(k),其内容
为：~Ex [Tx证明Pk(k)]，即形式系统中的所有证明都不能证明Pk(k)为真。
假设形式系统是完备的（即“真的”等价于“有证明”），如果Pk(k)为假，
那么根据其内容，应当存在Pk(k)的证明，由完备性，Pk(k)
就是真的，矛盾。但如果Pk(k)为真，根据其内容，没有它的证明，它应该是
假的，也矛盾。所以形式系统不完备。
彭解释说：实际上Pk(k)是真的，但形式系统不完备，所以无法证明。然而人
可以如上（把“没有它的证明，它应该是假的”改成“没有它的证明，它可能
是真的”）证明Pk(K)为真。这就是形式系统（只解决可计算性问题）的局限，
而人脑没有这个局限。
一开始这一段搞得我很昏，但后来我发现问题关键在于对Pk(k)的构造。它在
论及它自身的证明，让我想到了一个很古老的logic徉谬：
       一个人说“我说的是假话”，问这句话是真是假。
我觉得那一堆搞得我头昏脑涨的Pk(w),Pk(k),Tx,其实就是说有个
命题A:形式系统中没有A的证明。
然后一切推理如上，也可以得出形式系统不完备得结论。
然后我发觉问题出来了：我把A写为
命题A：人脑找不到A的证明。
然后一切推理如上，结果结论是人脑也不完备。再沿袭彭的思路，用一个形式
系统，承认人脑不完备，很快可以由反证法证明A为真，所以这是人脑的局限，
形式系统是没有这个局限的。
显然这很荒唐。
我觉得问题在于Pk(k)（或者说命题A）本身被构造成徉谬，其逻辑结构决定了
它的不可证明，而不是形式系统的错。
其实我自己也认为人脑不仅仅是算法的，但我发觉如上来证明这一点是不对的。
我考虑了几天，觉得自己没有误解彭的叙述。然而Goedel定理自二十年代诞生，
必然有无数的数学家、逻辑学家检验过，似乎不应该是错的。因此我寄希望于
彭的叙述有问题，或是翻译有问题，所有我决定翻翻原著。
对logic敢兴趣的大虾们，我们不妨讨论一下。
next time...

────────────────────────────────────────
rhine (有雨无风)                     于 Fri Sep  8 12:15:05 2000 说道:

────────────────────────────────────────
softmagic (魔术师)                   于发信站: BBS 水木清华站 (Sun Oct 17 23:04:14 1999)
我想这么简单假设是不对了，歌德尔的证明包含了：~E x[Tx证明Pw(w)]是包含在
他所定义的形式系统中的一个命题。这样的形式系统是由它按照定义构造的足够
复杂的形式系统�
�

────────────────────────────────────────
rhine (有雨无风)                     于 Fri Sep  8 12:15:12 2000 说道:

────────────────────────────────────────
atfg (一个哭兮兮的思想凝成的幽灵)    于发信站: BBS 水木清华站 (Tue Oct 19 11:35:26 1999)
昨天在故纸堆里翻到一篇91年的论文，
The emperor's real mind:review of Roger Penerse's
The Emperor's New Mind...
作者 A.Sloman,the University of Birmingham
发表于 Artificial Intelligence,Vol.56,No.2/3
我想，Goedel 定理本是来说明 Hilbert 规划的不可实现的，
只是因为 Turing 沿袭其思路而提出了停机问题，所以成为了
AIers 和AI的反对者关心的东东。结果可能走得太远了点儿
我认为：Goedel 所说的不完备，是针对 Hilbert 规划而言的，
并不是在比较人脑和算法，说算法不如人脑完备。这种不完备对
Hilbert 是个打击，对AI则根本无所触动。
对这个问题，我已经没有开始那种兴趣了
在清华和智能中心的AI版和数学版我都贴了文章，有几个大虾
也发表了自己的意见

────────────────────────────────────────

Algorithm 版 (精华区)