图灵的贡献主要有两个：一是建竝了图灵机二是提出了图灵测试、阐述了机器智能的概念。图灵机的概念是现代可计算理论的基础图灵证明，只有图灵机能解决的计算问题实际计算机才能解决。 为纪念图灵对计算机科学的贡献美国计算机协会（ACM）于1966年创立了图灵奖，每年奖给在计算机科学领域中莋出贡献的研究人员被誉为计算机业界和科学界的诺贝尔将。 图灵机就是一个最简单的计算机模型图灵机将控制处理的规则用0 和1表述，将处理的信息及处理的结果也用0和1表达处理即是对0和1的变换（可以用机械/电子系统实现）。 图灵与图灵机模型 英国科学家阿兰.图灵 （） 图灵是现代计算机理论模型的提出者 图灵的贡献主要有两个： 建立了图灵机模型 提出了图灵测试、阐述了机器智能的概念。 图灵证明只有图灵机能解决的计算问题，实际计算机才能解决 “图灵奖”是美国计算机协会于1966年设立的。 图灵机由一条无限长的纸带、读/写头忣控制器构成 什么是图灵机？ 控制器内包括控制规则表它能够通过读/写头对纸带上的符号进行读或写，读写头可以在纸带上左右移动 纸带分成了一个个的小方格，每个方格中可以记录机器字母表里的符号如0或1等。 图灵机模型 机器的程序是五元组｛Si , X , Y , L(R或N) , Sj｝形式的指令集定义了机器在一个特定状态下读入一个特定字符时所采取的动作。 五个元素的含义如下： ①Si 表示机器当前的状态； ②X 表示机器从方格中讀入的内容也即当前内容； ③Y 表示机器用来代替X 写入方格中的内容； ④L、R、N 分别表示左移一格、右移一格和不移动； ⑤Sj 表示机器下一步嘚状态。 图灵机——计算机的理论模型 图灵机——计算机的理论模型 图灵机磁带 图灵机的计算开始于初始状态设为S0，终止于停止（HALT）状態设为SH。 例: 设计能够实现“a+1”运算的图灵机计算完成后要求读写头回到原位。 设a 为十进制数11 机器状态=S0 当前位置 输入 输出 当前状态 （Si） 當前内容 （X） 重写的新内容 （Y） 读写头移动方向 （LR或N） 进入的新状态 （Sj） S0 b b L S1 图灵机可以将程序先保存到存储带上，按照程序一步一步运行矗到给出结果结果也保存到存储带上。 图灵机不是一种具体的机器而是一种理论模型，可用来指导制造一种十分简单但运算能力极强嘚计算装置使得这种机器能够对任何“可计算”的函数进行有效的计算，在有限步内求出函数的计算结果 图灵机模型理论是计算学科朂核心的理论之一，图灵机模型是算法分析和程序语言设计的基础为计算机设计指明了方向。 图灵的贡献主要有两个：一是建立了图灵機二是提出了图灵测试、阐述了机器智能的概念。图灵机的概念是现代可计算理论的基础图灵证明，只有图灵机能解决的计算问题實际计算机才能解决。 为纪念图灵对计算机科学的贡献美国计算机协会（ACM）于1966年创立了图灵奖，每年奖给在计算机科学领域中作出贡献嘚研究人员被誉为计算机业界和科学界的诺贝尔将。 图灵机就是一个最简单的计算机模型图灵机将控制处理的规则用0 和1表述，将处理嘚信息及处理的结果也用0和1表达处理即是对0和1的变换（可以用机械/电子系统实现）。

让我们先来看几个简单的概念：

囿限状态机  -  输入集合和输出集合都是有限的并只有有限数目的状态。

课本中的组合电路+时序电路的模型就是一个有限状态机我们不妨通过它来推测有限状态机应有的组成：

2. 集合S的特殊元素S0，即为起始状态

5. S×I映至S的函数f，即转换函数

6. S映至O的函数g，即为输出函数

前四個内容很容易理解，而f与g这两个函数由电路的设计决定一般是时序电路（存储电路）部分决定f，组合电路部分决定g

具体模型可以用下媔图示表示

而对于计算理论或数学中的定义有限状态机M，有如下的五元组定义：有穷状态转换系统M = <S, A, h, S₀, F>

其中S是M的有穷状态集，初始状态S_0∈S結束状态F?S；M总处在某个状态，开始时在S₀；A是有穷符号集h : S×A → S×(A ? { _ }) 是转换函数（部分函数），_表示无输出若M在状态S接到输入a_∈A,假设h(S, a) = <S’,

對比我们总结的模型，发现出现了终止状态（由于我们所学电路功能主要是实现计数、分频、输出序列波等持续性功能所以没有接触到終止状态），这说明我们的模型基本反映了有限状态机的组成但只是第二个定义无终止状态（即F为空集）的特例，下面我们的讨论就采鼡后面的经典定义

有限状态机在现实生活中其实随处可见，伸缩式圆珠笔其实就是一个有限状态机（两种状态互相转换）下面我们用實现一个简单的有限状态机-自动门。

要求如下：有一自动门它可以被锁上，也可以开锁当门锁上时，某人可以在它的槽中塞进一枚硬幣这样，门就会自动开锁转变到开锁的状态；人通过后，门就会自动锁上

对状态进行分析可得下图

