t**********k
发帖数: 511 | 1 逻辑和计算机
从原理上说，计算机是一个无比简单的东西，就是一个逻辑处理器，计算机所做的所有
工作最后都是转化成逻辑运算来执行的。所以，任何能进行基本逻辑运算（非，与，和
）的东西，都可以用来构成计算机。计算机的构想早在在17世纪就提出来了，不过只能
用机械方式。
第一个真正现代意义上的计算机是用电子管实现的，但是它的应用非常有限，庞大，奇
贵，速度慢，而且耗能巨大。还有一个致命的缺陷，就是可靠性好不了。
现在的CPU集成了几亿只器件，如果用电子管，意味着上亿个插件，上十亿个焊点，这
样复杂的东西没有办法保证质量，更不可能大规模生产。计算机的发展赖于集成电路的
进步。
计算机的广泛应用，以至于完全改变了人类的生活，其硬件基础是上个世纪前30年以爱
因斯坦为首的那一拨人做的，有了量子物理和相对论，才能有凝聚态物理，才能有集成
电路，接下来才可能有计算机，网络的广泛使用。
记得曾经在网上有人讨论爱因斯坦和爱迪生哪一个更牛，这实在有点过分，两个人完全
不在一个档次，而且差得很远。爱因斯坦是一个科学家，《维基百科》说也是一个思想
家，我以为不错，他奠定了现代物理学的基础，对人类产生了根本的影响，极大地改变
了人类的生活以及我们对这个世界的理解，《时代杂志》把他评为上个世纪最伟大的人
物，毫不过分。
爱迪生只是一个发明家，发明了白炽灯，留声机这一类应用的产品而以。他的那一套发
明的方法已经过时，产品也没有人用了。比如美国已经不生产白炽灯，将来的照明肯定
是用发光二极管，效率接近于完美，寿命极长，这也是建立在爱因斯坦的理论基础之上
的。
总的说来，科学家对人类的影响是最大的，永久的，什么政治家，帝国不过是过眼云烟
罢了。
计算机软件的基础是数理逻辑，它可以看成是上个世纪数学取得的最重要的进展，几乎
改变了数学的整个面貌。建立的时间和现代物理基本上在同时，计算机科学可以看成是
数理逻辑在这个领域的一个具体运用。当然，一般的“码工”可能用不着知道数理逻辑
，那是因为有人为他们弄出了某种计算机语言，但对于那些弄出语言的人，没有数理逻
辑作为基础是不可能。
这个问题这样来讲也许容易一点，计算机的界限在哪里。不能说计算机能做什么，因为
它能做的事太多了，只能说计算机不能做什么，或者说是人工智能的问题。这个词好像
容易引起误解，因为要严格定义人工智能就得定义什么是人的智力，或者思维，而人的
思维是一个无法定义的东西，我们弄不清楚。
这个问题得从数学方面来探究，因为计算机说到底是一个逻辑处理器，这是计算机的硬
件所决定的，无法改变，这个问题就就能变成：逻辑能干什么？
这个问题主要由三个人的工作而得以阐明，弗雷格，罗素，哥德尔。这是数学最奇妙的
一点，数学的一些基础研究在开始的时候，根本看不到有什么用处，只是一些游戏式的
东西，或者哲学问题。但是，后来的发展却使这些东西变得有极大的实用价值。那个时
候的人根本就不知道什么是现在的计算机。
弗雷格的名字恐怕大多数人都没有听说，但他却是数理逻辑的奠基人，被认为是亚里士
多德以后最伟大的逻辑学家。罗素有了集合论这个工具，在弗雷格的基础之上想要完成
一件无比宏伟的工作，想把全部数学的基础建立在逻辑的上面。当然，罗素并不是要为
计算机做什么，他不怎么不关心这种事，而是出自于一种哲学上的思考，这就是所谓的
奥卡姆剃刀。
在弗雷格之前，数学和逻辑可以说是分开的东西。如果数学是一个假设，逻辑是另一个
假设（不是所有的人都承认数学只是一个假设的，这个问题我在谈维特根斯坦时比较详
细地讨论过，这里不妨当做一个假设接受下来，并不影响下面的讨论），那么把它们变
成一个东西就有极大的价值，因为奥卡姆剃刀说：“若无必要，勿增实体”，少一个假
设，自然出错的可能将会减少，这可以说是科学的一个基本原则。当然，如果数学就是
反映了客观实在，那么更应该能够统一。
但是，罗素失败了，因为他发现了所谓的罗素悖论，到了哥德尔不完备定律做了结论，
那不可能成功，就像哥德尔所说：“有些事实被认知为真，但不必然可证。”当然，要
是数学不是必然可证的话，那么逻辑怎么能是数学的基础。虽然罗素失败了，但是这些
人的努力却极大地推动了数学和哲学的发展，可以认为构成了上个世纪数学和哲学的主
流，而且，他们的工作在后来就构成了计算机科学的基础。
图灵被广泛地认为是计算机科学之父：“图灵在他的重要论文《论可计算数及其在判定
问题上的应用》，对哥德尔1931年在证明和计算的限制的结果作了重新论述，他用现在
叫做图灵机的简单形式裝置代替了哥德尔的以通用算术为基础的形式语言。”《维基百
科》这段话大致说明了图灵和哥德尔的关系，图灵不过是把哥德尔的定律用在计算机上
（图灵机可以看成是一种理想计算机），这种一致性的背后就是图灵机和形式语言说到
底都是逻辑。
图灵最重要的工作是：“停机问题（halting problem）是逻辑数学中可计算性理论的
一个问题。通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运
行的问题。该问题等价于如下的判定问题：给定一个程序 和输入 , 程序 在输入 下是
否能够最终停止。
艾伦•图灵在1936年证明了，一个可以解决停机问题的通用算法是不存在的。这
个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上
是不可判定问题。这是最早提出的决定性问题之一。
用数学语言描述，则其本质问题为: 给定一个图灵机 T，和一个任意语言集合 S，是否
T 会最终停机于每一个 。其意义相同于可确定语言。显然任意有限 S 是可判定性的
，可数的（countable）S 也是可停机的。
停机问题本质是一阶逻辑的不自洽性和不完备性，类似的命题有理发师悖论、全能悖论
等。”（本篇所有引用都来自《维基百科》，例外注明）
这里的理发师悖论、全能悖论都是罗素悖论的另一些表达形式。
这里就我自己的理解来解释一下，你要计算机干一个活，必须要知道它能不能胜任，也
就是在有限的时间里能不能得到一个结果，不然的话，就是眼前一片黑，所谓理论的指
导作用就是这个意思，实际上就是要了解计算机一个什么东西，我想这一点的重要性不
难理解。
毫无疑问，语言是人类最重要，也是最伟大的工具，但是，仍然只是一个工具，用于人
与人之间的沟通。那么对于一个工具来说，最要紧的就是知道它能够做什么，也许更重
要的是要知道它不能做什么，比如说你知道汽车不能在水里开肯定比能开多快要重要得
多。在语言哲学家看来，过去哲学的荒谬之处就在于对语言泛用，而根本不知道语言的
局限性，就像他们一直在水里开汽车，还在宣称感觉好极了，而且还边开边领悟到了这
个世界的真谛。
语言哲学和停机问题是有关联的，它们都是要企图找到一条线，那些是做不到的事情，
一个是针对语言，另一个是针对计算机，而且都是以数理逻辑作为基础的，这一点也决
不是偶然的。
在维特根斯坦看来，我们真正能理解的，能够达到一致的东西都必须以逻辑作为基础，
因为逻辑是一个天生的东西，大家都是一样的。除此以外，达到一致是不可能的，就像
你不可能说清楚什么是漂亮。
如果我们认可维特根斯坦关于语言只能确实地表达逻辑结构，那么从计算机的角度来理
解语言就会容易一些。如果一些计算机的程序和数据库是一模一样，那么当然，对同一
个问题它们的结论也必然是同样的。所以也许可以说，人与人的不同就在于各自程序和
数据库并不一样，这个不一样可以认为是与遗传和早年的经历和教育有关，恐怕没有两
个人可能一模一样，所以说，人与人的不同是不可以避免的。用维特根斯坦的话来说，
人与人的不同就在于各自的原子命题不同，出发点不同，所以各人眼中的世界是不可能
一样的。
而哥德尔告诉我们，在逻辑的基础之上，我们不能建立一个无所不包而完美的数学体系
。用图灵的话来说，一个可以解决停机问题的通用算法是不存在的。这个问题可以这样
来看，我们要让计算机解决哥德巴赫猜想（任一大於2的偶數，都可表示成兩個質數之
和），写了一个程序，从小到大尝试将这样的偶数分成两个素数的和。如果它遇到一个
不能被分解为两个素数之和的 偶数，它就停机并输出这两个偶数；否则，它就一直运
行下去。这样一来，问题就可以变成判断计算机能不能停机，知道计算机会不会停机就
是解决这个猜想。很多数学猜想实际上都可以转化成停机问题，所以说，如果有一个通
用办法，我们就可以证明很多数学猜想。
但是，图灵告诉我们，没有通用算法，只能有针对各个不同的问题的办法，当然，如果
我们找到了一个办法来判断哥德巴赫猜想的停机问题，就是解决了这个猜想。由于计算
机是一个逻辑运算的机器，这样我们就能理解哥德尔的说法，不是说哥德巴赫猜想不能
用逻辑证明（所谓证明就是逻辑），而只是说我们不能建立一个无所不包而完备的数学
体系。那么当然，在逻辑的基础之上，我们也不能建立一个理想的语言体系来说出所有
的东西，因为数学可以看成是一种语言，而且是比日常语言要简单得多。
进一步来说，对于计算机，娼妓和淑女的区别仅仅是两个字的代码不同，不可能有自己
的好恶感。从这个角度，我们也容易理解伦理学，美学都是与逻辑无关的东西，因此达
不到一致，就根本不是哲学所应该讨论的问题。就像罗素所说，所谓好坏与美丑一样，
都是各人自己的喜爱，就像萝卜白菜，
逻辑是一个有限的东西，所以计算机不可能什么都能做；同样，逻辑的有限也就造成了
语言的有限，用语言表达的所谓绝对真理一定有逻辑上的毛病。这种真理我们无法断定
存不存在，但就是有，也是不能用语言说出来的。因此，人的所知非常有限，我们只能
依靠逻辑，而逻辑有限。
我们也许还能这样说，如果我们能构造一台完美的计算机，能够解决一切数学问题，那
么当然这台计算机可以是一个绝对的参照，其它计算机都要以它来确定对错。但是，哥
德尔告诉我们在逻辑上这是不可能的；同理，也就不可能有一个人能做到这一点，没有
人能知道什么绝对真理，而让我们可以无条件的追随。那么当然，怀疑和批判就是我们
永远必须的。
当然，如果是神那就是另一个故事了，因为神是超人的，宗教与逻辑无关。有人有另一
种说法，神其实是靠人来解释的，也可以说是人造的。
所以说，计算机不但不可能是莎士比亚，也不可能写出《红楼梦》，而且，甚至有些数
学理论都不是用计算机能得到的，得依靠人的直觉，人的创造能力不能是逻辑的，爱因
斯坦那种天才人物永远是我们需要的。
哥德尔是一个奇人，极为低调，家人从别人那里才知道他在数学界的地位。很多人认为
他是上个世纪最伟大的数学家，被誉为数学上的爱因斯坦。与他同时的另一个大天才诺
依曼曾经在那个问题上作过不小的努力，但却没有成功。
“在普林斯頓時，哥德爾和愛因斯坦成了很好的朋友。後人常將他們比較。哥德爾和愛
因斯坦都在自己的範疇有極為重大的貢獻，很聰明，有好奇心，直率。但愛因斯坦性格
開朗外向，這點和哥德爾大相径庭。愛因斯坦的死對哥德爾的情緒有很大打擊。”
下面转录几段哥德尔的轶事（以下三段不是来自《维基百科》）：“哥德尔曾透露他和
爱因斯坦的友谊是基于他们之间观点的不同而不是一致。哥德尔晚年在广义相对论里取
得重要成果，并于1951年被授予爱因斯坦奖。爱因斯坦晚年说：“我自己的工作没啥意
思，我来上班就是为了能有同哥德尔一起散步回家的荣幸。”我总有些好奇，这二个天
才在一起会谈些什么？我们能不能理解？
不过“罗素在普林斯顿访问时，每周都去爱因斯坦家，同爱因斯坦，哥德尔，泡利讨论
。他流露出失望：“他们仨都是流亡的犹太人，也都见多识广，但对形而上学都有德国
倾向。哥德尔根本就是个柏拉图主义者。"其实哥德尔不是犹太人。”哥德尔相信有神
论，而罗素一直对基督教持批评态度，重要原因就是柏拉图的哲学是基督教哲学（经院
哲学）直接来源，而批判柏拉图则被罗素视为自己的终身任务。
“数 学家、经济学家摩根斯顿和爱因斯坦同是哥德尔入美国籍的证人（那时入籍要证
人）。去移民局的路上，哥德尔号称可以证明美国宪法逻辑上会导致独裁。爱因斯坦
和摩根斯顿都建议哥德尔不要在移民官面前提这事，但哥德尔还是提了。爱因斯坦吸引
了移民官注意力，哥德尔顺利变成公民。”这么伟大的一个逻辑学家有这种看法，恐怕
是不错的。
“他自幼多病，而且從小就患了强迫症（疑病症）。他還患過抑鬱症。後來他在普林斯
頓的醫院絕食而死，因為他認為那些食物有毒。”“哥德爾的妻子Adele Nimbursky 比
哥德爾大六歲。哥德爾21歲兩人認識時，Adele 已婚且在夜總會 Der Nachtfalter 工
作。他們的婚姻遭到哥德爾家人反對，但有情人終成眷屬，在1938年9月20日結婚。他
們沒有小孩。”天才看来和我们这些普通人相距甚远。
我去过普林斯顿高等研究院，那是这二个天才最后工作的地方。那是一个初春，阳光灿
烂，但树荫处仍然可见积雪，春风依旧带着阵阵寒意。就像那些美国漂亮的校园，那里
开阔而人迹稀少，不由有了一些感叹，这二人的工作完全改变了世界，改变了每一个人
生活方式，但是，这里却如此寂寥！
不过这倒是与他们秉性相符，淡漠甚至有些厌恶名利，安安静静做自己喜欢的事情最好
。不过我毫无疑问地相信，只要这个世界上还存在科学和数学，他们就绝不会被人遗忘！ |
s*******y
发帖数: 46535 | 2 德兄关注的东西变了
【在 t**********k 的大作中提到】
: 逻辑和计算机
: 从原理上说，计算机是一个无比简单的东西，就是一个逻辑处理器，计算机所做的所有
: 工作最后都是转化成逻辑运算来执行的。所以，任何能进行基本逻辑运算（非，与，和
: ）的东西，都可以用来构成计算机。计算机的构想早在在17世纪就提出来了，不过只能
: 用机械方式。
: 第一个真正现代意义上的计算机是用电子管实现的，但是它的应用非常有限，庞大，奇
: 贵，速度慢，而且耗能巨大。还有一个致命的缺陷，就是可靠性好不了。
: 现在的CPU集成了几亿只器件，如果用电子管，意味着上亿个插件，上十亿个焊点，这
: 样复杂的东西没有办法保证质量，更不可能大规模生产。计算机的发展赖于集成电路的
: 进步。
|
R******k
发帖数: 4756 | 3 有一些观点不敢苟同，但不得不赞叹德兄知识的广博。
另外，高等研究院其实和普林斯顿大学没有啥关系，把普林斯顿放在它的名字里面实在
是便宜了普林斯顿大学~ |
B****n
发帖数: 11290 | 4 還是有點關係的
不說研究上有密切的合作 seminar會互相出席
普林斯頓還曾經出借辦公室給他們 說起來還是有些淵源的
【在 R******k 的大作中提到】
: 有一些观点不敢苟同，但不得不赞叹德兄知识的广博。
: 另外，高等研究院其实和普林斯顿大学没有啥关系，把普林斯顿放在它的名字里面实在
: 是便宜了普林斯顿大学~
|
B****n
发帖数: 11290 | 5 直觀上來看 需要無限步驟的事 都無法能用電腦解決
所以所謂停機問題是否是要先把無限的問題轉成有限的呢?
【在 t**********k 的大作中提到】
: 逻辑和计算机
: 从原理上说，计算机是一个无比简单的东西，就是一个逻辑处理器，计算机所做的所有
: 工作最后都是转化成逻辑运算来执行的。所以，任何能进行基本逻辑运算（非，与，和
: ）的东西，都可以用来构成计算机。计算机的构想早在在17世纪就提出来了，不过只能
: 用机械方式。
: 第一个真正现代意义上的计算机是用电子管实现的，但是它的应用非常有限，庞大，奇
: 贵，速度慢，而且耗能巨大。还有一个致命的缺陷，就是可靠性好不了。
: 现在的CPU集成了几亿只器件，如果用电子管，意味着上亿个插件，上十亿个焊点，这
: 样复杂的东西没有办法保证质量，更不可能大规模生产。计算机的发展赖于集成电路的
: 进步。
|
l*****n
发帖数: 125 | 6 停机问题和哥德尔的不完备定理是不同的问题，前者是关于undecidability, 后者是关
于incompleteness，虽然直观上来说，他们的证明都和理发师悖论有关。
另外，first order logic是sound and complete的，只不过undecidable, 你说的 “
一阶逻辑的不自洽性和不完备性”是完全不存在的。哥德尔的不完备定理并不是说FOL
is incomplete，而是说任何可以包含peano arithmetic的证明系统是不完备的，这完
全是两回事。 |
x*******a
发帖数: 57 | 7 你确定爱因斯坦的相对论和凝聚态有关么。。。
还能把爱因斯坦直线联系到计算机上么。。。
当然我是小爱的big fans |
p***r
发帖数: 20570 | 8 没啥大关系，除了一些个别的小地方，比如自旋轨道耦合。。。
【在 x*******a 的大作中提到】
: 你确定爱因斯坦的相对论和凝聚态有关么。。。
: 还能把爱因斯坦直线联系到计算机上么。。。
: 当然我是小爱的big fans
|
s******t
发帖数: 2511 | 9 神马情况？主贴还没看，敢情楼主说的是Bose-Einstein统计？
【在 x*******a 的大作中提到】
: 你确定爱因斯坦的相对论和凝聚态有关么。。。
: 还能把爱因斯坦直线联系到计算机上么。。。
: 当然我是小爱的big fans
|
x*******a
发帖数: 57 | 10 展开说说， 好久没接触， 真不记得自旋耦合有相对论的东西
【在 p***r 的大作中提到】
: 没啥大关系，除了一些个别的小地方，比如自旋轨道耦合。。。
|
|
|
j******f
发帖数: 825 | 11 美学和伦理学与逻辑无关吗？不尽然吧。
计算机的基本结构建立在逻辑基础上不能说明它就不能有好恶。
人由单个细胞构成，单个细胞没有好恶，建立在它们之上的人就有，这又如何解释呢？ |
s******t
发帖数: 2511 | 12 薛定谔方程的相对论形式是狄拉克方程，Dirac equation里有spin orbit coupling，
你看一下4.6节
http://www.phy.ohiou.edu/~elster/lectures/advqm_4.pdf
【在 x*******a 的大作中提到】
: 展开说说， 好久没接触， 真不记得自旋耦合有相对论的东西
|
x*******a
发帖数: 57 | 13 如果没记错， 二次量子化那是场论了吧。
貌似对于大部分的凝聚态物理都不会用的，至少我曾经做过的那部分，还有据了解
mosfet的知识， 还是用的经典的泊松方程， 和薛定谔方程加微扰解出来的能带论
【在 s******t 的大作中提到】
: 薛定谔方程的相对论形式是狄拉克方程，Dirac equation里有spin orbit coupling，
: 你看一下4.6节
: http://www.phy.ohiou.edu/~elster/lectures/advqm_4.pdf
|
s**********n
发帖数: 3199 | 14 没看楼主原帖－－cs的表示有洁癖没法读．．．开始觉得你也是cs的，后来看到peano
arithmetic觉得你还是数学系底，，，
目测楼主所谓自洽不是sound把，是指consistency吧．．．当然consistency完全不足
与soundness,completeness并列，从cs角度，重要性难望soundness／completeness项
背。
洁癖再为你补充下：soundness指whatever provable (in the proof system) is
indeed semantically true (according to the logic) (completeness反之，any
truth is also provable)，严格说，soundness/completeness一起组成任何逻辑系统
的最重要性质－－即是否存在proof system that is sound and complete；稍次是
decidability涉及有无procedure可以在某proof system里能derive (prove) 所有
statement的semantics。soundness/completeness/decidability都是逻辑系统的meta
properties，相比之下，consistency是弱很多的object property，具体statements在
具体proof system下的表现而已。也无怪楼主拎不清某个proof system incomplete和
fol关系，莫说入室，还未升堂咯。
FOL
【在 l*****n 的大作中提到】
: 停机问题和哥德尔的不完备定理是不同的问题，前者是关于undecidability, 后者是关
: 于incompleteness，虽然直观上来说，他们的证明都和理发师悖论有关。
: 另外，first order logic是sound and complete的，只不过undecidable, 你说的 “
: 一阶逻辑的不自洽性和不完备性”是完全不存在的。哥德尔的不完备定理并不是说FOL
: is incomplete，而是说任何可以包含peano arithmetic的证明系统是不完备的，这完
: 全是两回事。
|
s******t
发帖数: 2511 | 15 狄拉克方程是高量的内容，尚未场论。
应用物理可能不太在意纯理论的推导。具体凝聚态的方法我不太清楚。
比如，从应用来说，自旋耦合可用“改良薛定谔方程”，手动在Hamilton量中加入自旋
耦合项的，没问题，也可以得到精细结构，解释Zeeman effect，可以回忆一下曾谨言
的教科书，但是这种方法从纯理论上来说很ugly。
狄拉克方程是爱因斯坦流，那种极具美学色彩的方程推导。从相对论协变导出方程，带
入相对论协变的电动力学四维矢量，就可以得到自旋轨道耦合项，解释精细结构，完美
地统一了special relativity，量子力学和电子自旋。这还不算，Dirac直接顺藤摸瓜
，预测了正电子。狄拉克帅呆了。
【在 x*******a 的大作中提到】
: 如果没记错， 二次量子化那是场论了吧。
: 貌似对于大部分的凝聚态物理都不会用的，至少我曾经做过的那部分，还有据了解
: mosfet的知识， 还是用的经典的泊松方程， 和薛定谔方程加微扰解出来的能带论
|
z*****3
发帖数: 1793 | 16 总算是有懂的人写篇科普文章了，有些码农真的是恶心，明明不懂，非要装懂。
谢谢LZ写那么长。我人懒，肯定不会话时间写那么长的科普长文。 |
z*****3
发帖数: 1793 | 17 首先，halting problem和 Godel's incompleteness theorem必然联系。Godel讲的就
是undecidability.我想你是没上过symbolic logic. 要学Godel's incompleteness
theorem必须先学decidability和undecidability。
http://en.wikipedia.org/wiki/On_Formally_Undecidable_Propositio
这篇文章就是出处。
其次，这里的不自洽性是inconsistent，和soundness没关系。Godel 我上symbolic
logic的时候老师是这样翻译的。soundness应该翻译成可靠性。
所以他说的是对的，
“Any effectively generated theory capable of expressing elementary
arithmetic cannot be both consistent and complete”
http://en.wikipedia.org/wiki/Gödel%27s_incompleteness_theo
这是第一定理的部分内容。
而是说任何可以包含peano arithmetic的证明系统是不完备的。这是第二定理的内容。
“For any formal effectively generated theory T including basic arithmetical
truths and also certain truths about formal provability, if T includes a
statement of its own consistency then T is inconsistent.”
一般人能知道Godel's incompleteness theorem 就不容易了。很幸运的是我们有幸知
道其实是有两个定理。我唯一比较遗憾的是数理逻辑的基础够了，学校有个老师开专门
开了一门讲Godel’s incompleteness的课，我毕业来美了- -！人生有时候就是那样，
是如此接近，又如此遥远。
另外，可以利用Godel's incompleteness theorem 证明halting problem is
undecidable.具体证明我找不到了。主要原因是都利用了对角线方法，本质上一样。说
一下，为什么Godel's要说包含PA,因为Godel对每个logic 表达式用自然数编码（Godel
coding），没PA没法搞。
FOL
【在 l*****n 的大作中提到】
: 停机问题和哥德尔的不完备定理是不同的问题，前者是关于undecidability, 后者是关
: 于incompleteness，虽然直观上来说，他们的证明都和理发师悖论有关。
: 另外，first order logic是sound and complete的，只不过undecidable, 你说的 “
: 一阶逻辑的不自洽性和不完备性”是完全不存在的。哥德尔的不完备定理并不是说FOL
: is incomplete，而是说任何可以包含peano arithmetic的证明系统是不完备的，这完
: 全是两回事。
|
e**5
发帖数: 645 | 18 最新一期时代杂志做了个专题 好像叫 the age 2 of reason
我没细读呢 猜测与大数据 深度问答 等等有关
【在 t**********k 的大作中提到】
: 逻辑和计算机
: 从原理上说，计算机是一个无比简单的东西，就是一个逻辑处理器，计算机所做的所有
: 工作最后都是转化成逻辑运算来执行的。所以，任何能进行基本逻辑运算（非，与，和
: ）的东西，都可以用来构成计算机。计算机的构想早在在17世纪就提出来了，不过只能
: 用机械方式。
: 第一个真正现代意义上的计算机是用电子管实现的，但是它的应用非常有限，庞大，奇
: 贵，速度慢，而且耗能巨大。还有一个致命的缺陷，就是可靠性好不了。
: 现在的CPU集成了几亿只器件，如果用电子管，意味着上亿个插件，上十亿个焊点，这
: 样复杂的东西没有办法保证质量，更不可能大规模生产。计算机的发展赖于集成电路的
: 进步。
|
l*****n
发帖数: 125 | 19
peano
我也是CS的。。。
我没有在翻译楼主的话，也没有把自洽翻译成sound，只是描述一个事实：FOL is
sound and complete.
Consistency一般是用来描述一个theory的，所以“一阶逻辑的不自洽性”就是个伪命
题，懒得说了。。
解释的挺好，可以再补充一点：一阶逻辑的完备性和哥德尔不完备性定理中的完备性是
两个不同的概念，前者是指一个证明系统，后者是指一个theory
【在 s**********n 的大作中提到】
: 没看楼主原帖－－cs的表示有洁癖没法读．．．开始觉得你也是cs的，后来看到peano
: arithmetic觉得你还是数学系底，，，
: 目测楼主所谓自洽不是sound把，是指consistency吧．．．当然consistency完全不足
: 与soundness,completeness并列，从cs角度，重要性难望soundness／completeness项
: 背。
: 洁癖再为你补充下：soundness指whatever provable (in the proof system) is
: indeed semantically true (according to the logic) (completeness反之，any
: truth is also provable)，严格说，soundness/completeness一起组成任何逻辑系统
: 的最重要性质－－即是否存在proof system that is sound and complete；稍次是
: decidability涉及有无procedure可以在某proof system里能derive (prove) 所有
|
l*****n
发帖数: 125 | 20 Godel的定理简单的说就是证明了"arithmetic is not recursively enumerable."
RE是比decidability弱一些的一个性质，并不要求程序终止，也可以叫做
semidecidable。所以证明了arithmetic不是RE的当然也就证明了arithmetic不是
decidable的。所以，理解Godel的定理需要知道什么是RE，当然和decidability也有关
系，但是说要学Godel's incompleteness theorem必须先学decidability和
undecidability，个人觉得还是未必，呵呵。
至于证明，我也说了，halting problem和Godel的定理有类似的地方，都可以用到对角
线方法（也可以不用，两者都有不止一种证法），本质上都是在构造逻辑悖论，但并不
代表他们描述的是同一个性质，一个是关于RE，一个是关于decidability。
关于inconsistency，看来是我表述不清，每个人都以为我把自洽性当成soundness，其
实我并没有这个意思。我没提inconsistency是因为这是一个关于theory的概念，而不
是关于FOL本身的，所以我说过了，楼主说FOL是inconsistent是一个伪命题，连基本概
念都还没搞清楚。至于soundness，我只是陈述一下FOL的soundness而已，不过我确实
不知道soundness该怎么翻成中文。。
你引用的wiki上的关于哥德尔不完备定理没有问题，和我说的并不矛盾。FOL的完备性
也是哥德尔证明的，称为Godel's completeness theorem，这个和哥德尔不完备性定理
是两个概念，虽然都用completeness这个词。前者是指逻辑系统是完备的，后者是指描
述arithmetic的theory是不完备的。FOL的undecidability可以用halting problem来证
，也是Church-Turing定理的推论。
另外，我在CS系和数学系都学过逻辑课，也学过一些model theory和finite model
theory.
【在 z*****3 的大作中提到】
: 首先，halting problem和 Godel's incompleteness theorem必然联系。Godel讲的就
: 是undecidability.我想你是没上过symbolic logic. 要学Godel's incompleteness
: theorem必须先学decidability和undecidability。
: http://en.wikipedia.org/wiki/On_Formally_Undecidable_Propositio
: 这篇文章就是出处。
: 其次，这里的不自洽性是inconsistent，和soundness没关系。Godel 我上symbolic
: logic的时候老师是这样翻译的。soundness应该翻译成可靠性。
: 所以他说的是对的，
: “Any effectively generated theory capable of expressing elementary
: arithmetic cannot be both consistent and complete”
|
|
|
r*********o
发帖数: 14 | |
g**s
发帖数: 2331 | 22 建议改名字，《数学,哲学与计算机艺术》。收藏了。
强迫症的人，智商高的居多。 |
w*****m
发帖数: 20421 | 23 满锅糊涂没个豆啊，这到底要讲什么啊，就是个马工命
别把自己当科学家使了。 |
w***r
发帖数: 7173 | 24 在这个楼里回复的ID 我发现都是牛人。
所以，我来搭便车。 |
z*****3
发帖数: 1793 | 25 Agree 大部分。最后纠正Church-Turing thesis不是定理(theorem)。是一个假设。这
是我们上课的时候特别强调的。是没办法证明的，所以不能说是定理。也就是说，如果
你相信Church-Turing thesis，可以推论出FOL的undecidability。
【在 l*****n 的大作中提到】
: Godel的定理简单的说就是证明了"arithmetic is not recursively enumerable."
: RE是比decidability弱一些的一个性质，并不要求程序终止，也可以叫做
: semidecidable。所以证明了arithmetic不是RE的当然也就证明了arithmetic不是
: decidable的。所以，理解Godel的定理需要知道什么是RE，当然和decidability也有关
: 系，但是说要学Godel's incompleteness theorem必须先学decidability和
: undecidability，个人觉得还是未必，呵呵。
: 至于证明，我也说了，halting problem和Godel的定理有类似的地方，都可以用到对角
: 线方法（也可以不用，两者都有不止一种证法），本质上都是在构造逻辑悖论，但并不
: 代表他们描述的是同一个性质，一个是关于RE，一个是关于decidability。
: 关于inconsistency，看来是我表述不清，每个人都以为我把自洽性当成soundness，其
|
l*****n
发帖数: 125 | 26 No... 你说的是Church-Turing Thesis, 我说的是Church-Turing Theorem, 1936年就
证明了的，两者不是一回事。呵呵，我也给个wiki链接吧：
http://en.wikipedia.org/wiki/Entscheidungsproblem
Church-Turing Theorem的内容是：The validity of FOL is RE-complete. 所以
undecidability就是一个很简单的推论，另外一个推论是：The satisfiability of
FOL is not recursively enumerable.
【在 z*****3 的大作中提到】
: Agree 大部分。最后纠正Church-Turing thesis不是定理(theorem)。是一个假设。这
: 是我们上课的时候特别强调的。是没办法证明的，所以不能说是定理。也就是说，如果
: 你相信Church-Turing thesis，可以推论出FOL的undecidability。
|
z*****3
发帖数: 1793 | 27 这是我第一次看见有人把判定问题(Entscheidungsproblem)称为Church-Turing
Theorem。你这样非常容易混淆。
我学lambda calculus和turing machine 的时候都是说说Entscheidungsproblem。也许
是老师不同吧。
【在 l*****n 的大作中提到】
: No... 你说的是Church-Turing Thesis, 我说的是Church-Turing Theorem, 1936年就
: 证明了的，两者不是一回事。呵呵，我也给个wiki链接吧：
: http://en.wikipedia.org/wiki/Entscheidungsproblem
: Church-Turing Theorem的内容是：The validity of FOL is RE-complete. 所以
: undecidability就是一个很简单的推论，另外一个推论是：The satisfiability of
: FOL is not recursively enumerable.
|
a*o
发帖数: 25262 | 28 从原理上说，停机问题是一个无比简单的东西，把插头一拔，问题就解决了。 |
l*****n
发帖数: 125 | 29 我学的时候两个都讲，Entscheidungsproblem是一个问题，Church-Turing theorem对
这个问题给出了否定的答案，我觉得挺通顺的啊哈哈
这是我第一次看见有人把判定问题(Entscheidungsproblem)称为Church-Turing
Theorem。你这样非常容易混淆。我学lambda calculus........
【在 z*****3 的大作中提到】
: 这是我第一次看见有人把判定问题(Entscheidungsproblem)称为Church-Turing
: Theorem。你这样非常容易混淆。
: 我学lambda calculus和turing machine 的时候都是说说Entscheidungsproblem。也许
: 是老师不同吧。
|
t******5
发帖数: 46 | |
|
|
y**e
发帖数: 49 | 31 I would suggest read some history on research of mathematics foundation.
many claims here are simply not what happened. by the way, the presentation
seems illogical to me |
R******k
发帖数: 4756 | 32 我在这个楼里面发了两个贴，是不是更牛一些？
【在 w***r 的大作中提到】
: 在这个楼里回复的ID 我发现都是牛人。
: 所以，我来搭便车。
|
w***r
发帖数: 7173 | 33 你比别人牛两倍。
【在 R******k 的大作中提到】
: 我在这个楼里面发了两个贴，是不是更牛一些？
|
p***r
发帖数: 20570 | 34 有一个非相对论的唯象半经典解释，就是说以电子为静止参照系，电子能感受到核的磁
场，这样电子自旋会受这个磁场的影响。比较严格的推导还是得用量子场论。
【在 x*******a 的大作中提到】
: 展开说说， 好久没接触， 真不记得自旋耦合有相对论的东西
|
