https://groups.google.com/group/swarmagents_ai/

Presentation on theme: "https://groups.google.com/group/swarmagents_ai/"— Presentation transcript:

1 https://groups.google.com/group/swarmagents_ai/
Kurt Godel [ ] 资料来源：互联网，《哥德尔》by王浩 整理：Miner （2009.4）

2 生平简介 1906, begin 1924. 维也纳大学，打算专攻理论物理
不是犹太人，家人称其为“为什么先生” 1924. 维也纳大学，打算专攻理论物理 定期参加石里克组织的维也纳小组的聚会(但见解不同)，转向数学 1929. 博士论文：哥德尔完备性定理 （1928年才开始研究数理逻辑） 1930.柯尼斯堡会议,哥德尔宣布了不完全性定理，会后哥德尔与冯诺依曼私下里谈话，冯诺依曼当下就懂得了哥德尔（第一定理）的证明。在11月20日给哥德尔的信里，冯诺伊曼说：“我把您在科尼斯堡的结果告诉了艾哈德·施密特，他对此欣喜若狂。像我一样，他也认为这是长时间以来最伟大的逻辑发现。” 1931. 不完备性定理发表 1942. 开始与爱因斯坦( )频繁往来，直至后者去世 1943. 主要精力由数理逻辑转向哲学 (有神论,仿效莱布尼茨而不是斯宾诺莎) 研究莱布尼茨；1959年起系统研读胡塞尔 在哲学领域他说过他从未得到他想找的东西。 1948年，入籍考试时试图证明美国宪法允许的行为何以会导致法西斯主义，爱因斯坦和法官一起努力让哥德尔安静下来，以免他继续就他的“发现”发表详细而冗长的谈话 。 1951年2月，哥德尔卧病在床，奥本海默（R. Oppenheimer）告诉临床医生“你的病人是亚里士多德以来最伟大的逻辑学家”。 1978年3月3日的追悼会上，外尔说，“承认哥德尔是两千五百年间唯一能不带夸耀地说‘亚里士多德和我’的人，其实是不为过的”。 1978, end 去世前4周，他说：“我失去作肯定判断的能力了，我只能作否定判断。”

3 普林斯顿 哥德尔和爱因斯坦

4 哥德尔完备性定理 1929, 博士论文，一阶谓词演算中所有逻辑上有效的公式都是可以证明的
命题演算的完全性已由美国数学家Post在1921年给出证明 具体证明参见任何一本数理逻辑教材

5 哥德尔不完备性定理 1931, incompleteness theorems
“On formally undecidable propositions of Principia Mathematica and related systems 数学原理中的形式不可判定命题及有关系统” for any computable axiomatic system that is powerful enough to describe the arithmetic of the natural numbers (e.g. the Peano axioms or ZFC), that:   1. If the system is consistent, it cannot be complete. (This is generally known as the incompleteness theorem.)   2. The consistency of the axioms cannot be proved within the system. 第一不完全定理:设系统S包含有一阶谓词逻辑与初等数论,如果S是一致的(无矛盾),存在则下文的T与非T在S中均不可证. 第二不完全定理:如果系统S含有初等数论，当S无矛盾时，它的无矛盾性不可能在S内证明。

6 Peano axioms （皮亚诺公设） 数学家皮亚诺提出的关于自然数的五条公理系统。根据这五条公理可以建立起一阶算术系统，也称皮亚诺算术系统。   ①1是自然数； ②每一个确定的自然数a，都有一个确定的后继数a‘ ，a’ 也是自然数（一个数的后继数就是紧接在这个数后面的数，例如，1的后继数是2，2的后继数是3等等）； ③如果b、c都是自然数a的后继数，那么b = c； ④1不是任何自然数的后继数； ⑤任意关于自然数的命题，如果证明了它对自然数1是对的，又假定它对自然数n为真时，可以证明它对n' 也真，那么，命题对所有自然数都真。(这条公理也叫归纳公设，保证了数学归纳法的正确性)

