1. 怎么准备出发？

计算为什么要借助机器，靠人不行吗？

计算 = 运算 + 存储

人的能力很有限：大脑的运算速度和手的记录速度。

计算机擅长快速计算和大量存储。

快到什么程度？这台 Mac Pro 的 CPU2.6GHz，每秒 2.610^9 次 / 秒，这是多快呢？光速是 0.310^9 米 / 秒，二者一比，就是 9 次 / 米，光走一米，计算机已经运算了 9 次！

存储量大到什么程度？这台 Mac Pro 是 250GB，一个 Byte 约是 8bits。2.5 * 10^11B，这相当于多少本书呢？

怎样才是 “可计算地思考”？

知识按照是否可以操作分成两种：

1. 不可操作 ——Declarative Knowledge，宣称。
2. 可以操作 ——Imperative Knowledge，命令。

可计算地思考，就是寻找和构建命令式知识的过程。

为什么 “算法 algorithm” 这个词有点怪？

它不是来自于希腊语或拉丁文，它来自一位波斯数学家的姓：Muhammad ibn Musa al-Khawarizmi

算法是菜谱。

算法是一有限句指示，描述一种计算，在一组输入的基础上，通过明确定义的状态转换，最终产出一个结果。

用机器实现算法走了哪两条路线？

固定程序计算器：弹道，线性方程组，密码破解，计算器。

存储程序计算器：Manchester Mark I。

可以存储的计算机必须加上哪两个辅助功能？

编译器和控制流。

程序员和厨师有什么相似？

基础的食材 / 动作，组合出无限可能。

编程语言有什么基本要求？

用什么方式组织计算？是否可以编程？

用图灵机 Universal Turing Machine 组织计算：假想的计算装置：包含 1. 无限长的纸带；2. 一个读写头；3. 一套控制规则表；4. 一个状态寄存器。注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。参考 博客

图灵证明了，如果某个功能可计算，就可以用图灵机编程计算它。

这个 “如果” 有玄机。举个例子，停机问题 halting problem。据说 它类似于集合论中的 “自指” 问题，罗素的理发师悖论。

好消息是：越来越多的现实问题，进入有能力有方法计算的范围了！

图灵完备性 Turing completeness？

别操心这个，现代所有语言都是完备的，也就是底层一致，彼此可以替换。

编程语言由什么构成？

语素 literals` tokens和符号infix operators`。

什么是语法和语义？

三个层次。

语法 syntax—— 在什么位置上该放哪类东西？

静态语义 static semantic—— 前后关系是否合理？

语义 semantic—— 含义是否明确准确？

一个程序可能出什么错？

最轻的：崩溃掉。 中间的：无限循环。程序员不知道程序需要运行多久时，很难判断。 最严重：给出了像样的结果，缺可能对，也可能不对。

如果不对，后果严重：病人误诊，飞机相撞。

所以，程序要能自证清白。

动手：写一个指路说明，看看他会得多少交通罚单？