《计算机导论第2章图灵机模型及数据编码基数》由会员分享，可在线阅读，更多相关《计算机导论第2章图灵机模型及数据编码基数（59页珍藏版）》请在金锄头文库上搜索。
1、内容提要,2.1 概述,2.2 图灵机,2.3 数据在计算机中的表示,2.1 概述,图灵机模型理论是计算机学科最核心的理论之 一，它是在总结前人制造计算机思想的基础上提出 的理论计算模型，它不仅指导了现代电子计算机的 设计，为计算机设计指明了方向，并且是算法分析 和程序语言设计的基础理论。尽管如此，图灵机模 型却并不复杂，也许正因为如此，才注定了其在计 算学科中所具有的强大生命力。掌握了图灵机理论， 等于获得了学习计算机系统知识的“金钥匙”。,2.2 图灵机,在第一台电子计算机ENIAC诞生的10年前即1936年，英 国数学家图灵发表了题为“论可计算数及其在判定问题中的 应用”On Compu
2、ter Numbers With an Application to the Entscheidungs Problem的学术论文，奠定了学术界公认的 现代电子计算机的理论和模型基础。 1、希尔伯特纲领20世纪初，逐步形成了关于数学基础研究的逻辑主义、 直觉主义和形式主义三大流派。其中，形式主义流派的代表 人物是数学家希尔伯特DHilbert。他在数学基础的研 究中提出了一个设想，其大意是：将每一门数学的分支形式 化，构成形式系统或形式理论，并在以此为对象的元理论即,元数学中，证明每一个形式系统的相容性，从而导出全部 数学的相容性，希尔伯特的这一设想， 就是所谓的“西尔伯特纲领”。“西尔伯特纲
3、领”的目标，其实质就 是要寻找通用的形式逻辑系统，该系 统应当是完备的，即在该系统中，可 以机械地判定任何给定命题的真伪。,DHilbert 希尔伯特,“西尔伯特纲领”的研究基础是逻辑和代数，主要源于19世纪 英国数学家乔治布尔GBoole所 创立的逻辑代数体系即布尔代数。 1854年，布尔在他的著作中成功地将 “真” 、“假”两种逻辑值和“与”、“或”、 “非”3种逻辑运算归结为一种代数。这 样，形式逻辑系统中的任何命题都可 用数学符号表示出来，并能按照一定 的规则推导出结论。尽管布尔没有将“布尔代数”与计算机联系起来，但 他的工作却为现代计算机的诞生作 了重要的理论准备。,GBoole 乔
4、治布尔,希尔伯特的工作建立在布尔工作的基础上，并使其进一步具 体化。希尔伯特对实现自己的纲领充满信心。然而，1931年， 奥地利25岁的数理逻辑学家哥德尔KGdel提出的关 于形式系统的“不完备性定理”中指出，这种形式系统是不存 在的，从而宣告了著名的“西尔伯特纲领”的失败。希尔伯特 纲领的失败同时也暴露了形式系统的局限性，它表明形式系 统不能穷尽全部数学命题，任何形式系统中都存在着该系统 所不能判定其真伪的命题。,“西尔伯特纲领”虽然失败了，但它仍然不失为人类抽象 思维的一个伟大成果，它的历史意义是多方面的。首先，“西尔伯特纲领”是在保全古典数学的前提下去排 除集合论悖论的，它给数学基础问题
5、的研究带来了全新的转 机。其次，希尔伯特纲领的提出使元数学得到了确立和发展。 最后，对计算学科而言，最具意义的是，希尔伯特纲领的失 败启发人们应避免花费大量的精力去证明那些不能判定的问 题，而应把精力集中于解决具有能行性的问题。,2、图灵对计算本质的揭示在哥德尔研究成果的影响下20世纪30年代后期，图灵 AMTuring从计算一个数的一般过程入手对计算的本 质进行了研究，从而实现了对计算本质的真正认识。根据图灵的研究，直观地说，所谓计算就是计算者人 或机器对一条两端可无限延长的纸带上的一串0和1执行指 令，一步一步地改变纸带上的0或1，经过有限步骤，最后得 到一个满足预先规定的符号串的变换过程
6、。图灵用形式化方 法成功表述可计算这一过程的本质。图灵的研究成果是哥德 尔研究成果的进一步深化，该成果不仅再次表明了某些数学 问题是不能用任何机械过程来解决的思想，而且还深刻揭示 可计算所具有的“能行过程”的本质特征。,图灵的描述是关于数值计算的，不过，我们知道英文字 母表的字母以及汉字均可以用数来表示，因此，图灵机同样 可以处理非数值计算。不仅如此，更为重要的是，由数值和 非数值英文字母、汉字等组成的字符串，既可以解释成 数据，又可以解释成程序，从而计算的每一过程都可以用字 符串的形式进行编码，并存放在存储器中，以后使用时译码， 并由处理器执行，机器码结果可以从高级符号形式即 程序设计语言机
7、械地推导出来。图灵的研究成果是：可计算性图灵可计算性。在进行 可计算性问题的讨论时，不可避免地要提到一个与计算具有 同等地位和意义的基本概念，那就是算法。算法也称为能行,方法或能行过程，是对解题计算过程的精确描述，它由 一组定义明确且能机械执行的规则语句、指令等组成。 根据图灵的论点，可以得到这样的结论：任一过程是能行的 能够具体表现在一个算法中，当且仅当它能够被一台图 灵机实现。图灵机等计算模型均是用来解决问题的，理论上的能行 性隐含着计算模型的正确性，而实际实现中的能行性还包 含时间与空间的有效性。,3、图灵机,为纪念图灵对计算机的贡献， 美国计算机博物馆于1966年 设立了“图灵奖”,计
8、算机是使用相应的程序来完成任何设定好的任务。,图灵机是一种思想模型， 它由三部分组成： 一个控制器，一条可以无限延伸的 带子和一个在带子上左右移动的读 写头。,根据图灵的观点可以得到这样的结论：凡是能用算 法方法解决的问题，也一定能用图灵机解决；凡是图灵机 解决不了的问题，任何算法也解决不了。今天我们知道， 图灵机与当时提出的用于解决计算问题的递归函数、演 算和POST规范系统等计算模型在计算能力上是等价的。它 们于20世纪30年代共同奠定了计算科学的理论基础。相比 于其他几种计算模型，图灵机是从过程这一角度来刻画计 算的本质，其结构简单，操作运行规则也较少，从而为更 多的人所理解。 图灵机的
9、特征图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，如图所示。图灵机,的带子被划分为一系列均匀的方格。读写头可以沿带子方向左 右移动，并可以在每个方格上进行读写。 写在带子上的符号为一个有穷字母表： S0,S1,S2,SP。 通常，可以认为这个有穷字母表仅有两个S0、S1字符，其中S0 可以看作是“0”，S1可以看作是“1”，它们只是两个符号，要说 有意义的话，也只有形式的意义。,由字符“0”和“1”组成的字母表可以表示任何一个数。 机器的控制状态表为q1, q2,qm,。通常，将一个图灵 机的初始状态设为q1，在每一个具体的图灵机中还要确定一 个结束状态qw。
10、一个给定机器的“程序”认为是机器内的五 元组qiSjSkR或L或Nql形式的指令集，五元组定义了 机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下：qi 表示机器目前所处的状态；Sj 表示机器从方格中读入的符号；Sk 表示机器用来代替写入方格中的符号；R、L、N 分别表示向右移一格、向左移一格、不移动；ql 表示下一步机器的状态。,图灵机的工作原理 机器从给定带子上的某起始点出发，其动作完全由其初始状态及机内五元组来决定。就某种意义而言，一个机器其实就是它作用于纸带上的五元组集。一个机器计算的结果是从机器停止时带子上的信息得到的。 4、冯诺依曼型计算机1946年2月14日
11、，世界上第一台数字电子计算机ENIAC在美国宾夕法尼亚大学研制成功。该机是使用电子线路来执行算术和逻辑运算以及信息存储的真正工作的计算机器，它的成功研制显示了电子线路的巨大优越性。但是，ENIAC的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯诺依曼及其同事完成了关于电子计算装置逻辑结构设计的研究报告，具体,介绍了制造电子计算机和程序设计的新思想，给出了由控 制器、运算器、存储器、输入和输出设备5类部件组成的， 被称为冯诺依曼型计算机或存储程序式计算机的组织 结构，以及实现它们的方法，为现代计算机的研制奠定了 基础，
12、至尽为止，大多数计算机采用的仍然是冯诺依曼型 计算机的组织结构，只是作了一些改进而已。因此，冯诺 依曼被人们誉为“计算机器之父”。,冯诺依曼型计算机的组织结构,John von Neumann 冯诺依曼,1949 EDSAC,存储程序工作原理 计算机的两个基本能力：一是能够存储程序，二是能够自动地执行程序。 计算机是利用“存储器”（内存）来存放所要执行的程序的，而称之为CPU的部件可以依次从存储器中取出程序中的每一条指令，并加以分析和执行，直至完成全部指令任务为止。,香侬是现代信息论的著名创始人。1938年，香侬在发表的论文中， 首次用布尔代数进行开关电路分析，并证明布尔代数的逻辑运算可 以通
13、过继电器电路来实现。阿塔纳索夫提出了计算机的三条原则： 1）以二进制的逻辑基础来实现数字运算，以保证精度； 2）利用电子技术来实现控制、逻辑运算和算术运算，以保证计算速度； 3）采用把计算功能和二进制数更新存储功能相分离的结构。,Claude Shannon,奠定现代计算机发展的重要人物和思想,2.3 数据在计算机中的表示,计算机中的数据和指令都是用二进制代码表示的，这是因为计算机的各组成部分是仅具有两个稳定状态的物理元件电子开关线路所组成。为此，要想深入学习计算机的各个部分，必须掌握二进制代码的有关知识。 计算机中用二进制代码表示数据信息有两种方法： 按“值”表示：在选定的进位制中正确地表示
14、出数值，包括数字、符号、小数点位置及正负号等。如“9.5”可表示为二进制的 “1001. 1”。 按“形”表示：按照一定的编码方法来表示数据。如用ASCII码表示“9.5”，其形式为0101101、0111001、0101110、0110101。,1、进位制数及其相互转化 (一)进位制数（进位计数制） 数制的定义：用一组固定的数字(数码符号)和一套统一的 规则来表示数值的方法就叫做数制(number system也称计数 制)。这一定义主要的内涵是： (1) 数制的种类很多，除了十进制数，还有二十四进制(24小 时为一天)，六十进制(60分为1小时，60秒为1分)，二进制(鞋、 袜、筷子等两只
15、为一双)，等等。 (2) 在一种数制中，只能使用一组固定的数字来表示数的大 小。数字在一个数中所处的位置称为数位。具体使用多少个 数字来表示一个数值的大小，就称为该数制的基数(base)。 例如，十进制数(Decimal),的基数是10，使用09十个数字，二进制数(Binary)的基数为 2，使用0，1两个数字。在计算机文献中，十进制数是在数 的末尾加字母D来标识。例如，1989D，表示十进制数1989。 一般情况下，1989就是一个十进制数，不在后面加D。二进 制数是在数的末尾加字母B来标识。例如，101B，表示二进 制数的101，即十进制数的5。 (3) 在一种数制中，有一套统一的规则。N
16、进制的规则是逢N 进1，或者借1为N。 权或称位权，是指数位上的数字乘上一个固定的数值。十 制数是逢十进一，所以对每一位数可以分别赋以位权100， 101，102，。 用这样的位权就能够表示十进制的数。,基数某一基数中的最大数是“基数减1”，而不是基数本身，如 十进制数中的最大数为(101)9，二进制数中的最大数为 (21)1；最小数均为0。数位、基数和位权是进位计数制中的三个要素。 采用二进制记数法原因目前，在计算机内部，数据的计算和处理都采用二 进制记数法，主要是由二进制数在技术操作上的可行性、可 靠性、简易性以及其逻辑性所决定的。 (1) 可行性若用十进制数，需要0，1，9等不同的10个基 数，用电子技术实现这10种状态就很困难。而用二进制数， 则只需0，1两个基数，要表示两个状态，这在电学技术上的,实现最为容易。例如，电灯的亮和灭，晶体管的导通和截止， 等等。 (2) 可靠性因二进制数只要两个状态，数字转移和处理就不 易出错，这样计算机工作的可靠性就高。 (3) 简易性二进制数运算法则简单。例如，二进制的加法、 积法法则都只有三个。运算法则少，使计算机运算器结构大 大简化，控制也可随之简化。 (4) 逻辑性由于二进制数只要0，1两个数码，可以代表逻辑 代数中的“假”和“真”，这就是在计算机中使用二进制的逻辑 性。,
