计算的自动化1

第4章计算的自动化—计算机硬件从计算理论（计算技术）和计算硬件（计算工具）的角度论述数字电子计算机的原理与实现

可计算性与图灵

ENIAC——第一台数字电子计算机冯·诺依曼与计算机体系结构计算机硬件体系结构的发展计算机系统及其相关学科第4章计算的自动化—计算机硬件可计算性理论20世纪30年代开始，数理逻辑学家们首先开始探究计算的含义。可计算性理论（computabilitytheory）、计算复杂性理论（computationalcomplexitytheory）和自动机理论（automatatheory）得到了很大的发展，这一时期，图灵、丘奇、哥德尔等数学家为此做出了决定性的贡献。可计算性理论是研究计算的可行性和函数算法的理论，又称算法理论。它是算法设计与分析的基础，也是计算机科学的理论基础。可计算性理论在可计算理论中，是把问题分成可解的（能行的）和不可解的（不能行的）。例如：（1）对输入行97+35进行计算，得出99（按位逻辑或）（2）对输入行X2进行计算，得出2X（微分）（3）对一行汉字进行计算，得出一行英文（文字翻译）（4）输入公理和规则，得出一个结论（定理证明）上述四个问题的共同特点是：从输入得到输出必须每一步都能够具体进行。可计算性理论又例如下面的函数，它是一个完全定义的函数，但是不能具体地求出，因此是不可解的。为了回答究竟什么是计算、什么是可计算性等问题，人们采取的是建立计算模型的方法。从30年代到40年代，数理逻辑学家相继提出了四种模型，它们是递归函数、λ演算、图灵机和POST系统。可计算性理论这四种模型完全是从不同的角度探究计算过程或证明过程的。但这几种模型完全具有一样的计算能力（等价）。在这一事实基础上，最终形成了如今著名的丘奇—图灵论点：凡是可计算的函数都是一般递归函数（或都是图灵机可计算的，或都是λ演算可计算的，或都是POST系统可计算的）。这就确立了计算与可计算性的数学含义。一个比较直观的说法：所谓计算,就是从已知符号串开始，一步一步地改变符号串，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。可计算性理论

与计算具有同等地位和意义的基本概念是算法。从算法的角度讲，一个问题是不是可计算的，与该问题是不是具有一个相应的算法是完全一致的。一般而言，算法就是求解某类问题的通用法则或方法。也就是一系列计算规则或程序，即符号串变换的规则。莱布尼兹的贡献二进制莱布尼茨发明了微积分和乘法器，除此之外，他还研究出了二进制数的运算法则，系统地阐述了二进制计数法，初步创建了逻辑代数学。为现代计算机的发展奠定了坚实的基础。逻辑代数学1674年，他描述了一种能够解代数方程的机器。1675年，他为一种机械装置写了相应的逻辑推理，这样就指出了一个目标，即把推理归结为一种演算，并最终制成能够完成这些演算的机器。布尔的贡献逻辑变成代数1847年，乔治·布尔在逻辑的数学分析（TheMathematicalAnalysisofLogic）中分析了数学和逻辑之间的关系，并阐述了逻辑归于数学的思想。1854年，他出版了《思维的规律》（《TheLawsofThought》），布尔代数（BooleanAlgebra）问世了，数学史上树起了一座新的里程碑。布尔的贡献在亚里斯多德的古典逻辑中有这样一些句子，如：①所有的植物都是有生命的。②没有河马是聪明的。③有些人说英语。布尔逐渐意识到，在逻辑推理中，像“有生命的”、“河马”或“人”这样一些词的重要之处在于它所描述的所有个体的类（Class）或群体（Collection）：有生命事物的类、河马的类、人的类。布尔的贡献不仅如此，他还认识到这种类型的推理可以用一种关于这些类的代数来表达。布尔用字母来表示类，就像字母以前曾被用来表示数或算子一样。如果字母x和y表示两种特定的类，那么布尔就说，xy表示既在x中又在y中的事物的类。在某种意义上，布尔认为这种类的运算类似于数的乘法运算。然而，他发现了一个重要的区别：如果y仍然表示绵羊的类，那么yy表示的是什么呢？它必定表示既是绵羊又是绵羊的事物的类。但这与绵羊的类是一样的，所以yy=y。布尔的贡献与普通代数中的乘法的类比如果x和y表示两个类，则布尔将用xy表示那些既属于x又属于y的东西的类，他用这个记号是要暗示与普通代数中的乘法的类比。现在的术语：

