1701065603
1701065604
香农的信息定义关注的是消息源的可预测性。不过在现实世界中，信息是用来分析并产生意义的东西，信息被存储，并和其他信息结合，产生结果或行为。总之，信息是用来计算的。
1701065605
1701065606
历史上计算的意义变化很大。直到20世纪40年代末，计算都是指手工进行数学运算（小学生称之为“做算术”）。计算员（Computer）就是做数学运算的人。我以前的老师伯克斯（Art Burks）常和我们说他娶的是“计算机”——指的是第二次世界大战时被征召入伍手工计算弹道的妇女，伯克斯的夫人在遇到他时正是这样一位计算员。
1701065607
1701065608
现在计算指的是各式各样的计算机干的事情，另外自然界的复杂系统似乎也干这个。但是计算到底是什么呢？它又能做些什么呢？计算机什么都能算吗？是不是存在原则上的局限性？这些问题都是在20世纪中叶才得到解决。
1701065609
1701065610
复杂 [:1701064737]
1701065611
希尔伯特问题和哥德尔定理
1701065612
1701065613
对计算的基础及其局限的研究，导致了电子计算机的发明，但其最初的根源却是为了解决一组抽象（而且深奥）的数学问题。这些问题是德国数学大师希尔伯特（David Hilbert，图4.1）于1900年在巴黎的国际数学家大会上提出来的。
1701065614
1701065615
希尔伯特在演讲中提出了世纪之交面临的23个亟待解决的数学问题。其中第2个和第10个问题在后来影响最大。实际上，它们不仅仅是数学内部的问题，它们还是关于数学本身以及数学能证明什么的问题。总的来说，这些问题可以分为三个部分：
1701065616
1701065617
1.数学是不是完备的？也就是说，是不是所有数学命题都可以用一组有限的公理证明或证否。
1701065618
1701065619
1701065620
1701065621
1701065622
▲图4.1 希尔伯特（1862—1943）（美国物理学会西格尔图像档案，兰德收藏）
1701065623
1701065624
举个例子，还记得中学几何里学过的欧几里得公理吧？记不记得用这些公理可以证明“三角形内角和为180度”这样的定理？希尔伯特的问题是：是不是有某个公理集可以证明所有真命题？
1701065625
1701065626
2.数学是不是一致的？换句话说，是不是可以证明的都是真命题？“真命题”是专业术语，但我在这里用的是直接意义。假如我们证出了假命题，例如1+1=3，数学就是不一致的，这样就会有大麻烦。
1701065627
1701065628
3.是不是所有命题都是数学可判定的？也就是说，是不是对所有命题都有明确程序（definite procedure）可以在有限时间内告诉我们命题是真是假？这样你就可以提出一个数学命题，比如“所有比2大的偶数都可以表示为两个素数之和”，然后将它交给计算机，计算机就会用“明确程序”在有限时间内得出命题是“真”还是“假”的结论。
1701065629
1701065630
最后这个问题就是所谓的Entscheidungsproblem（“判定问题”），它可以追溯到17世纪的数学家莱布尼茨（Gottfried Leibniz）。莱布尼茨建造了他自己的计算机器，并且认为人类将建造出能判定所有数学命题真假的机器。
1701065631
1701065632
这三个问题过了30年都没有解决，不过希尔伯特很有信心，认为答案一定是“是”，并且还断言“不存在不可解的问题”。 [54]
1701065633
1701065634
然而他的乐观断言并没有维持太久，可以说非常短命。因为就在希尔伯特做出上述断言的同一次会议中，一位25岁的数学家宣布了对不完备性定理的证明，他的发现震惊了整个数学界，这位年轻人名叫哥德尔（Kurt G del，图4.2）。不完备性定理说的是，如果上面的问题2的答案是“是”（即数学是一致的），那么问题1（数学是不是完备的）的答案就必须是“否”。
1701065635
1701065636
哥德尔的不完备性定理是从算术着手。他证明，如果算术是一致的，那么在算术中就必然存在无法被证明的真命题——也就是说，算术是不完备的。而如果算术是不一致的，那么就会存在能被证明的假命题，这样整个数学都会崩塌。
1701065637
1701065638
1701065639
1701065640
1701065641
▲图4.2 哥德尔（1906—1978）（照片由普林斯顿大学图书馆提供）
1701065642
1701065643
哥德尔的证明很复杂。 [55] 不过直观上却很容易解释。哥德尔给出了一个数学命题，翻译成白话就是“这个命题是不可证的”。
1701065644
1701065645
仔细思考一下。这个命题很奇怪，它居然谈论的是它自身——事实上，它说的是它不可证。我们姑且称它为“命题A”。现在假设命题A可证，那它就为假（因为它说它不可证），这就意味着证明了假命题——从而算术是不一致的。好了，那我们就假设命题A不可证，这就意味着命题A为真（因为它断言的就是自己不可证），但这样就存在不可证的真命题——算术是不完备的。因此，算术要么不一致，要么不完备。
1701065646
1701065647
难以想象这个命题如何转换成用数学语言表述，但是哥德尔做到了——哥德尔证明的复杂和精彩之处就在此，在这里我们不去讨论。
1701065648
1701065649
绝大多数数学家和哲学家都坚定地认为希尔伯特问题能被正面解决，这对他们是个沉重的打击。就像数学作家霍吉斯（Andrew Hodges）说的：“这是在研究中惊人的转折， [56] 因为希尔伯特曾以为他的计划将一统天下。对于那些认为数学完美而且无懈可击的人来说，这让人难以接受……”
1701065650
1701065651
复杂 [:1701064738]
1701065652
图灵机和不可计算性