当然，上面讲述的还是一个没有停止状态的有限状态机而且是由电子电路实现的，接下来的例子是在软件方面具有有限状态的有限状态机

这是一个地址识别的算法。ㄖ常我们描述地址（指中文）的语句中地址级别是依次降低的国家、省（直辖市）、市、区县、街道、门牌号（或者从区县之后是乡、村）。而这些就是我们要构造的有限状态机的全部状态这些状态构成的状态图是单向图，比如当前的状态是“省”，如果遇到一个词組（即输入）和市名有关我们就进入状态相应“市”（即状态转换）；走到最低级的地址单位（即终止状态），那么这条地址是有效的否则无效。比如说“北京市海淀区清华大学紫荆公寓2#”对于上面的有限状态机来讲有效，而“上海市辽宁省石家庄市”则无效（因为無法从市走回到省即便可以也会由于石家庄市不属于辽宁省而进入错误状态）。

使用有限状态机识别地址关键要解决两个问题，即通過一些有效的地址建立状态机以及给定一个有限状态机后，地址字串的匹配算法而这两个问题都有现成的算法。有了关于地址的有限狀态机后我们就可又用它分析网页，找出网页中的地址部分建立本地搜索的。同样我们也可以在搜索引擎中对用户输入的查询进行汾析，挑出其中描述地址的部分当然，剩下的关键词就是用户要找的内容

以上就是有限状态机的实际应用，这让我们感到它的功能的確很强大其实想想看，无论对连续系统还是离散系统状态概念无所不在，有限状态机提供了一种描述和控制应用逻辑的非常强大的方法具有规则简单、可读性和可验证性强等特点。

1、 每一种有限状态机均功能唯一即设计好之后无法完成其他原理不同的工作；

2、 因为其状态有限，当所要描述的系统的状态太多时可能确定的有限状态机无能为力；

3、 有一些任务是有限状态机无法完成的，比如它可以判斷输入的0、1数列中0或1的个数是否为奇数或偶数但是无法判断0是否比1多或者相反。

前两个问题表示有限状态机的可扩展性差（或者对比计算机而言是无可编程性）而后者是因为有限状态机状态有限而且不能记下自己需要记录的东西（或者对比图灵机理论是不能写）。

于是峩们发现有限状态机不但状态有限功能也有限（根据计算理论，这是因为它只能接受正则语言而正则语言是最低级的语言，所以能够解决的问题是有限的）

事实上，最初的计算“机”（其实更应该说是计算器）都是功能单一的虽然人们不断地试图在一台机器上集成哽多的功能，但是相对于下面要讲到通用计算理论这些行为还是“盲目”的。

图灵机理论的提出及相关理论：

下面我们的主人公将是图靈也许你现在对他一无所知，但阅读这一节后你需要深刻的记住他，因为在我看来是他启发与影响了他之后的整个计算机发展史。為了让大家更好地理解与接受他的理论我会多穿插一些背景，毕竟天才也不是生活在真空中的

图灵早年在剑桥大学求学，在那个年代剑桥大学的大数学家罗素和怀特海已经创立了“数理逻辑学”。“数理逻辑”这个学科的创建起源于一个逻辑上的“悖论”。为了非專业人士都能明白逻辑悖论的含义哲学家或者数学家喜欢用讲故事的办法来解释它。一个经典的故事是：村子里有位理发师他为而且呮为村子里所有那些不给自己理发的人理发。数学的逻辑推理上会出现类似的悖论数学家们十分担心“数学大厦”会因悖论的存在而坍塌，于是他们都想方设法去修补数学基础例如，康托发表专著《集合论》罗素与怀特海联合撰写三卷《数学原理》。

       剑桥大学是“数悝逻辑学”的发源地与大本营一群聪明而勤奋的青年数学家聚集在数学泰斗罗素教授的周围，图灵是其中的佼佼者1935年，刚刚毕业年僅23岁的图灵就被剑桥大学国王学院甄选为研究员，成为剑桥大学有史以来最年轻的研究员正是图灵在数学，尤其是在“数理逻辑学”方媔的深厚功底令他几年后终于厚积薄发，一举奠定了他计算机科学的创始人的地位

       图灵先知先觉，在电子计算机远未问世之前他已經想到所谓“可计算性”的问题。物理学家阿基米得曾宣称:“给我足够长的杠杆和一个支点我就能撬动地球。”类似的问题是数学上嘚某些计算问题，是不是只要给数学家足够长的时间就能够通过“有限次”的简单而机械的演算步骤而得到最终答案呢？这就是所谓“鈳计算性”问题一个必须在理论上做出解释的数学难题。

       经过智慧与深邃的思索图灵以人们想不到的方式，回答了这个既是数学又是哲学的艰深问题1936年，图灵在伦敦权威的数学杂志上发表了一篇划时代的重要论文《可计算数字及其在判断性问题中的应用》文章里，圖灵超出了一般数学家的思维范畴完全抛开数学上定义新概念的传统方式，独辟蹊径构造出一台完全属于想象中的“计算机”，数学镓们把它称为“图灵机”这样的奇思妙想只能属于思维像“袋鼠般地跳跃”的图灵。

       “图灵机”想象使用一条无限长度的纸带子带子仩划分成许多格子。如果格里画条线就代表“1”；空白的格子，则代表“0”想象这个“计算机”还具有读写功能:既可以从带子上读出信息，也可以往带子上写信息计算机仅有的运算功能是:每把纸带子向前移动一格，就把“1”变成“0”或者把“0”变成“1”。“0”和“1”代表着在解决某个特定数学问题中的运算步骤“图灵机”能够识别运算过程中每一步，并且能够按部就班地执行一系列的运算直到獲得最终答案。

       “图灵机”是一个虚拟的“计算机”完全忽略硬件状态，考虑的焦点是逻辑结构图灵在他那篇著名的文章里，还进一步设计出被人们称为“通用图灵机”的模型它可以模拟其他任何一台解决某个特定数学问题的“图灵机”的工作状态。他甚至还想象在帶子上存储数据和程序“通用图灵机”实际上就是现代通用计算机的最原始的模型。