xy被称为x和y的交集。

当x表示一个类时，方程xx=x总是真。这时布尔提出一个问题：在x表示一个数的普通代数中，什么时候方程xx=x为真？仅当x为0或1时方程才为真。布尔的贡献一条真理：

这样就必须把符号0和1解释成类。∵对于普通乘法运算0乘以任何数都等于0；1乘以任何数都等于那个数。即：如果只限于0和1两个值，那么逻辑代数就成了普通代数。0x＝0，1x＝x布尔的贡献∴对于类如果把0解释成一个没有任何东西属于它的类那么对于任何x，0x都将等于0即：0为空集如果1包含我们所考虑的每一个对象那么对于任何x，1x都将等于x

或者说

1是我们所要言说的全体。即：1为全集布尔的贡献布尔对“＋”和“－”的解释如果x和y表示两个类，布尔就用“x＋y”来表示“或者在x中，或者在y中的类”，今天它被称为x和y的并集。布尔本人的例子是：如果x表示“男人的类”，y表示“女人的类”

则“x＋y”就是“由所有男人和女人所组成的类”。

类“x－y”表示“在x中但是不在y中的事物的类”。如果x表示“所有人的类”，y表示所有孩子的类

那么“x－y”就表示“所有成年人的类”。

特别地，“1－x”将表示不在x中的事物的类，从而x＋（1－x）＝1布尔的贡献让我们看看布尔的代数是如何工作的。我们用普通代数的记号xx记作x2。于是布尔的基本规则可以写成x2＝x或x－x2＝0。根据通常的代数规则把这个方程因式分解，得到：x（1－x）＝0用语言来描述就是：没有任何东西可以既属于又不属于一个给定的类x。布尔的贡献布尔的逻辑体系不仅包含亚里斯多德的逻辑，而且远远超过了它。乔治·布尔的伟大成就就是一劳永逸证明了逻辑演绎可以成为数学的一个分支。尽管在亚里斯多德的先驱工作之后，逻辑学上曾经有过某些发展，但布尔却发现这门学科从本质上说仍然是两千年前亚里斯多德之后的样子。从布尔开始，数理逻辑就一直处于连续不断的发展之中。布尔其人乔治·布尔（GeorgeBoole，1815年～1864年）是皮匠的儿子。由于家境贫寒，布尔不得不在协助养家的同时为自己能受教育而奋斗。尽管他考虑过以牧师为业，但最终还是决定从教，而且不久就开办了自己的学校。在备课的时候，布尔不满意当时的数学课本，便决定阅读伟大数学家的论文。在阅读法国数学家拉格朗日的论文时，布尔有了变分方面的新发现。

