图灵机的计算能力第二-广西大学计算机与电子信息学院

第4章计算学科中的基本概念李陶深[e-mail]4.1计算模型与二进制4.1.1计算模型与图灵机计算模型与图灵机计算模型：刻画计算这一概念的一种抽象的形式系统或数学系统。在计算科学中，是指具有状态转换特征，能够对所处理的对象的数据或信息进行表示、加工、变化、接收、输出的数学机器。计算模型的层次：计算某个（类）具体问题的计算方法；按照计算方法对应的程序完成某类问题特定计算所需要的平台。在计算能力上具有某种等价性的形式系统。计算模型的模型（一切计算模型所内含的机理）计算模型与图灵机图灵的观点及结论：凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。与图灵机等价的计算模型：递归函数λ-演算POST规范系统图灵机是从过程这一角度来刻画计算的本质，其结构简单、操作运算规则也较少，从而为更多的人所理解。图灵机图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，…bb10100010bbb…读－写头控制器状态ql图灵机写在带子上的符号为一个有穷字母表：{S0，S1，S2，…，Sp}。可以认为这个有穷字母表仅有S0、S1两个字符，其中S0可以看作是“0”，S1可以看作是“1”，由“0”和“1”组成的字母表可以表示任何一个数。由于“0”和“1”只有形式的意义，因此，也可以将S0改称为“白”，S1改称为“黑”，甚至，还可以改称为“桌子”和“老虎”，这样改称的目的在于割断与直觉的联系，并加深对布尔域中的值{真，假}，以及二进制机器本质的理解。机器的控制状态表为：{q1，q2，…，qm}。将一个图灵机的初始状态设为q1，在每一个具体的图灵机中还要确定一个结束状态qw。一个给定机器的“程序”机器内的五元组（qiSjSkR（或L或N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下：qi表示机器目前所处的状态；Sj表示机器从方格中读入的符号；Sk表示机器用来代替Sj写入方格中的符号；R、L、N分别表示向右移一格、向左移一格、不移动；ql表示下一步机器的状态。一个机器计算的结果是从机器停止时带子上的信息得到的。容易看出，q1S2S2Rq3指令和q3S3S3Lq1指令如果同时出现在机器中，当机器处于状态q1，第一条指令读入的是S2，第二条指令读入的是S3，那么机器会在两个方块之间无休止地工作。另外，如果q3S2S2Rq4和q3S2S4Lq6指令同时出现在机器中，当机器处于状态q3并在带子上扫描到符号S2时，就产生了二义性的问题，机器就无法判定。例子：b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，设带子上的输入信息是10100010，读入头位对准最右边第一个为0的方格，状态为初始状态q1。规则如下：q101Lq2q110Lq3q1bbNq4q200Lq2q211Lq2q2bbNq4q301Lq2q310Lq3q3bbNq4…bb10100010bbb…读－写头控制器状态ql计算结果是10100011，即对给定的数加1。…bb10100010bbb…读－写头控制器状态ql以上命令计算的是这样一个函数：S(x)＝x＋1。当没有输入时，即初始状态所指的方格为空格（b）时，不改变空格符，读写头不动并停机。图灵机的计算能力第一，把图灵机看作识别器，即判断带子上最初的内容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受，否则为不接受。例2一台图灵机可以设计成识别下面的序列：1000110,10011101,010101011。图灵机的计算能力第二，把图灵机看作生成器，对给定的输入集合，考察输出集合，并研究输入输出集合性质之间的关系，这就研究了图灵机的生成能力。例3设一台图灵机的输入集合为In＝{1n0n│n∈N}，可设计一台图灵机，对给定的输入集合In，得到输出集合Out＝{0n1n│n∈N}。其中，N是全体自然数的集合。图灵机的计算能力第三，把图灵机看作计算器，相当于一个函数。图灵机的输入是函数的自变量的值，图灵机的输出是函数的值。例4图灵机可以计算下列函数：(1)s(x)＝x＋1；(2)o(x)＝0；(3)A(0，y)＝y＋1，A(x＋1，0)＝A(x，1)，A(x＋1，y＋1)＝A(x，A(x＋1，y))。图灵机的计算能力第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数，而第三个函数就比较复杂，一时难于判断。顺便提一下，第三个函数叫做阿克曼函数，它是阿克曼（W.Ackermann）在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理论中具有重要价值。事实上，图灵机还可以计算形式上比第三个函数更复杂的函数。图灵机的计算能力图灵机可以计算S(x)＝x＋1（后继函数），N(x)＝0（零函数），Ui(n)(x1，x2，…，xn)＝xi，1≤i≤n（投影函数）上述3个函数的任意组合。从递归论中，我们知道这3个函数属于初始递归函数，任何原始递归函数都是从这3个初始递归函数经有限次的复合、递归和极小化操作得到的。从可计算理论可知每一个原始递归函数都是图灵机可计算的。4.1计算模型与二进制4.1.2二进制计算机的数字系统计算机采用的是二进制数字系统。基本符号：0、1进位原则：逢二进一优点：易于物理实现二进制数运算简单机器可靠性高通用性强缺点：对人来说可读性差十进制数的表示各位数字与它的权相乘，其积相加。例如:27997.63=21*104+7*103+9*102+9*101+7*100+6*10-1+3*10-2对于任意的十进制数：S=kn*10n+kn-1*10n-1+…+k1*101+k0*100+k-1*10-1+…+k-m+1*10-m+1+k-m*10-m(n1,m1)其中，10称为十进制的基数,ki∈{0,1,2,3,4,5,6,7,89}，m，n为正整数。小数点的位置不言自明。计算机的数字系统计算机采用的是二进制数字系统。二进制和十进制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。基本符号：0、1进位原则：逢二进一优点：易于物理实现二进制数运算简单机器可靠性高通用性强缺点：对人来说可读性差二进制数S＝knkn-1…k0.…k-m＝kn×2n＋kn-1×2n-1＋…＋k0×20＋…＋k-m×2-m-m＝∑ki×2ii＝n其中，2称为二进制的基数，ki∈{0,1},m,n为正整数。进一步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样。二进制数二进制的运算规则比十进制的运算规则简单得多。只要建立两种进制的数据之间的转换方法，那么，二进制将具有更多的优势。计算机的理论基础是逻辑和代数。当二进制与同样只使用“真”和“假”两个值的逻辑代数建立了联系后，这就为计算机的逻辑设计提供了便利的工具。不同进位计数制间的转换——R进制→十进制各位数字与它的权相乘，其积相加。例如:(11111111.11)2=1*27+1*26+1*25+1*24+1*23+1*22+1*21+1*20+1*2-1+1*2-2=(255.75)10(3506.2)8=3*83+5*82+0*81+6*80+2*8-1=(1862.25)10(0.2A)16=2*16-1+10*16-2=(0.1640625)10二进制与十进制间的转换——十进制→二进制十进制整数转换成二进制的整数“除R取余”法，例如：268余数234┄┄┄┄┄┄┄┄┄┄┄┄0低位217┄┄┄┄┄┄┄┄┄┄┄028┄┄┄┄┄┄┄┄┄┄┄124┄┄┄┄┄┄┄┄┄┄022┄┄┄┄┄┄┄┄┄┄021┄┄┄┄┄┄┄┄┄00┄┄┄┄┄┄┄┄┄1高位所以6810＝10001002二进制与十进制间的转换——十进制→二进制十进制小数转换成二进制小数“乘R取整”法，例如：高位0.3125×2=0.6250.625×2=1.250.25×2=0.50.5×2=1.0所以0.312510=0.01012不同进位计数制间的转换——二、八、十六进制的相互转换每位八进制数相当于三位二进制数每位十六进制数相当于四位二进制数(1011010.10)2=(001011010.100)2=(132.4)8(1011010.10)2=(01011010.1000)2=(5A.8)16(F7)16＝(11110111)2＝(11110111)2信息的存储单位位(bit)：度量数据的最小单位，表示一位二进制信息。字节(byte)：由八位二进制数字组成(1byte=8bit)。K字节1K=1024byteM字节1M=1024KG字节1G=1024MT字节1T=1024G非数值信息的表示西文字符：ASCII码：用7位二进制数表示一个字符，最多可以表示27=128个字符EBCDIC码：用8位二进制数表示一个字符，最多可以表示28=256个字符汉字：应用较为广泛的是国家标准信息交换用汉字编码(GB2312-80标准)，简称国标码。是二字节码，用二个七位二进制数编码表示一个汉字。4.2存储程序式计算机的基本结构与工作原理4.2.1冯·诺依曼型计算机冯·诺依曼型计算机图灵机的出现为现代计算机的发明提供了重要的思想。图灵机的带子可以看成是计算机的存储设备，数据可以存储在上面，也可以根据需要擦去。图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器安排下，决定读写头的每一步操作。这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，确实包含了存储程序的重要思想。冯·诺依曼型计算机计算机程序是指能够在计算机系统中运行的程序。现在的计算机全称为存储程序式通用电子数字计算机。其含义是：在计算机中各种信息用数字代码表示，如指令、数值型数据、字符、图像等。在物理机制上，数字代码以数字型信号出现。信息表示数字化----理解计算机工作原理的基本出发点。冯·诺依曼型计算机目前有两种电信号：模拟信号：一种在时间上连续的信号，用信号的某些参数（如幅值）去模拟信息。数字信号：一种在时间上或空间上不连续（离散）的信号。冯·诺依曼型计算机采用数字化方法表示信息的优点：抗干扰能力强，可靠性高。位数增多则数的表示范围扩大，可以表示更精确的数字。物理上容易实现，并可存储。表示信息的类型和范围极其广泛。能用逻辑代数等数字逻辑技术进行处理。冯·诺依曼型计算机ENIAC的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯·诺依曼（VonNeumann）及其同事完成了关于“电子计算装置逻辑结构设计”的研究报告，具体介绍了制造电子计算机和程序设计的新思想：存储程序、顺序控制至今为止，大多数计算机采用的仍然是冯·诺依曼型计算机的组织结构，只是作了一些改进而已。因此，冯·诺依曼被人们誉为“计算机器之父”。冯·诺依曼型计算机的组织结构存储器运算器控制器输入/输出设备命令寄存器输入设备和输出设备输入设备和输出设备作用：是将信息输入计算机和输出计算机。常用的文字输入设备是键盘（还有扫描仪、穿孔卡片读入机和鼠标等专用输入设备）当在键盘上按下一个键时，按下的键通过编码变换成机器可读的数据形式，如字符“A”变换成ASCII码“1000001”，该编码数据随即存入存储器等待处理，通过与“1000001”对应的字符点阵数据在屏幕上显示一个字符“A”。输出设备有打印机、显示器、绘图仪、磁记录设备等。存储器存储器存储器是一种数据或信息的存储部件，它分成很多存储单元，并按照一定的方式进行排列。每个单元都编了号，称为存储地址。指令和数据存放在存储器中,而且对指令和数据同等对待，都不加区别地送到运算器中运算。指令在存储器中基本上是按执行顺序存储的，由指令计数器指明