不过图灵在提出图灵机构想之后又发现了新问题，有些问题图灵机是无法计算的比如定义模糊的问题，如“人生有何意义”或者缺乏数据的问题，“明天3D中奖号是多少”其答案当嘫是无法计算出来的。但也有一些定义完美的计算问题它们亦是不可解的，这类问题称为不可计算问题

不可计算的问题在实践中几乎碰不到，事实上很难找到这样的例子，既不可计算但又有人向计算的明确定义的问题一个罕见的问题是所谓的停机问题。设想要编写┅个用于检查并判定另一个程序是否会运行结束的程序而事实上，不存在一个程序能够判断另一个程序是否与无限循环有染我们可以來这样设想：假定我们有一个Test程序，此程序把别的测试程序当成输入我们把它插入另一个程序Paradox（悖论）中，并在Test中使用Paradox函数作为参数（即Paradox（） { … ；Test（Paradox）；…}）这个Paradox函数的编写思路是这样的，如果Test程序判断Paradox会运行结束那么Paradox就进入无限循环，如果Test判断Paradox不会结束则Paradox函数立刻终止。于是Test函数对Paradox函数无效所以判断函数是否会终止的程序不存在。

计算机不能解一些问题并不是计算机的弱点因为停机问题本质仩是不可解的，不可能建造出一个解停机问题的机器通用计算机无法完成的计算，无论什么东西同样无法胜任

接下来我们给出图灵机模型的一个严格的形式定义：

一个图灵机是一个七元组（Q，∑σ，δ，q₀，q_acceptq_reject），其中Q∑，σ都是有穷集合。

∑是输入字母表不包括特殊空白符号；

σ是带字母表，其中包括∑与空白符号；

δ：Q×σ→Q×σ×（L，R）是转移函数；

从上述形式定义可以看出模型的关键在于有窮控制器中的状态转换函数根据图灵的通用计算理论，这个转换函数是灵活可变的（对应于通用图灵机）当然也可以使单一的（对应於专用图灵机，即便如此它的能力也强于有限状态机，因为图灵机是可以接受0级语言的）不过这并非图灵提出图灵机的意义所在。

下媔我们来比较有限状态机与通用图灵机的区别所在：

1、 图灵机既能读又能写；

2、 带子是无限长的（可以无限存储结合读写头既能左移又能右移的特点，当然就可以解决判断输入的0与1个数谁多的问题）而且带子上不但可以写入数据，还可以写入实现某一具体功能的；

3、 进叺拒绝和接收状态立即停机；

同有限状态机一样我们构造一个图灵机来实现一个简单的功能。

目标：利用二进制来设计一个专门计算“x+1”的图灵机要求计算完成时，读写头要回归原位

字母表∑：{0，1*}；

停机状态集合H：{halt}；

从这个过程中我们发现，虽然图灵机可以实现x+1的功能但是他的工作流程理解起来并不是人们日常的计算过程，甚至与现代计算机的计算原理也并无太大相关这是因为与现代计算机相仳，它的计算方式也还是有局限性由于图灵机每次只能读入一个数据，改写所读入的数据而不像现代计算机可以同时读入多个数据、妀写其他数据，所以相应的算法难理解性也就增加

图灵机的意义与思想内涵：

图灵提出图灵机的模型并不是为了同时给出计算机的设计，它的意义我认为有如下几点：

1、      它证明了通用计算理论肯定了计算机实现的可能性，同时它给出了计算机应有的主要；

2、      图灵机模型引入了读写与算法与程序语言的概念极大的突破了过去的计算机器的设计理念；

3、      图灵机模型理论是计算学科最核心的理论，因为计算機的极限计算能力就是通用图灵机的计算能力很多问题可以转化到图灵机这个简单的模型来考虑。

对图灵机给出如此高的评价并不是高估因为从它的设计与运行中，我们可以看到其中蕴涵的很深邃的思想

通用图灵机等于向我们展示这样一个过程：程序和其输入可以先保存到存储带上，图灵机就按程序一步一步运行直到给出结果结果也保存在存储带上。

另外我们可以隐约看到现代计算机主要构成（其实就是冯诺依曼理论的主要构成），存储器（相当于存储带）中央处理器（控制器及其状态，并且其字母表可以仅有0和1两个符号）IO系统（相当于存储带的预先输入）；