注：变分是数学分析的分支，它处理的是寻求优化某些参数的曲线和曲面。布尔其人由于他对代数关系的对称有很强的感觉，在孤独的研究中，他首先发现了不变量，并把这一成果写成一篇高质量论文发表，此后尽管仍然留在小学教书，但已经开始和许多第一流的英国数学家交往或通信，其中有数学家、逻辑学家德·摩根。德·摩根定理：and语句转换成or语句1、not(aandb)=(nota)or(notb)2、not(aorb)=(nota)and(notb)天不下雨，我就不会淋湿=天在下雨，且我正在被淋湿警察总是说谎或者教师总是知道真相这个事实不是真的”变成了“警察不总是说谎，教师不总是知道真相”。布尔其人布尔此时已经在研究逻辑代数，即布尔代数。他把逻辑简化成极为容易和简单的一种代数。在这种代数中，适当的材料上的“推理”，成了公式的初等运算的事情，这些公式比过去在中学代数第二年级课程中所运用的大多数公式要简单得多。这样，就使逻辑本身受数学的支配。为了使自己的研究工作趋于完善，布尔在此后6年的漫长时间里，又付出了不同寻常的努力。1849年，他被任命位于爱尔兰科克的皇后学院的数学教授。布尔其人1854年，布尔出版了《TheLawsofThought》（《思维规律》），这是他最著名的著作。当时他已39岁，布尔代数问世了，数学史上树起了一座新的里程碑。这是他对符号逻辑诸多贡献中的第一次。几乎像所有的新生事物一样，布尔代数发明后没有受到人们的重视。欧洲大陆著名的数学家蔑视地称它为没有数学意义的哲学上稀奇古怪的东西，他们怀疑英伦岛国的数学家能在数学上做出独特贡献。布尔其人一直到布尔去世后的20世纪初，罗素在《数学原理》中认为，“纯数学是布尔在一部他称之为《思维规律》的著作中发现的。”此说一出，立刻引起世人对布尔代数的注意。今天，布尔发明的逻辑代数已经发展成为纯数学的一个主要分支。布尔在1855年结婚，他的妻子是皇后校园一位希腊文教授的侄女。1864年，布尔死于肺炎，肺炎是他在暴风雨天气中尽管已经湿淋淋的了仍坚持上课引起的。罗素悖论悖论是自相矛盾的命题。即如果承认这个命题成立，就可推出它的否定命题成立；反之，如果承认这个命题的否定命题成立，又可推出这个命题成立。如果承认它是真的，经过一系列正确的推理，却又得出它是假的；如果承认它是假的，经过一系列正确的推理，却又得出它是真的。悖论悖论有三种主要形式：

1．一种论断看起来好像肯定错了，但实际上却是对的（佯谬）。

2．一种论断看起来好像肯定是对的，但实际上却错了（似是而非的理论）。

3．一系列推理看起来好像无懈可击，可是却导致逻辑上自相矛盾。悖论世界文学名著《唐·吉诃德》中有这样一个故事：唐·吉诃德的仆人桑乔·潘萨跑到一个小岛上，成了这个岛的国王。他颁布了一条奇怪的法律：每一个到达这个岛的人都必须回答一个问题：“你到这里来做什么？”如果回答对了，就允许他在岛上游玩，而如果答错了，就要把他绞死。对于每一个到岛上来的人，或者是尽兴地玩，或者是被吊上绞架。有多少人敢冒死到这岛上去玩呢？一天，有一个胆大包天的人来了，他照例被问了这个问题，而这个人的回答是：“我到这里来是要被绞死的。”请问桑乔·潘萨是让他在岛上玩，还是把他绞死呢？如果应该让他在岛上游玩，那就与他说“要被绞死”的话不相符合，这就是说，他说“要被绞死”是错话。既然他说错了，就应该被处绞刑。但如果桑乔·潘萨要把他绞死呢？这时他说的“要被绞死”就与事实相符，从而就是对的，既然他答对了，就不该被绞死，而应该让他在岛上玩。小岛的国王发现，他的法律无法执行，因为不管怎么执行，都使法律受到破坏。他思索再三，最后让卫兵把他放了，并且宣布这条法律作废。这是一条悖论。理发师悖论在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。图灵的贡献1936年，阿兰•图灵通过对人的计算过程的分析，提出了一种抽象的计算模型──图灵机（TuringMachine）。图灵把人们用纸笔进行数学运算的过程看作下列两种简单的动作：而在每个阶段，人要决定下一步的动作，依赖于（a）此人当前所关注的纸上某个位置的符号（b）此人当前思维的状态。①在纸上写上或擦除某个符号②把注意力从纸的一个位置移动到另一个位置图灵的贡献为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：①一条无限长的纸带、②一个读写头、③一个状态寄存器、④一套控制规则。纸带被划分为一个个小格子，每个格子上包含一个来自有限字母表的符号，字母表中用一个特殊符号b表示空白。纸带上的格子从左到右依此被编号为012...，纸带的右端可以无限伸展。图灵的贡献读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。状态寄存器用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。控制规则它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。图灵机模型0101001011010010ABCJKLMNFProgramprogram①无限长的纸带②读写头③状态寄存器④控制规则图灵认为：这样一台机器就能模拟人类所能进行的任何计算过程。控制规则5元组(qi

Sj

Sk

R(L,N)q1)表示机器目前所处的状态表示机器从单元格中读入的符号表示机器将要写入单元格中的符号R、L和N分别表示向右(Right)移一格，向左(Left)移一格，不移动(NotMove)表示下一步机器的状态（当前状态，当前单元格内容，要写的值，移动方向，要输入的新状态）图灵机模型图灵的贡献假设：

