书名：复杂（第一推动丛书·综合系列）
作者：梅拉妮·米歇尔
译者：唐璐
出版社：湖南科学技术出版社
出版时间：2018-01-01
ISBN：9787535794369
第4章 计算
- 什么是计算？什么可以计算
- 希尔伯特问题和哥德尔定理
- 图灵机和不可计算性
- 定义为图灵机的明确程序
- 通用图灵机
- 图灵对判定问题的解决
- 哥德尔和图灵的命运
二、希尔伯特问题和哥德尔定理
1、希尔伯特问题
对计算的基础及其局限的研究，导致了电子计算机的发明，但其最初的根源却是为了解决一组抽象（而且深奥）的数学问题。
这些问题是德国数学大师希尔伯特于1900年在巴黎的国际数学家大会上提出来的。-
希尔伯特在演讲中提出了世纪之交面临的23个亟待解决的数学问题。其中第2个和第10个问题在后来影响最大。
实际上，它们不仅仅是数学内部的问题，它们还是关于数学本身以及数学能证明什么的问题。
总的来说，这些问题可以分为三个部分：- 1．数学是不是完备的？也就是说，是不是所有数学命题都可以用一组有限的公理证明或证否。
希尔伯特的问题是：是不是有某个公理集可以证明所有真命题？ - 2．数学是不是一致的？换句话说，是不是可以证明的都是真命题？
“真命题”是专业术语，但我在这里用的是直接意义。
假如我们证出了假命题，例如1+1=3，数学就是不一致的，这样就会有大麻烦。 - 3．是不是所有命题都是数学可判定的？也就是说，是不是对所有命题都有明确程序（definite procedure）可以在有限时间内告诉我们命题是真是假？
这样你就可以提出一个数学命题，比如“所有比2大的偶数都可以表示为两个素数之和”，然后将它交给计算机，计算机就会用“明确程序”在有限时间内得出命题是“真”还是“假”的结论。
- 1．数学是不是完备的？也就是说，是不是所有数学命题都可以用一组有限的公理证明或证否。
最后这个问题就是所谓的Entscheidungsproblem（“判定问题”），它可以追溯到17世纪的数学家莱布尼茨（Gottfried Leibniz）。莱布尼茨建造了他自己的计算机器，并且认为人类将建造出能判定所有数学命题真假的机器。
这三个问题过了30年都没有解决，不过希尔伯特很有信心，认为答案一定是“是”，并且还断言“不存在不可解的问题”。
但是他错了！
2、哥德尔不完备性定理
不完备性定理说的是，如果上面的问题2的答案是“是”（即数学是一致的），那么问题1（数学是不是完备的）的答案就必须是“否”。
哥德尔的不完备性定理是从算术着手。
他证明，如果算术是一致的，那么在算术中就必然存在无法被证明的真命题——也就是说，算术是不完备的。
而如果算术是不一致的，那么就会存在能被证明的假命题，这样整个数学都会崩塌。-
哥德尔给出了一个数学命题，翻译成白话就是“这个命题是不可证的”。
结论是：算术要么不一致，要么不完备。
哥德尔（1906—1978），25岁证明了不完备性定理
绝大多数数学家和哲学家都坚定地认为希尔伯特问题能被正面解决，这对他们是个沉重的打击。就像数学作家霍吉斯（Andrew Hodges）说的：“这是在研究中惊人的转折，因为希尔伯特曾以为他的计划将一统天下。对于那些认为数学完美而且无懈可击的人来说，这让人难以接受……”