正是在图灵搭建的理论基础之上，计算机才有了后来的蓬勃发展美国的阿坦纳索夫在1939年果然研究制慥了世界上的第一台电子计算机ABC，其中采用了二进位制电路的开与合分别代表数字0与1，运用电子管和电路执行逻辑运算等ABC是“图灵机”的第一个硬件实现。冯·诺依曼不仅在上个世纪40年代研制成功了功能更好、用途更为广泛的电子计算机并且为计算机设计了编码程序，还实现了运用纸带存储与输入至此，天才图灵在1936年发表的科学预见和构思得以完全实现

明白了图灵那无与伦比的贡献，人们就不难悝解何以冯·诺依曼对于“计算机之父”的桂冠坚辞不受。曾经担任过冯·诺依曼研究助手的美国物理学家弗兰克尔教授这样写道：“许哆人都推举冯·诺依曼为“计算机之父”，然而我确信他本人从来不会促成这个错误。或许，他可以被恰当地称为‘计算机的助产士’。依我之见，正是冯·诺依曼使世界认识了由图灵引入的计算机的基本概念。”弗兰克尔教授此言不虚在1949年，冯·诺依曼发表了一篇题为《自动计算机的一般逻辑理论》的论文客观而公正地阐述了图灵在计算机理论上的重大贡献。他写道:“大约12年前英国逻辑学家图灵就开始研究‘可计算问题’，他准确地给出了‘自动计算机’的一般性定义”冯·诺依曼宁愿把“计算机之父”的桂冠转戴在图灵头上。当然，这已经是在图灵离开普林斯顿十来年以后的事了，他当年在普林斯顿并没有像后来那样受人景仰图灵曲高和寡，当年就能看明白他那篇攵章划时代意义的仅仅是少数杰出的数学家，如冯·诺依曼者。

从人类科技发展的历史来看当理论成熟或即将成熟之日，也就是人们開始着手实现之时（虽然在理论创立之前也会有人尝试但还是那句评价，“盲目”）理论指导实践就是这个道理下面我们就沿着有限狀态机、图灵机的这条思路，将自己置身于二十世纪中叶联系当时的技术能力，来构建出一台我们自己的计算机

 图灵理论的一个基本偠求是所有信息都可用符号编码，包括图灵机本身（相当于对图灵机自身功能的描述）编码方式使我们首先要考虑的，这主要取决于编碼集的元素个数与编码元素之间的关系在图灵机的实现中我们可以看到图灵采用的是0、1编码，当然乍看上去我们可能会觉得不太可能，难道我们平时接触的复杂而又多样的种种事物都可以用简单的0、1表示么就算是表示了出来又通过方式进行运算得到我们想要的结果呢？这些其实都不是我们需要考虑的因为这些已经被解决，而完成这项工作的人就是乔治·布尔，19世纪的英国逻辑学家他将人类的逻辑思维简化为一些数学运算，还发明了一种语言用于描写与处理各种逻辑命题和确定其真假与否这种语言被称作逻辑代数，同图灵机的构想一样在当时布尔并不认为是在为计算机的发展做出贡献，虽然事后证明的确意义重大完成将布尔代数引入计算机科学领域的是克劳德·香农，他创立了信息论，并在其中定义了我们称之为“二进制位”的信息度量。采用二进制主要基于以下原因： 

 （1）技术实现简单：當然这与我们后面要讲到的内容有关（最终我们的计算机要由逻辑电路组成，逻辑电路通常只有两个状态开关的接通与断开，这两种状態正好可以用“1”和“0”表示 

 （2）简化运算规则：两个二进制数和、积运算组合各有三种，（求和法则3个：0+0=0 , 0+1=1+0=1, 1+1=10；求积法则3个：0×0=00×1=1×0=0， 1×1=1）运算规则简单有利于简化计算机内部结构，提高运算速度 

 （3）适合逻辑运算：逻辑代数是逻辑运算的理论依据，二进制只有两个數码正好与布尔代数中的“真”和“假”相吻合。 

 （4）易于进行转换二进制与十进制数易于互相转换。 

 （5）用二进制表示数据具有抗幹扰能力强可靠性高等优点。 

随后我们遇到的问题是如何将我们想要表达的问题转化为0、1代码当然，不同的问题经过不同人的处理会囿不同的逻辑表示关键是要保证计算机明白你要表达的真实意思，而这只要你在表示的同时给出一个编码原则这里最本质的概念是信息，哲学家格雷戈里·贝特森将信息定义为“生异之异（the difference that makes a difference）”换句话说，信息是一种差异性、可能性同时它又有影响其它信息的能力，这样看来信息是完全可以用二进制位来表出的例如，当你和别人谈话时说的每个字都是字典中所有字中的一个。如果给字典中所有嘚字从1开始编号我们就可能精确地使用数字进行交谈，而不使用单词(当然对话的两个人都需要一本已经给每个字编过号的字典以及足夠的耐心) ，人与计算机的交谈也是这个道理

那么接下来我们就要考虑如何通过现有（二十世纪中叶）的技术来实现一个二进制系统，是嘚我们想要实现的运算在里面流动（进行）并最终流出。先不要着急我们先来看一下前人的研究成果，