b表示空格;

q1表示机器初始状态;

q4表示机器结束状态;

输入10100010;

读入头对准最右边第一个为0的方格;

状态是初始状态q1。

则按照下面规则，输出正确的计算结果。q101Lq2 1q110Lq3 2q1bbNq4 3q200Lq2 4q211Lq2 5q2bbNq4 6q301Lq2 7q310Lq3 8q3bbNq4 9图灵的贡献b10100010b1q2Programq2q1q101Lq2q110Lq3q1bbNq4q200Lq2q211Lq2q2bbNq4q301Lq2q310Lq3q3bbNq4q4输入：10100010输出：10100011S（x）＝x＋1后继函数图灵的贡献显然，最后的结果是10100011，即对给定的数加1。其实，以上命令计算的是这样一个函数：

S（x）＝x＋1（后继函数）当没有输入时，即初始状态所指的方格为空（b）时，不改变空格符号，读写头不动并停机。图灵的贡献图灵机不仅可以计算S(x)＝x＋1（后继函数）还可以计算N(x)＝0（零函数）Ui(n)(x1，x2，…，xn)＝xi，1≤i≤n（投影函数）以及这3个函数的任意组合从递归论中，我们知道这3个函数属于初始递归函数，而任何原始递归函数都是从这3个初始递归函数经有限次的复合、递归和极小化操作得到的。从可计算理论中，我们知道每一个原始递归函数都是图灵机可计算的。图灵的贡献为了纪念图灵在计算机领域奠基性的贡献，美国计算机学会决定设立“图灵奖”，从1956年开始颁发给最优秀的计算机科学家，它就像科学界的诺贝尔奖那样，是计算机领域的最高荣誉。姚期智，美国普林斯顿大学计算

机科学系讲座教授、美国科学院

院士、计算机科学理论学家，

2000年获得的图灵奖。是迄今为

止获得图灵奖的唯一一位华裔科

