总结及例题

0.1 什么是计算机

构成计算机的三个要素：计算单元、存储单元和控制它的指令序列。

还可以划分为硬件和软件。

• 硬件为计算单元、存储单元；
• 软件则是指令序列。

0.2 机械计算机、布尔代数和开关电路

香农的电路设计思想分为模块化和等价性。

• 模块化：用少量简单的模块搭建各种复杂的功能。
• 等价性：再复杂的计算都可以等价成很多加减乘除的运算，进而等价成开关电路逻辑运算。

0.3 图灵机：计算的本质是机械运动

图灵的疑问：

• 数学问题是否都有明确的答案；
• 如果有明确的答案，是否可以通过有限步的计算得到答案；
• 对于那些有可能在有限步计算出来的数学问题，能否有一种假想的机器，它不断运动，最后当它停下来的时候，那个数学问题就解决了。

希尔伯特的三个问题：

• 数学是完备的吗？完备性：对于任意一个命题，要么可以证明它是对的，要么证明是错的；
• 数学是一致的吗？一致性：一个命题不能既是真的，又是假的；
• 数学是可判定的吗？可判定行：一个具体的问题，能否判定是否有答案。

哥德尔不完全问题：

• 数学不可能既是完备的，又是一致的。

第十问题：

• 对于任意多个未知数的整系数不定方程，要求给出一个可行的算法，使得借助它，通过有限次运算，可以判定该方程有无整数解。

世界上有很多问题我们无法判定它们的对错，因此它们不是数学问题。即并非所有的问题都是数学问题，即使是数学问题，也并非都可以通过计算机来解决。

0.4 人工智能的极限

今天的人工智能主要是指基于大数据的深度学习。人工智能系统理解为由特定程序（控制指令序列）控制的、能够解决某一类问题的计算机。

图灵的伟大之处在于划定了可计算问题的边界。