早在17世纪欧洲一批数学家就巳开始设计和制造以数字形式进行基本运算的数字计算机。1642年法国数学家帕斯卡采用与钟表类似的齿轮传动装置，制成了最早的十进制加法器1678年，德国数学家莱布尼兹制成的计算机进一步解决了十进制数的乘、除运算。1834年英国数学家巴贝奇在研制差分机的工作中，看到了制造一种新的、在性能上大大超过差分机的计算机的可能性他把这个未来的机器称为分析机。巴贝奇的分析机由三部分构成第┅部分是保存数据的齿轮式寄存器，巴贝奇把它称为“堆栈”它与差分机中的相类似，但运算不在寄存器内进行而是由新的机构来实現。第二部分是对数据进行各种运算的装置巴贝奇把它命名为“工场”。第三部分是对操作顺序进行控制并对所要处理的数据及输出結果加以选择的装置。为了加快运算的速度巴贝奇设计了先进的进位机构。他估计使用分析机完成一次50位数的加减只要1秒钟相乘则要1汾钟。计算时间约为第一台电子计算机的100倍同时，在多年的研究制造实践中巴贝奇写出了世界上第一部关于计算机程序的专著。

这台汾析机虽然已经描绘出有关程序控制方式计算机的雏型但限于当时的技术条件而未能实现。

我们不难总结出这几点：

2、   巴贝奇提出了通鼡机并具有程序存储控制的思想雏形；

3、   巴贝奇的设想在当时的技术条件下，即机械机的条件下是很难实现的

此外，在那时有人制慥过模拟机器，即不是用我们已经认同的离散数字信号做处理我们在介绍采用0、1编码时，并没有明确排除模拟信号计算的可能性事实仩，这确实是可能的不过现在我们来解释一下我们之所以不那样做的原因。

在物理世界中完全意义上的连续流是无法做到的，模拟计算机的问题是其信号只能达到有限的精度一种模拟信号-无论是电气信号、机械信号或化学信号-都会包含一定程度的噪音，即到某一级分辨率上信号基本上是随机的。任何模拟信号必然受到大量无关的、未明噪音源的影响。如果信号中有百万分之一的噪音那么，杜宇信号来说只有一百万中有意义的差异。既然如此那信号中的信息大可用一个20个二进制位组成的十进制信号来表示（2²⁰=1048578）。在一个模拟计算机中是有意义的差异的个数再翻一番，需要使其中每样东西的精度提高一倍而在数字计算机中，只需增加一个二进制位便可其实朂好的模拟计算机的精度不到30个二进制位。

那好现在我们可以充满信心的使用离散数字信号，也应当把目光从机械机上移开机械及由於其在速度、规模、稳定性、精确度上的缺陷，无法成为我们所要设计的机器的有效载体再强调一遍，我们处在20世纪中叶这时候电工學、电子学不断取得重大进展，在元件、器件方面接连发明了真空二极管和真空三极管；在系统技术方面相继发明了无线电报、电视和雷达。所有这些成就为现代计算机的发展准备了技术和物质条件相对于机械机而言，电路可以有更高的工作频率（意味着计算速度更快）、更小的规模、更稳定、更加精确（高低电平表示不同状态）而且在存储方面它相对于机械机有更大的优势（而这也是我们的主要需求），所以我们把目标放在电子电路实现上

我们已经知道了用0、1表示信息，也想好了用电路的高低电平表示0、1那么下一步就是如何进荇信息存储与简单运算（写到这里可以发现，跟数字电子技术课程的流程是一样的）

来看两个比较重要的事件：1904年，John A.Fleming 取得真空二极管的專利权；1947年,英国完成了第一个存储真空管看来我们可以使用它们的，除了这些东西之外我们还有一些器件是可以使用的，比如存储器件中可以的选择有水银延迟线存储器、阴极射线示波管静电存储器、磁鼓和磁心存储器等，好了有了这些硬件之后，我们就可以专心於电路逻辑上的设计了

最初的时候肯定是没有组合电路逻辑电路之分的，更没有《数字电子技术》这本书可是我们还是根据逻辑式的嶊导与构想，掌握一些基本电路的设计方法的（注意不是电路设计的基本方法），我觉得一项新技术或新产品的往往是这样：人们大概囿一个方向抽象出一定的模块与功能，然后一点一点的加以实现起初人们掌握的是最基础的知识，在实现的过程中他们要通过摸索詓搭配与做修改，与此同时他们慢慢积累总结出一般方法，最终形成成熟的工艺流程比如，设计电路的过程中我们会发现一些区别，有的电路只与当前输入有关而另一些电路还与过去的输入有关，当然我们可以总结出组合电路与时序电路概念与设计上的区别来就昰这样一点一点，我们可以设计出符合简单运算要求的逻辑电路来当然这里还是涉及一些理论的东西的，那就是要设计出多少什么功能嘚基本运算单元才能保证把任何问题分解成的子运算都属于我们的基本运算单元集这个问题现在（二十一世纪）的争议是要构建简单指囹集还是复杂指令集，而且不同种CPU它们的指令集是不同的这的确是一个复杂的问题，但是我们在二十世纪中叶的时候主要目的还是科学計算与军事应用需要的指令应该也还不多吧，所以这个问题我们就跳过了

最后就是真正的对照设计方案连接我们的计算机了，电子管組成的运算电路、各种器件组成的存储器通过导线的连接（当然运算电路、存储电路、IO输入的架构还是一个很不容易产生但很伟大的想法的，虽然它在图灵机中已经有所体现我们在这里把它忽略掉，下面将有介绍）终于可以使用了！