学家。图灵其人图灵（AlanTuring，1911～1954）出生在英国伦敦的帕丁顿(Paddington)其父JuliusMathisonTuring是一名英属印度的公务员。在图灵小时候，父亲经常来往于英伦和印度，由于对英属殖民地安全的忧虑，父亲把家庭留在英伦与朋友同住。图灵其人孩提时代性格活泼好动。3岁那年，他进行了首次实验尝试，把玩具木头人的胳膊掰下来栽到花园里，想让它们长成更多的木头人。8岁时，他开始尝试写作了一部科学著作，题名《关于一种显微镜》。图灵其人6岁的时候，他的父母为他在一间叫圣迈克尔的（St.Michael‘s）日间学校注了册。女校长很快就注意到他的天才，随后Marlborough学院的许多教育家也注意到这一点。1926年，他14岁的时候转到了在多尔瑟(Dorset)的Sherborne寄宿学校。开学的第一天，刚好遇上了大罢工。图灵决心要赶上第一天的课，独自从南桑普敦（Southampton）骑了六十英里的自行车去上学，途中还在一间旅社度过一宵。图灵其人图灵很早就表现出科学探究精神，他的老师认为：“阿兰的头脑可以像袋鼠般地跳跃。”在三个星期里自己学会阅读。1928年，图灵18岁(爱因斯坦已经49岁)的时候，他看到了阿尔伯特·爱因斯坦的著作，不但能够理解，而且能够从一段并没有明示的文字里推导出爱因斯坦的运动定律。1931年，他考入剑桥皇家学院。在哈代指导下学习。图灵其人大学毕业后留校任教，不到一年功夫，就发表了几篇很有份量的数学论文，被选为皇家学院最年轻的研究员，年仅22岁。1936年，图灵发表了一篇划时代的论文——《论可计算数及其在判定问题中的应用》，后被人改称《理想计算机》。论文里论述了一种“图灵机”。当世界上还没人提出通用计算机的概念前，图灵已经在理论上证明了它存在的可能性。图灵其人1936.9，图灵渡海到美国普

林斯敦大学读研究所，12月

他公开演讲他的计算理论，

但是几乎没什么人来听讲。当〈可计算数〉刊出时，也

没有引起大家的重视，只有

两个人向他索取抽印本。1938.8，图灵在邱奇的指导下获得了博士学位。他辞谢了冯诺曼邀请他担任助理的机会，也拒绝了他父亲要他留在美国的建议，他毅然决然地返回国王学院。图灵其人1939年，二战(1939年－1945年)爆发，图灵回到剑桥，曾担任英美联合的密码破译机关的顾问，协助军方破解德国的着名密码系统Enigma，帮助盟军取得了二战的胜利。在剑桥，图灵聆听了维特根斯坦关于数学基本原理(foundationsofmathematics）的讲座。他们激烈地争论，图灵为形式主义辩护，而维特根斯坦则认为把数学抬得太高而且不能发现任何绝对真理。图灵其人1950年10月，图灵的另一篇论文《机器能思考吗》（CanMachineThink?）发表，首次提出检验机器智能的“图灵试验”，从而奠定了人工智能的基础，使他再次荣膺“人工智能之父”称号。图灵其人在他的同事和学生中间，这位衣着随便、不打领带的著名教授，不善言辞，有些木讷害羞，常咬指甲。在剑桥，图灵是一个妇孺皆知的怪才，常有出人料想的举动。他每天骑自行车到离公寓3公里的一个叫布雷奇莱公园的地方上班，因常患过敏性鼻炎，一遇花粉，鼻涕不止。图灵就常戴防毒面具骑车上班，招摇过市，成为剑桥的一大奇观。图灵其人他的自行车链条经常在半道上掉落，要是换了别人，早就去车铺修理了。而图灵偏不，他在琢磨，发现这链条总是踏到一定的圈数时下滑，图灵在骑车时就特别留心计算，于是能做到在链条下滑前一刹那戛然停车！让旁人叹服不已，以为是在玩杂耍。后来，图灵居然在踏脚旁装了一个小的机械计数器，到圈数时就停，好换换脑筋想些别的问题。图灵的脑袋转得比自行车飞轮还快。图灵其人1954.6.8，图灵因食用浸过氰化物溶液的苹果死亡。判决他的死是自杀。但他母亲极力争论他的死是意外，因为他在实验室里不小心堆放了很多化学物品。丘奇－图灵论题

丘奇－图灵论题（TheChurch-Turingthesis）是计算机科学中以数学家阿隆佐·丘奇（AlonzoChurch，1903.6.14～1995.8.11）和阿兰·图灵命名的论题，它的内容是：“通过运行UTM上的恰当程序，每个能行过程都是可实现的。”该论题最基