7 证明 基本上，第一定理的证明是通过在形式公理系统中构造如下命题    p = “此命题是不可证明的”来完成的。这样，它可以看成是说谎者悖论的一个现代变种。 如果公理系统是相容的，哥德尔证明了p（及其否定）不能在系统内证明。因此p是真命题（p声称它不可证明，而它确实不能），尽管其证明不能在系统内形式化。请注意将p作为公理加入系统并不能解决问题：扩大了的系统中会有另一个哥德尔语句出现。

8 结论 数学不但是不完全的（Incomplete），而且是不可完全的(Incompletable) 数学家外尔
 数学家外尔 上帝是存在的，因为数学无疑是不矛盾的； 魔鬼也是存在的，因为我们无法证明这种不矛盾性。  

9 推论 Can‘t find a set of axioms sufficient for all mathematics
粉碎了希尔伯特的计划-- 把整个数学形式化 1900年在巴黎数学家大会上，希尔伯特向全世界数学家提出了20世纪亟待解决的23个最具挑战性的问题。23个问题中的第二个，是证明初等数论形式系统的无矛盾性。 Not all mathematical questions are computable. 图灵机停机问题是不可判定的: 是否存在一台"万能的"图灵机 H, 把任意一台图灵机 M 输入给 H, 它都能判定 M 最终是否停机, 输出一个明确的 "yes" 或 "no" 的答案? 假定存在一个能够判定任意一台图灵机是否停机的万能图灵机 H(M), 如果 M 最终停机, H 输出 "halt"; 如果 M 不停机, H 输出 "loop". 我们把 H 当作子程序, 构造如下程序 P: function P(M) { if (H(M)=="loop") return "halt"; else if (H(M)=="halt") while(true); // loop forever } 因为 P 本身也是一台图灵机, 可以表示为一个字符串, 所以我们可以把 P 输入给它自己, 然后问 P(P) 是否停机. 按照程序 P 的流程, 如果 P 不停机无限循环, 那么它就停机, 输出"halt"; 如果 P 停机, 那么它就无限循环, 不停机

10 误解1：任何公理系统都是不完备的 该定理需假设公理系统可以定义自然数。不过并非所有系统都能定义自然数，就算这些系统拥有包括自然数作为子集的模型。 例如，欧几里德几何可以被一阶公理化为一个完备的系统。

11 误解2：AI不可能实现 1989年，英国数学家、物理学家彭罗斯《皇帝新脑》 认为这表明了计算机的缺陷，人类的直觉可以解决的问题计算机不能解决，所以计算机永远不可能具有人脑的能力。

12 哥德尔的观点 不完全性定理并未给出人类理性的极限，而只揭示了数学形式主义的内在局限
不完全性定理可以作为“人心胜过计算机”论断的部分证据，但是，仅仅使用他的定理不足以作出如此强硬论断。 哥德尔指出，图灵曾给出的“心的过程不能超越机械过程”的论证在附加以下两个假定之后才有可能：（a）没有与物质相分离的心。（b）大脑的功能基本上像一台数字计算机。他认为（b）的概率很高；但无论如何（a）是将要被科学所否证的时代偏见。 人心有洞察具有超穷性质的数学真理的直觉能力，特别是能够洞察数学形式系统的一致性。 不完全性定理并不排除存在事实上等价于数学直觉的定理证明机器。但是定理蕴涵着，我们或者不能确切知道这台机器的详情，或者不能确切知道它是否会准确无误地工作。

13 其他观点 机器可以学习人类解决问题的方式，不单纯用公理系统解决问题，还可以使用启发式知识,经验等等。
图灵的观点：并不需要机器永远输出永真的答案 – 不在哥德尔定理限制范围内 there might be men cleverer than any given machine, but then again there might be other machines cleverer again, and so on. 改进的图灵机：可以中断计算来寻求外部信息

14 哥德尔的其他想法 1971年他还曾给出一个论证上帝存在的本体论公理化证明
相信人有来生，认为我们所生活的世界绝不是唯一一个我们曾经生活过和将要继续生活的世界，并且相信存在异于人类的高级智慧生物 曾有人问哥德尔，是否可以将他的不完全性定理推广到数学之外，哥德尔尝试给出了一个他自己认为合理的表述：一个完全不自由的社会（即处处按统一法则行事的 社会）就其行为而言或者是不一致的，或者是不完全的，即无力解决某些可能是极端重要的问题。在困难的处境中，这两者当然都会危及社会的生存。这个说法也适 用于个体的人。 人类需要一个肉体器官来把握抽象印象，预言“作为精密理论的哲学”将在今后几百年内产 生，断言将心智等同于计算机的“生物机械主义” 和“没有与物质相分离的心”这样的论断终将被未来的科学发展所否证。

15 关于广义相对论与时间概念 1949，“关于相对论与唯心主义哲学之间的关系的一点评论”
“狭义相对论的出发点正在于发现时间的一种新的很让人震惊的性质，那便是同时性的相对性，它在很大程度上也蕴涵着先后的相对性”……“物质的存在”把“跟着物质的平均运动一起运动”的那些观察者划出来了。在所有已知的宇宙论解中，“这些观察者的局部时间拟合成一个世界时间”，我们可以把它看作“客观时间” 但是，在“爱因斯坦引力场方程一类新宇宙论解的一例”给出的一个新解中，这个新世界没有这样的“世界时间”。 广义相对论允许闭合类时曲线的存在 有可能作时间旅行 “划不出绝对时间，因而并不存在客观时间流逝的世界与自然律的相容性本身就有助于认清能规定绝对时间的那些世界中时间的意义。” 我们存在的这个宇宙是哥德尔宇宙吗？-- 可能 2005, 《A World Without Time: The Forgotten Legacy of Godel and Einstein 没有时间的世界:爱因斯坦与数学大师哥德尔》

16 哥德尔和物理学的终结 2002年8月17日，英国著名科学家霍金在北京国际弦理论会议上发表了题为《哥德尔与M理论》的报告，他说，建立一个单一的描述宇宙的大统一理论是不太可能的。这一推测正是基于数学领域的哥德尔不完全性定理。 后来多次发表”哥德尔和物理学的终结”演讲

17 我们不是天使(霍金的演讲的部分)     直至目前，大多数人都含蓄地假定存在一种终极理论，我们最终能够发现它。事实上，我本人就曾说过 我们会很快找到这个理论。但是M－理论让我怀疑这是否是真的。也许要以有限数量的命题来阐述宇宙终极理论是不可能的。这和哥德尔不完备性定理非常相似，该 定理说任何有限公理系统都不足以证明其中的每一个数学命题。     哥德尔定理和我们是否能以有限数量的原理构建宇宙终极理论有什么关系呢？一个联系是明显的。根据实证论科学哲学，一个物理理论是一数学模型。因此如果有数学命题不能证明的话，那就有物理问题不能预测。     在标准的实证论科学哲学看来，物理理论无偿居住于柏拉图式理想数学模型天国中。也 就是说，一个模型可以任意程度地详细，可以包含任意多量的信息，而不会影响它们所描述的宇宙本身。但我们不是天使，可以从外面观察宇宙。相反，我们和我们 的模型两者都是我们所描述的宇宙中的组成部分，因此一个物理理论是自指的，就像哥德尔定理所说的那样。人们因此可以认为它或者是不一致的，或者是不完备 的。我们迄今所有的各种物理理论既是不一致的，也是不完备的。     如果不存在一种可从有限条数原理推导出来的终极理论，一些人将非常失望。我过 去就属于这个阵营。但是我已改变了我的看法。现在我很高兴我们寻求知识的努力永远都不会到达终点，我们始终都有获得新发现的挑战。没有这种挑战，我们就会停滞。哥德尔定理保证了数学家们总有事情要做，我想M－理论也将为物理学家们做同样的事情。

18 书 王浩( ) 1971年起开始密切接触哥德尔；哥德尔允许王浩出版他的传记， 不过要在哥德尔死后。 1987 / 2002 哥德尔(reflections on kurt godel) 1996 / 2009 逻辑之旅: 从哥德尔到哲学(A Logic Journey: From Gödel To Philosophy) 2005,不完备性：哥德尔的证明与悖论(Incompleteness: The Proof and Paradox of Kurt Godel) 1958 / 2008, 哥德尔证明 (Godel's Proof, Fiftieth Anniversary Edition edition)