本文节选:复杂性第四章中的计算
作者梅勒妮·米歇尔
编者按:自从计算机诞生以来，计算的概念已经经历了很长时间。现在很多科学家把计算看作是自然界的普遍现象。细胞、组织、植物、免疫系统和金融市场显然与计算机的工作方式不同，那么它们所说的计算到底是什么意思呢？他们为什么这么说？
◆◆◆ 什么是计算？能算出什么？
香农的信息定义了信息源的可预测性。然而，在现实世界中，信息是用来分析和产生意义的东西。信息被储存起来，并与其他信息相结合，以产生结果或行为。简而言之，信息是用来计算的。
计算的意义在历史上变化很大。直到20世纪40年代末，计算都是手工的数学运算(小学生称之为“做算术”)。计算机是做数学运算的人。我以前的老师阿特·伯克斯(Art Burks)经常告诉我们，他娶了一个“计算机”——一个在第二次世界大战中被征召用手计算弹道的女人。Beukes的妻子遇到他时就是这样一个计算器。
现在计算指的是计算机做的各种事情，自然界的其他复杂系统似乎也是这样。但是到底什么是计算呢？它能做什么？计算机能计算任何东西吗？原则上网络有限制吗？这些问题直到20世纪中期才得以解决。
◆☪☪ 希尔伯特问题和哥德尔定理
对计算的基础和局限性的研究导致了电子计算机的发明，但其最初的根源是为了解决一组抽象的(且深奥的)数学问题。这些问题是德国数学家戴维·希尔伯特在1900年的国际数学家大会上提出的。
希尔伯特，1862-1943(美国物理学会西格尔图像档案，兰德收藏)
(AIP埃米利奥塞格雷视觉档案，兰德收藏)
希尔伯特在演讲中提出了世纪之交需要解决的23个数学问题。其中，问题2和10对后来的影响最大。事实上，它们不仅是数学的内部问题；它们是关于数学本身和数学能证明什么的问题。一般来说，这些问题可以分为三个部分:
1。数学完整吗？
也就是说，所有的数学命题都可以被有限的一组公理证明或证伪吗？
带上巴克斯特。com为例。还记得中学几何里的欧几里德公理吗？还记得这些公理可以用来证明三角形内角之和为180度的定理吗？希尔伯特的问题是:有没有一个公理集合可以证明所有的真命题？
2。数学一致吗？
换句话说，所有能被证明的东西都是真命题吗？“真命题”是个专业术语，但我这里用的是直接的意思。如果我们证明一个伪命题，比如1 ^ 1 = 3，数学不一致，就会有大麻烦。
3。所有命题都是数学上可确定的吗？
也就是说，是不是所有的命题都有一个确定的程序，可以在有限的时间内告诉我们一个命题是真还是假？这样，你可以提出一个数学命题，比如“所有大于2的偶数都可以表示为两个素数之和”，然后交给计算机，计算机会用“显式程序”在有限的时间内得出该命题是“真”还是“假”的结论。
最后一个问题是所谓的Entscheidungsproblem(“判断问题”)，这个问题可以追溯到17世纪数学家戈特弗里德·莱布尼茨。莱布尼茨建造了自己的计算机器，并相信人类会建造一台可以判断所有数学命题真假的机器。
这三个问题30年都没有解决，但希尔伯特自信答案一定是“是的”，他断言“没有解决不了的问题。”
然而，他乐观的断言并没有持续多久。可以说是非常短暂的。因为就在希尔伯特做出上述论断的同一次会议上，一位25岁的数学家宣布了不完全性定理的证明，他的发现震惊了整个数学界。这个年轻人的名字叫库尔特·哥德尔。不完全性定理说，如果上面问题2的答案是“是”(即数学是一致的)，那么问题1(数学是否完全)的答案一定是“否”。
歌德，1906-1978
(图片由普林斯顿大学图书馆提供)
歌德的不完全性定理是从算术开始的。他证明了如果算术是一致的，那么算术中一定存在无法证明的真命题——也就是说，算术是不完整的。如果算术不一致，那么就会出现可以证明的伪命题，整个数学就会崩溃。
哥德尔的证明很复杂。但直觉上，这很好解释。歌德给出了一个数学命题，翻译成白话就是“这个命题是不可证明的。”
仔细想想。这个命题很奇怪。它实际上是在谈论它自己——事实上，它说它不能被证明。我们称之为“命题A”。现在假设命题A是可证明的。那么就是假的(因为上面说不能证明)。这意味着伪命题被证明——从而算术不一致。好，我们假设命题A是不可证明的。这意味着命题A是真的(因为它所断言的是它不能证明自己)，但接下来还有一个不可证明的真命题——算术是不完全的。因此，算术要么不一致，要么不完整。
很难想象这个命题是如何用数学语言表达出来的，但哥德尔做到了——这也是哥德尔证明的复杂之处和美妙之处，这里就不讨论了。
大多数数学家和哲学家都坚信希尔伯特问题是可以正面解决的，这对他们是一个沉重的打击。正如数学作家霍奇基斯所说，“这是研究中一个惊人的转折点，因为希尔伯特认为他的计划将统治世界。对于那些认为数学完美无瑕的人来说，这是无法接受的……”
◆☪☪ 图灵机与不可计算性
歌德干净利落地解决了希尔伯特的第一个和第二个问题，然后第三个问题被英国数学家艾伦·图灵干掉了。
图灵，1912-1954年
1935年，图灵23岁，在剑桥师从逻辑学家马克斯·纽曼读研究生。纽曼向图灵介绍了哥德尔刚刚得到的不完全性定理。在了解哥德尔的结果后，图灵找到了解决希尔伯特第三问题的方法，并确定了问题。同样，他的回答是“不”
图灵是怎么证明的？如前所述，判断的问题是，有没有“明确的程序”来判断任何命题是否可以被证明？“明确程序”是什么意思？图灵的第一步是定义这个概念。遵循两个世纪前莱布尼茨的思路，图灵通过构想一个强大的算术机器来阐述他的定义，这个机器不仅可以进行算术运算，还可以对符号进行运算，从而证明数学命题。通过思考人类是如何计算的，他构造了一个假想的机器，现在叫做图灵机。图灵机后来成为电子计算机的蓝图。
节选自复湖南科技出版社
通往平均霸权的道路
数学之美:平凡而神奇的贝叶斯方法
告诉你，大师，学数学有什么用？
本文地址:http://www.mangdie.com/post/50295.html
