计算机文化与思维的基础

祖冲之将圆周率山巅一寺一壶酒（3.14159），尔乐苦煞吾（26535）推导到小数点后7位花了15年。

巴贝奇的差分机，以蒸汽为动力，可以计算对数的机器。对于蒸汽朋克文化是图腾一般的存在。18世纪末，法国发起了一项宏大而艰巨的计算工程──人工编制《数学用表》，由于没有先进计算工具，法国数学界调集大批精兵强将，组成了人工手算的流水线，算了个天昏地暗，终于完成了17卷大部头书稿。有一天，巴贝奇与著名的天文学家赫舍尔一起，边看书稿中的天文数表边吐槽，发现居然错误百出，巴贝奇目噔口呆地喊道“天哪，但愿上帝知道，这些计算错误已经充斥弥漫了整个宇宙！”。。。。于是他决心要发明一个计算机器来拯救宇宙。所谓差分，就是把函数表的复杂算式转化为差分运算，用简单的加法代替平方运算。Babbage’s Difference Engine #1 差分机（设计制造，成功）Babbage’s Difference Engine #2 大型差分机（设计制造，失败）1985年时，伦敦科学博物馆决定照着巴贝奇的图纸，打造一台完整的差分机2号，最后于2002年完工。视频显示的是伦敦科学博物馆的这台差分机。

巴贝奇意识到差分机是专门用途的计算工具，因此他自1831年以后转而设计可运行通用程序的机械计算机——分析机。分析机由蒸汽机驱动，大约有30米长、10米宽。它使用打孔纸带输入，采取最普通的十进制计数。它的“内存”由同轴转轮制成。大约可以存储1000个50位的十进制数（20.7kB)。有一个算术单元可以进行四则运算、比较和求平方根操作。为这台机器设计的语言类似于今天的汇编语言，而且它被认为是图灵完全的。但由于当时的技术条件所限，直到巴贝奇去世，也只做出分析机的部分模块，从来没有完全制成。直到1991年，伦敦博物馆才做出一个样品，但蒸汽驱动的完整分析机从来没有造出来过。2011年，伦敦博物馆打算搞个真的，但我在网上一直没搜到分析机确切实现的新闻。图片为查理巴贝奇的儿子亨利巴贝奇在他父亲工作的基础上做的分析机部分模块，完成于1910。

可计算性理论起源于对数学基础问题的研究。1900年希尔伯特提出23个数学问题，20世纪20年代哥德尔提出不完备性定理证明 20世纪30年代，为了讨论是否对于每个问题都有解决它的算法，数理逻辑学家提出了几种不同的算法定义。K.哥德尔和S.C.克林尼提出了递归函数的概念，A.丘奇提出λ转换演算，但是这些数学演算非常繁琐难懂。因此，需要一种非形式化的描述简化对机械计算的理解。A.M.图灵和E.波斯特各自独立地提出了抽象计算机的概念。这样，就可以通过抽象计算机，把算法看作抽象计算机的程序。通常把那些存在算法计算其值的函数叫作可计算函数。因此，可计算函数的精确定义为：能够在抽象计算机上编出程序计算其值的函数。这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的。最终算法的概念得以精确化。可计算性理论是研究计算的一般性质的数学理论，也称算法理论或能行性理论。它通过建立计算的数学模型（例如图灵机），精确区分哪些是可计算的，哪些是不可计算的。计算的过程就是执行算法的过程。可计算性理论的重要课题之一，是将算法这一直观概念精确化。算法概念精确化的途径很多，

图灵关于人工智能的论文，标题为lovelace Countess's Opposition，引用了Ada Lovelace对人工智能的论断：此类计算机不会拥有智能图灵则肯定机器可以思维的，他还对智能问题从行为主义的角度给出了定义，由此提出一假想：即一个人在不接触对方的情况下，通过一种特殊的方式，和对方进行一系列的问答，如果在相当长时间内，他无法根据这些问题判断对方是人还是计算机，那么，就可以认为这个计算机具有同人相当的智力，即这台计算机是能思维的。这就是著名的“图灵测试”（Turing Testing）。

以大型机、超级计算机为代表，目标是计算速度的提升和计算能力的提高。

连通图可以一笔画的充要条件是：奇点的数目不是0 个就是2 个（连到一点的数目如是奇数条，就称为奇点，如果是偶数条就称为偶点，要想一笔画成，必须中间点均是偶点，也就是有来路必有另一条去路，奇点只可能在两端，因此任何图能一笔画成，奇点要么没有要么在两端）

一切直觉上能行、可计算的函数都是可用图灵机计算，图灵机可以计算就是可计算的

计算复杂度一般用时间复杂度和空间复杂度两个标准来衡量

常见时间复杂度递增排序依次为：常数O(1), 对数阶O(logn), 线性阶O(n), 线性对数阶O(nlogn),平方阶O(n^2),K次方阶O(n^k),指数阶(2^n)其中除了指数阶外，其他都可以归纳为多项式时间。

多项式时间O(n^k),此k为一常数值（依问题而定）

P问题可以用多项式时间的确定性算法直接求解NP问题 只能用多项式时间的确定性算法来检查和验证它的解

如果找到一个多项式内能被解决的npc问题的解决方法，那么P=NP。

过去的指标是按：巨型机，中型机，小型机，微机来划分的