图灵机
计算机的思想雏形应当追溯至阿兰图灵和他的图灵机。图灵机指的是这样一种机器，能够看懂任何数学命题，并且判定其推理正误。因为数学命题可能用不同的符号#陈述，可能使用不同的公理系统。这台机器也应当能够学会任何规则。图灵机构想同当时的思想环境密不可分：人们想给数学大厦封顶，自此以后数学能够严密证明一切数学命题。大卫·希尔伯特提出的“判定”问题就与此密切相关：存不存在一台机器能够自动判定一切数学命题的真假。图灵仔细研究这个问题，提出了图灵机这一理论构想。它能够依照一定规则计算，并且随时能够学习新的规则。图灵机的构想不是为了证明“判定”问题而是为了证否“判定”问题，设若有一个图灵机在运行，怎么判定它会停机还是会死循环呢。图灵认为这必然要靠另一架图灵机来判定。这另一架图灵机检测到前一台机器停机则自身并不停机，检测到前一台机器死循环则停机并输出“死循环”。这后一台图灵机也是在运作着的，当它反观自身时，就会出现悖论。要么它自己会停机，但此时它应当不停机；要么它永不停机，据规则它应当停机。这是一个机器版的罗素悖论。总之，存在那么些问题，图灵机是解决不了的。这一事实产生了“可计算性”这个概念。一切图灵机可计算的命题都是可计算的。
- 我很搞不懂这个前提。凭什么另一台图灵机检测到前一台停机时它自己非要继续运作下去？它也可以停机并且输出“停机”啊。这样的话当此图灵机反观自身时，要么它会停机，自己也输出停机。要么它自己会死循环，自己应当停机，但这样就有故障了。这似乎有点半吊子的感觉。
- 有一种$\lambda$语言，在数学上拿来表述算法，也成功地证否了“判定”问题。
可计算性这个概念还衍生出了$P=NP$问题。世界上有些问题固然是可计算的，可是算出来都要等到宇宙终结，这种可计算实在没有什么意义。我们用时空复杂度来衡量计算出一个问题的时跟空间成本。P指的的polynomial，可在多项式时间$O(n^x)$内解决的问题；NP即non-polynomial则可在多项式时间内检验解是否正确却难以在多项式时间内求解的问题。$P=NP$就是问理论上$NP$问题是否都有多项式时间内可求解的算法。
- 有种可能的解决这个问题的方向是处理布尔可满足性问题。
- 本书在此叉出一节讨论了柯氏复杂性（柯尔莫哥洛夫）和压缩文件的关系。
图灵机迈入现实
图灵机是个很漂亮的想法，但是离今天威力无穷的计算机差的还远。计算机真正落地要归功于冯诺依曼和香农。香农告诉世人电路可以由布尔逻辑式表达，而一切数学问题又可以划归为逻辑问题（这是数理逻辑学家罗素等人的功劳），因此可计算数学命题的图灵机才有了真正落地的可能。冯诺依曼1945年给出的初稿中谈到计算机必然包含三个组分：
- 中央处理器
- 中央控制器
- 存储器
再加上输入部件和输出部件，算成五大组分也是可以的。冯诺伊曼机器也是今后使用计算机的鼻祖原型。
指挥计算机
在计算机的肇始，“教”给计算机新的规则要靠插入不同的线路对计算机进行重新装配。威尔克斯在剑桥大学领衔研制的电子延迟存储自动计算机（Electronic Delay Storage Automatic Calculator，简称EDSAC）于1949年5月6日投入运行，它是在软件层面学习新的规则。这比在硬件层面改变计算机的规则要简单多了，但还是很难，因为计算机处理的最原始的信息是二进制码，无论是编写还是改进二进制码都是很费脑子也很不直观的。最初的人们想到的改进手段是微代码。也就是把一些常用的操作组合打包在硬件本身中，人们编写程序时只消把这一操作组合当成一个整体来看待就行了。引用书后的一条注释：
例如烹饪西红柿鸡蛋的步骤包括：购买西红柿和鸡蛋，清洗食材，打鸡蛋，炒鸡蛋，放西红柿继续炒，放盐，炒熟之后盛盘上桌。这样已连续的步骤被集成在CPU内部。外部程序需要烹饪西红柿鸡蛋的时候只需要向CPU下达指令说：“烹饪西红柿鸡蛋”就可以了。
微代码的思想就是把常用操作打包的思想，换个通行的词就叫 “模块化”。其后人们又想到了建立函数库，把常用的一些操作继续在软件层面打包进函数库里。（想一想print、abs之类的函数）这些给汇编语言蓄足了势——如果人们已经能把长长的机器码化约为几个简单的操作，把这几个简单的操作转译为文字语言也并非难事。这就是汇编代码。然而汇编代码仍然没有完全和计算机底层硬件脱离（似乎在汇编代码里设定一段程序的地址必须要靠手动，和具体硬件联系太紧密使汇编代码和机器码不能够跨机器运行），由格伦尼发明的Autocode是世界上最早出现的编译型高级编程语言，让程序员能在更抽象的层次思考（一些地方说编译是高级语言到汇编语言到机器码这整个过程；另一些地方说高级语言到汇编语言才叫编译，汇编语言到机器码那叫汇编。起码在中文世界里这个概念混来混去，难以查考，于此列出以供参考）。编程语言还有更精细的发展：
早期语言基本上都是过程式语言（程序员告诉计算机如何执行过程步骤），后来的语言则采用了不同的编程范型。在面向对象的语言〔20〕（Object-Oriented Language）中，数据及其操控方法都封装〔21〕在“对象”中，以实现代码的模块化，防止数据的意外损坏（这一点也是程序的“副作用”）。函数式编程语言利用若干简单的执行单元让计算结果不断渐进，逐层推导复杂的运算，而不是像过程语言一样，设计一个复杂的执行过程。
- 还存在特化于数据库查询的编程语言，如SQL。
计算机网络
计算机网络首先依赖于于香农的工作。香农为信息论奠基，阐述了信道、信息纠错、信息率等等内容，使人们能够把一切声光电信号转化为数字01信号进行传输。计算机网络的前身是阿帕网。英国国家物理实验室也建立起一个内网，机缘巧合下柯尔斯坦主持了将阿帕网同其相连的工作。尽管有重重困难，最后柯尔斯坦凭借自己在英国邮局的关系，借用邮局掌管的电话线路办成了这件事。
显然，计算机网络在开头是将几帮人弄出的不同网络系统连起来形成的。这些实现方案，传输方案可能完全不同的网络系统如何沟通联络是个必须面对的问题。罗伯特·卡恩和文特·瑟夫发布了TCP/IP协议，以此为标准不同的计算机在联络过程中出错的可能性要低得多。TCP/IP协议尽可能地包容不同的网络协议，具有强大包容性的它在多种因素促进下最终成为互联网的标准协议。此时类似于我们今天所谈的互联网的东西才最终诞生。
计算机网络要发展，必须要给内部的各个计算机编个代号。不然的话怎么办到点对点精确传输信息呢。阿帕网等大多数网络采取两套方案，一套是方便易记的字母地址域名，另一套是给计算机处理的精确数字地址IP。浏览器得到域名后通过叫域名解析的过程向域名服务器（DNS）查询得知域名对应的IP地址：首先计算机查询本地DNS，本地DNS查不到就去根服务器查，从根服务器自顶级域服务器到各次级域名服务器逐步查询直至查询成功。查到后计算机通过本地DNS发出建立TCP连接的请求。
- 根服务器主要用来管理互联网的主目录，全世界只有13台。1个为主根服务器，放置在美国。其余12个均为辅根服务器，其中9个放置在美国，欧洲2个，位于英国和瑞典，亚洲1个，位于日本。所有根服务器均由美国政府授权的互联网域名与号码分配机构ICANN统一管理，负责全球互联网域名根服务器、域名体系和IP地址等的管理。
以上所谈的是互联网，计算机网络信息传输所赖的种种基础设施。而我们谈的万维网指的是所有网页联系而成的那个总体。万维网产生自超文本这一概念。超文本把数据库中的零散信息链接在一个页面中，这一页面中又有某些通道通向数据库中的其它页面。这个页面的聚合就是Web的雏形。Web上的每个文件都有自己的统一定位标识符（URL），URL亦可以看成更细致的互联网编码系统。程序员想处理整个网页时也有伯纳斯·李发明的HTML语言可用。HTTP协议则解决了万维网的传输标准问题（万维网建立在互联网之上，HTTP协议亦建立在TCP/IP协议之上）。
- 网络信息传输要讲究信息安全。此事同各类密钥加密算法有关。
真是完美的文章，只是专业名词很多，哈哈