计算机的基本原理(Week 1)
第一次数学危机
公元前500年，毕达哥拉斯学派，他们相信数是万物的本源：一切数均可表示成整数或者整数之比
然而毕达哥拉斯证明了勾股定理，某些直角三角形的三边比不能用整数表达
希帕索斯悖论：边长为1的正方形，对角线？
危机的缓解：比例论，使用几何方法避开无理数
危机的解决：实数理论的建立
第二次数学危机
微积分：牛顿和莱布尼兹，建立在**无穷小****分析之上
贝克莱悖论：无穷小一会儿是0，一会儿不是0，像一个幽灵~
危机的缓解：重建实数理论
新的问题：魏尔斯特拉斯给出了一个处处不可微的连续函数➡直观&几何思考不可靠
第三次数学危机
集合论：康托尔建立，一切数学成果可建立在集合论基础上
罗素悖论：S由一切不是自身元素的集合所组成，S是否属于S？
哥德尔不完备性定理：把数学彻底形式化的愿望是不可实现的
问题：如何判断问题可计算or不可计算？
解决思路：为计算建立一个数学模型（计算模型），它能够完成的就是可计算的——图灵机
图灵与图灵机
1936年，《论可计算数在判定问题中的应用》提出了理想的计算机数学模型——图灵机（Turing Machine）
图灵机的构成
一条存储带：其上有一个个小方格，可存储一个数字or字母
一个控制器：包含一个读写头（读or写or改），可接受程序语句，可存储&改变自身状态，可沿着存储带移动
图灵机如何工作
准备：存储带初始化、控制器置于起始并设置好自身状态、准备好程序
执行过程：读字母or数字、根据状态和字符找到对应的程序语句、执行三个动作（写入字母or数字、变更自身状态、左右移）
停机：表示计算完毕，存储带上即为计算结果
图灵机的理论意义
特点：简单，强大，可实现
意义：可实现的通用计算模型，引入了通过读写符号和状态改变进行运算的思想，证实了基于简单字母表完成复杂运算的能力，引入了存储区、程序、控制器等概念的原型
计算机为什么能计算
计算机中数的表示——二进制
十进制转为二进制：除以二的商取余数，”触底反弹“
二进制转为八进制和十六进制：卡3位/4位
计算机中数的计算——布尔运算
基本逻辑运算：与、或、非
复合逻辑运算：同或、异或等
二进制加法：本位是异或运算，进位是与运算——半加器
半加器进行组合，一个半加器的输出作为另一个半加器的输入——全加器