我们的设计历程到此成功结束，但昰我们还是忽略了细节而且我们还是以自己现在的思维，做出了一些自认为显然的判断与设计我们还是有必要翻开历史，回顾一下计算机真实的发展历程虽然有时候看起来笨拙而可笑，但应当说它们都是自身所处时代的最优解现在的计算机绝不是一蹴而就的，况且我们现在的计算机也许就是未来人眼中的ENIAC。

计算机真实的发展历史：

    在第二次世界大战中美国政府寻求计算机以开发潜在的战略价值。这促进了计算机的研究与发展1944年Howard H. Aiken()研制出全电子计算器，为美国海军绘制弹道图这台简称 Mark I 的机器有半个足球场大，内含500英里的电线使用电磁信号来移动机械部件，速度很慢(3-5秒一次计算)并且适应性很差只用于专门领域但是，它既可以执行基本算术运算也可以运算复杂嘚等式

Computer)在费城公诸于世。ENIAC代表了计算机发展史上的里程碑它通过不同部分之间的重新接线编程，还拥有并行计算能力ENIAC由美国政府和賓夕法尼亚大学合作开发，使用了18000个电子管，70000个电阻器，有5百万个焊接点耗电160千瓦，其运算速度比Mark I快1000倍ENIAC是第一台普通用途计算机。

重大突破是由数学家冯·诺伊曼领导的设计小组完成的。1945年3月他们发表了一个全新的存储程序式通用电子计算机方案—电子离散变量自動计算机(EDVAC)主要设计原则是：

    （1）使用单一的处理部件来完成计算、存储以及通信的工作；

    随后于1946年6月，冯·诺伊曼等人提出了更为完善的设计报告《电子计算机装置逻辑结构初探》。同年7～8月间他们又在莫尔学院为美国和英国二十多个机构的专家讲授了专门课程《电子計算机设计的理论和技术》，推动了存储程序式计算机的设计与制造

第一代计算机的特点是操作指令是为特定任务而编制的，每种机器囿各自不同的机器语言功能受到限制，速度也慢

第二代晶体管计算机()

1948年，晶体管的发明大大促进了计算机的发展晶体管代替了体积龐大电子管，电子设备的体积不断减小1956年，晶体管在计算机中使用晶体管和磁芯存储器导致了第二代计算机的产生。第二代计算机体積小、速度快、功耗低、性能更稳定首先使用晶体管技术的是早期的超级计算机，主要用于原子科学的大量数据处理这些机器价格昂貴，生产数量极少

1960年，出现了一些成功地用在商业领域、大学和政府部门的第二代计算机第二代计算机用晶体管代替电子管，还有现玳计算机的一些部件:打印机、磁带、磁盘、内存、操作系统等计算机中存储的程序使得计算机有很好的适应性，可以更有效地用于商业鼡途在这一时期出现了更高级的 COBOL(Common Business-Oriented Language)和FORTRAN(Formula Translator)等语言，以单词、语句和数学公式代替了含混晦涩的二进制机器码使计算机编程更容易。新的职业(程序员、分析员和计算机系统专家) 和整个软件产业由此诞生

第三代集成电路计算机()

虽然晶体管比起电子管是一个明显的进步，但晶体管還是产生大量的热量这会损害计算机内部的敏感部分。1958年德州仪器的工程师Jack Kilby发明了集成电路(IC)将三种电子元件结合到一片小小的硅片上。科学家使更多的元件集成到单一的半导体芯片上于是，计算机变得更小功耗更低，速度更快这一时期的发展还包括使用了操作系統，使得计算机在中心程序的控制协调下可以同时运行许多不同的程序

第四代大规模集成电路计算机(1971-现在)

出现集成电路后，唯一的发展方向是扩大规模大规模集成电路(LSI)可以在一个芯片上容纳几百个元件。到了80年代超大规模集成电路 (VLSI)在芯片上容纳了几十万个元件，后来嘚(ULSI)将数字扩充到百万级可以在硬币大小的芯片上容纳如此数量的元件使得计算机的体积和价格不断下降，而功能和可靠性不断增强

70年玳中期，计算机制造商开始将计算机带给普通消费者这时的小型机带有友好界面的软件包，供非专业人员使用的程序和最受欢迎的字处悝和电子表格程序这一领域的先锋有Commodore， Radio Shack和Apple Computers等

1981年，IBM推出个人计算机(PC)用于家庭、办公室和学校80年代个人计算机的竞争使得价格不断下跌，微机的拥有量不断增加计算机继续缩小体积，从桌上到膝上到掌上与IBM PC竞争的Apple Macintosh系列于1984年推出，Macintosh提供了友好的图形界面用户可以用鼠標方便地操作。

下面的图片展示的是这整个发展历程的一小部分

“现代计算机创始人”查尔斯·巴贝奇的分析仪复制品，该分析仪是用于公式演算的多功能计算机，不过这台计算机在他有生之年始终未能问世。

美国人哈雷里斯利用卡片穿孔，开发了卡片制表系统这一系統被认为是现代计算机的雏形。1911年哈雷里斯将这项专利卖给了另外一家公司，13年后这家公司更名为国际商业机器公司也就是现在的IBM。

ENIAC-卋界上第一台现代电子计算机（局部图）

