前言
计算机科学的“品位” P12
如何了解计算机科学的大道
- 了解计算机科学的本质，精髓和内涵
- 清楚计算机科学的边界
- 知道计算机的美感
提高计算机品位要做到的事情
- 判断计算机那些事情能做，哪些不能做
- 了解计算机领域的前提要求
- 对计算机科学的理解：空间（知识的广度和深度），时间（计算机科学的过去，现在和未来）
- 计算机科学的艺术：包括问题的解法和算法的艺术
直到21世纪，骨干网和计算机技术的理论才成熟，才有云计算法发挥土壤，虽然在 1997 年就已经有并行处理工具，但是受制于当时的技术条件，这个工具并不能发挥太大的作用。Google 的迪安关于 GFS 的论文在这个时候发布，刚好顺应了时代。
引子：从机械到电子
0.1 计算机科学的定义：计算单元，存储单元和控制它的指令序列 P4
算盘是计算机，因为它满足了上述要求：计算单元是的手，存储单元是算盘本身，指令序列是算盘口诀。只要会了口诀，就可以计算出结果了。
0.2 计算机的发展：机械计算机，布尔代数和开关电路
1642 年 布莱兹·帕斯卡 发明的最早的计算机可以做加法和减法，但是输入数据太慢，无法高效的计算，这是计算机发展过程中的一个大问题 P5
1882 年 查尔斯·巴贝奇 则花费了巨大代价设计了一个 差分机 直到去世也没有造完
数字电路设计的基础奠基人们：发明布尔代数的是 乔治·布尔，康拉德·楚则 证明了布尔代数可以实现任何十进制计算，克劳德·香农 证明了逻辑控制、计算和开关电路等价
布尔代数：
- 运算元素： False 和 True
- 基本运算：与或非，这三个基本运算都可以从 与非 和或非 导出
香农的电路设计可以总结为：
- 模块化：只需要设计一个简单的模块，大量复用即可完成简单的功能
- 等价性：找到数学理论的等价性，使用布尔代数来解决更高进制的问题
- 计算机科学家要证明等价性，而工程师只要实现等价性就可以了
楚泽 发明二进制计算机：1936 年 26 岁开始研究二进制计算机，研制出了三个版本 Z1 Z2 与 Z3，他使用模块化的方法复用简单模块，成功做出了计算机
关于 量子计算：量子计算解决特定问题确实但是和二进制无关，因为二进制与其他进制本质上等价。根据这篇文章中的说法，量子计算更快是因为并行处理能力更强。
思考题：与或非可以用与非、或非表示：计算之魂思考题0.2——逻辑运算符的等价转换 - 知乎
思路：
- 关键：布尔值自己和自己与非就可以获得“非”，可以只取真值表对角线的元素
- 非一个布尔值，然后进行与非运算，可以得到 或运算
- 与非计算的结果做一个非，就得到了与运算
0.3 图灵机
艾伦·图灵 的三个根本问题：
- 数学问题是否有明确的答案
- 如果有，是否可以用有限的步骤得到答案
- 对于可以在有限步骤得到答案的问题，是否可以用一个运动的机器来解决，当问题解决的时候，机器也停机了。这就是图灵机的设想
大卫希尔伯特 的三个关于计算的数学问题：
- 数学是否是完备的？一个任意命题，可以证明是对的或者错的，这是完备性问题。
- 数学是否是一致的？一个命题不能既是真的又是假的，这是一致性问题。
- 数学是不是可判定的？是否能够判定一个问题有答案 ，这是可判定性问题。
哥德尔不完备性定理：库尔特·哥德尔 解决了前两个问题：世界上有的问题无法判断对错，因此他们不是数学问题
希尔伯特第十问题， 尤里·马基亚谢维奇 证明了算法不存在以下两个问题：
- 对于任意多个未知数的整系数不定方程，可以给出一个可行的算法，经过有限次的计算，可以判定该方程有无整数解。这个问题被尤里·马基亚谢维奇被证明很多不定方程，我们无法证明整数解存不存在。
- (x^2+y^2=z^2) 有整数解，但是 (3x^3+2x^2+y^3=z^3) 就无法证明有没有整数解
图灵机： 一个理论模型，可在有限的步骤里解决数学问题
四条定义：
- 无限长的纸带，带编号的格子里记录符号或者数字
- 读写头，可以改变当前位置的符号、数字
- 规则表，根据当前状态知道下一步的操作
- 寄存器，当前图灵机的状态，图灵机可能的状态是有限的
三条意义：
- 将数学问题分为两类：可以用图灵机在有限步骤内完成的计算；不可以的计算
- 奠定了一个计算机行之有效的架构规则：存储地址，计算机状态，规则表和读写头
- 将数学问题过程和机械运动对应起来
思考题 计算之魂思考题0.3——ENIAC和华为P30 - 知乎
0.4 人工智能的极限 P18
从数学问题到人工智能可解的问题，需要经过以下阶段：
- 数学问题
- 可判定的问题：尤里·马基亚谢维奇 已经证明了很多数学问题无法判定是否有解
- 有答案的问题：真正有有答案的问题，代表有解的问题，比可判定问题更少
- 可计算的问题：理论上能被图灵机解决的问题，才是可计算的。现在的计算机在原理上是图灵机。
- 工程可解问题：图灵机可以解决的问题里，有很多问题因为有限时间内不可解，在工程上就不可解了。计算复杂度超过指数函数的问题，就是工程不可解的
- 人工智能可解问题：为什么人工智能看起来很聪明？是因为很多问题找到了数学上的解题路径。
下层问题是上层问题的子集，其涵盖的范围不断缩小。