IBM 1956年发行的光盘图中的最大的光盘是上世纪70年代早期制造的

历经这所有的发展，才有了计算机现茬的高性能与广泛应用不过，虽然计算机的集成度越来越高越做越小，然而由于量子效应的存在技术现在正逼近其极限（0.2nm的工艺），科学家们看到传统的计算机结构必将有终结的一天而且尽管计算机的运行速度与日俱增，但是有一些难题是计算机根本无法解决的唎如大数的，理论上只要一个数足够大这个难题够目前最快的计算机忙几亿年的。事实上计算机从真空管、晶体管、集成电路、超大規模集成电路一路走来，从计算方式的本质来看是没有发生任何改变的我们一直沿着“电子”计算机的道路行走，而没有在其它采用不哃方式进行计算的计算机上有太多考虑不过这种状况已经开始有所转变，因为量子计算机、光子计算机、生物计算机已经开始为我们所熟知下面，我们就介绍一下这些“非电子”计算机从中我们可以发现，计算机科学确实是现代先进科学技术理论的交汇点

进入20世纪90姩代，实验技术和理论模型的进步为量子计算机的实现提供了可能尤其值得一提的是1994年美国的Peter W. Shor证明运用量子计算机竟然能有效地进行大數的因式分解。这意味着以大数因式分解算法为依据的、等领域的RSA公开密钥密码体系在量子计算机面前不堪一击于是各国政府纷纷投入夶量的资金和科研力量进行量子计算机的研究，如今这一领域已经形成一门新型学科-量子信息学

量子计算机具有特大威力的根本原因在於构成量子计算机的基本单元-量子比特（q-bit），它具有奇妙的性质而这种性质必须用量子力学来解释，因此称为量子特性我们现在所使鼡的计算机采用来进行数据的存储和运算，在任何时刻一个存储器位代表0或1而量子比特是由相干叠加而成，一个具有两种状态的系统可鉯看作是一个“二进制”的量子比特在量子世界里物质的状态是捉摸不定的，如电子的位置可以在这里同时也可以在那里原子的能级茬某一时刻可以处于激发态，同时也可以处于基态我们就采用有两个能级的原子来做量子计算机的q-bit。规定原子在基态时记为 |0〉在激发態时原子的状态记为 |1〉，而原子具体处于哪个态我们可以通过辨别得以了解微观世界的奇妙之处在于，原子除了保持上述两种状态之外还可以处于两种态的线性叠加，记为 |φ〉=a |1〉+ b |0〉 其中a，b分别代表原子处于两种态的几率幅如此一来，这样的一个q-bit不仅可以表示单独的“0”和“1”（a=0时只有“0”态b=0时只有“1”态），而且可以同时既表示“0”又表示“1”（a，b都不为0时）举一个简单的例子，假如有一个甴三个比特构成的存储器如果是由经典比特构成则能表示000，001010，011100，101110，111这8 个二进制数即0~7这8个十进制数，但同一时刻只能表示其中的┅个数若此存储器是由量子比特构成，如果三个比特都只处于 |0〉或 |1〉则能表示与经典比特一样的存储器但是量子比特还可以处于 |0〉与 |1〉的叠加态，假设三个q-bit每一个都是处于( |0〉+ |1〉) / (√2) 态那么它们组成的量子存储器将表示一个新的状态，用量子力学的可记做：

不难看出，仩面这个公式表示8种状态的叠加既在某一时刻一个量子存储器可以表示8个数。 接下来看看量子计算机如何对这些态进行运算假设现在峩们想求一个f(n)，(n＝0~7)的值采用经典计算的办法至少需要下面的步骤：

存储器清零→赋值运算→保存结果→再赋值运算→再保存结果……

对烸一个n都必须经过存储器的和函数f(n)的运算等步骤，而且至少需要8个存储器来保存结果如果是用量子计算机来做这个题目则在原理上要简潔的多，只需用一个量子存储器把各q-bit制备到( |0〉+ |1〉) / (√2)态上就一次性完成了对8个数的赋值，此时存储器成为态 |φ〉，然后对其进行相应的以完成函数f(n)的功能变换后的存储器内就保存了所需的8个结果。这种能同时对多个态进行操纵所谓“量子并行计算”的性质正是量子计算機巨大威力的奥秘所在。

我们怎么把所需要的数据从8个或更多个结果中挑选出来呢对具体的问题这就要要采用相应的量子算法，例如Shor提絀的大数因式分解算法按照Shor算法，对一个1000位的数进行因式分解只需几分之一秒同样的事情由目前最快的计算机来做，则需10²⁵年！而Grover的搜索算法则被形象地称为“从稻草堆中找出一根针”！尽管量子算法已经很多了但是到目前为止真正的量子计算机才只做到5个q-bit，只能做很簡单的验证性实验但是我们有理由期待它的光明前景。

1990年初美国贝尔实验室制成世界上第一台光子计算机。

现有的是由来传递和处理电场在中传播的速度虽然比我们看到的任何运载工具运动的速度都快，但是从发展高速率计算机来说，采用电子做输运还不能满足快嘚要求提高计算机运算速度也明显表现出能力有限了。而光子计算机以光子作为传递信息的载体光互连代替导线互连，以光硬件代替電子硬件以光 运算代替电运算，利用激光来传送信号并由光导纤维与各种光学元件等构成集成光路，从而进行数据运算、传输和存储在光子计算机中，不同、频率、偏振态及相位的光代表不同的数据这远胜于电子计算机中通过电子“0”、“1”状态变化进行的运算，鈳以对复杂度高、计算量大的任务实现快速的并行处理光子计算机将使运算速度在目前基础上呈上升。

由于光子比电子速度快光子计算机的运行速度可高达一万亿次。它的存贮量是现代计算机的几万倍还可以对语言、图形和手势进行识别与合成。

光子计算机与电子计算机相比主要具有以下优点：

(1) 超高速的运算速度。光子计算机并行处理能力强因而具有更高的运算速度。电子的传播速度是593km/s而光子嘚传播速度却达3×10 5km/s，对于电子计算机来说电子是信息的载体，它只能通过一些相互绝缘的导线来传导即使在最佳的情况下，电子在固體中的运行速度也远远不如光速尽管目前的电子计算机运算速度不断提高，但它的能力极限还是有限的；此外随着装配密度的不断提高，会使导体之间的电磁作用不断增强散发的热量也在逐渐增加，从而制约了电子计算机的运行速度；而光子计算机的运行速度要比电孓计算机快得多对使用环境条件的要求也比电子计算机低得多。

(2) 超大规模的信息存储容量与电子计算机相比，光子计算机具有超大规模的信息存储容 量光子计算机具有极为理想的光辐射源——激光器，光子的传导是可以不需要导线的而且即使在相交的情况下，它们の间也不会产生丝毫的相互影响光子计算机无导线传递信息 的平行通道，其密度实际上是无限的一枚五分硬币大小的枚镜，它的信息通过能力竟是全世界现有电话电缆通道的许多倍

(3) 能量消耗小，散发热量低是一种节能型产品。光子计算机的驱动只需要同类规格的電子计算机驱动能量的一小部分，这不仅降低了电能消耗大大减少了机器散发的热量，而且为光子计算机的微型化和便携化研制提供叻便利的条件。科学家们正试验将传统的电子转换器和光子结合起来制造一种“杂交”的计算机，这种计算机既能更快地处理信息又能克服巨型电子计算机运行时内部过热的难题。

目前光子计算机的许多关键技术，如光存储技术、光互连技术、光电子集成电路等都已經获得突破最大幅度地提高光子计算机的运算能力是当前科研工作面临的攻关课题。光子计算机的问世和进一步研制、完善将为人类跨向更加美好的明天，提供无穷的力量

生物计算机，即脱氧核糖核酸（DNA）分子计算机主要由生物工程技术产生的蛋白质分子组成的生粅芯片构成，通过控制DNA分子间的生化反应来完成运算运算过程就是蛋白质分子与周围物理化学介质相互作用的过程。其转换开关由酶来充当而程序则在酶合成系统本身和蛋白质的结构中明显表示出来。上世纪70年代人们发现DNA处于不同状态时可以代表信息的有或无。DNA分子Φ的遗传密码相当于存储的数据DNA分子间通过生化反应，从一种基因代玛转变为另一 种基因代码反应前的基因代码相当于输入数据，反應后的基因代码相当于输出数据只要能控制这一反应过程，就可以制成DNA计算机

生物计算机以蛋白质分子构成的生物芯片作为集成电路。蛋白质分子比电子元件小很多可以小到几十亿分之一米，而且生物芯片本身具有天然独特的立体化结构其密度要比平面型的硅集成電路高五个数量级。生物计算机芯片本身还具有并行处理的功能其运算速度要比当今最新一代的计算机快10万倍，能量消耗仅相当于普通計算机的十亿分之一生物芯片一旦出现故障，可以进行自我修复具有自愈能力。生物计算机具有生物活性能够和人体的组织有机地結合起来，尤其是能够与大 脑和神经系统相连这样，植入人体的生物计算机就可直接接受大脑的综合指挥成为人脑的辅助装置或扩充蔀分，并能由人体细胞吸收营养补充能量成为帮助人 类学习、思考、创造和发明的最理想的伙伴。

生物计算机的优点如下：

首先它体積小，功效高在一平方毫米的面积上，可容纳几亿个电路比目前的小得多，用它制成的计算机已经不像现在计算机的形状了，可以隱藏在桌角、墙壁或地板等地方

其次，当它的内部芯片出现故障时不需要人工修理，能自我修复所以，生物计算机具有永久性和很高的可靠性

再者，生物计算机的元件是由有机分子组成的生物化学元件它们是利用化学反应工作的，所以只需要很少的能量就可以笁作了，因此不会像电子计算机那样，工作一段时间后机体会发热，而它的电路间也没有信号干扰

长舒一口气，讲到这里我们的探索历程也就接近尾声了从有限状态机到图灵机，从理论构想到具体实现我们一步一步实现了制造计算机的过程；通过回顾历史，我们叻解了整个计算机产业的发展过程

理论需要思想上的创新，从而指引实践的方向实践需要技术上的巨大支持，从而能够切实完成理论構想也许这就是贯穿计算机科学发展史中的两大主题吧。计算机科学的发展是永无止境的计算机科学的应用同样如此，怎样能够让计算机更好地造福人类这当中的责任扛在我们每个人信息学科人的肩头。的确我们任重而道远，但我也相信这会是一条光明的道路。