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

1、第四章计算领域的基本概念、李涛深度、4.1计算模型和二进制、4.1.1计算模型和图灵机、计算模型和图灵机、计算模型：表征计算概念的抽象形式系统或数学系统。在计算科学中，是具有状态转换特征的数学机器，可以表示、加工、改变、接收和输出被处理对象的数据或信息。计算模型的层次：计算特定问题(类)的计算方法；按照与计算方法相对应的过程完成计算特定类型问题所需的平台。在计算能力上具有一种等价性的形式系统。计算模型的模型(所有计算模型中包含的机制)、计算模型和图灵、图灵的观点和结论：算法能够解决的所有问题都可以通过图灵解决。图灵机无法解决的问题，任何算法都无法解决。与图灵机等价的计算模型：递归函数-计算PO

2、ST规范系统图灵机从过程的角度表征计算的本质，其结构简单，操作规则少，因此更多的人可以理解。图灵机、图灵机由两端可无限扩展的磁带、读写磁头、控制读写磁头操作的命令集组成。图灵机、带中写的符号为可怜的字母表S0、S1、S2、Sp。你可以认为这个可怜的字母表只有S0，S1两个字符。其中S0可以看作“0”，S1可以看作“1”，由“0”和“1”组成的字母表可以代表任何数字。“0”和“1”仅具有形式意义，因此其目的是将S0转换为“白色”，将S1转换为“黑色”，甚至“表”和“老虎”，从而切断直观连接，加深对布尔字段的值真、假、二进制机器本质的理解机器的控制状态表为Q1、Q2、qm。将图灵机的初始状态设置为

3、Q1，并在每个特定图灵机上确定退出状态qw。给定计算机的“程序”，计算机上qiSjSkR(或l或n) N)ql格式的命令集，5元组定义系统在特定状态下读取特定字符时的行为。五个因素的含义如下：qi表示机器当前的状态。Sj表示机器从正方形中读取的符号。Sk表示计算机写入正方形而不是Sj的符号。r、l、n分别表示向右移动一格，向左移动一格，不移动。Ql QL表示下一阶段系统的状态。机器计算结果是从机器停止时磁带上的信息获得的。如果q1S2S2Rq3命令和q3S3S3Lq1命令同时出现在机器上，则第一个命令在Q1期间读取S2，第二个命令读取S3，然后机器在两个箱子之间无休止地运行。此外，如果q3S2

4、S2Rq4和q3S2S4Lq6命令同时出现在计算机上，则机器处于Q3状态，并且从绳扫描到符号S2时会出现异义性问题，因此机器无法判断。例如，b表示空格，Q1表示机器的初始状态，Q4表示机器的退出状态，读取头对齐最右侧的第一个0的棋盘格，将带的输入信息设置为10100010，状态为初始状态Q1。规则如下：q 1101 lq2 q110 lq3 bbnq 4 q200 LQ 2 q211 L2 Q2 bbnq 4 q301 l302 q310l 3 Q3 bbnq 4计算为给定数量加1的10100011。上述命令计算S(x)x1函数。如果初始状态的复选框为空白(b)，则空白字符不会更改，读写头也不

5、会停止运行。图灵机的计算能力，第一，将图灵机视为识别器，即判断磁带的原始内容是否能被图灵机接受。假定图灵机从左到右扫描磁带的内容，然后接受停机时间，否则不接受。示例2图灵机可以设计为识别1000110，1001101，01010101011等序列。将图灵机的计算能力，第二，将图灵机视为生成器，对给定输入集的输出集进行了探讨，并研究了输入输出集特性之间的关系，研究了图灵机的生成能力。示例3具有In1n0nnN的图灵机输入集，并且可以设计用于为给定输入集In获取输出集Out0n1nnN的图灵机。其中n是总自然数的集合。图灵机的计算能力，第三，将图灵机看作计算器相当于函数。图灵机的输入是函数的参数值

6、，图灵机的输出是函数的值。示例4图灵机可以计算以下函数：(1)s(x)x1；(2)o(x)0；(3)A(0，y)y1，A(x1，0)A(x，1)，A(x1，y1)A(x，A(x1，y)，图灵机的计算能力，第一和第二个函数读者不难从图灵机的定义中认识到，它们是图灵机可以计算的函数，而第三个函数更复杂，有时难以判断。请注意，第三个函数是在研究原始递归函数和递归函数的关系时由ackermann (W.Ackermann)提供的邪恶函数。这个函数在计算理论中有重要的价值。实际上，图灵机可能会计算比第三个函数形式更复杂的函数。图灵机的计算能力，图灵机为S(x)x1(后续函数)，N(x)0 (0函数)，U

7、i(n)(x1，x2，xn)xi，1in()在递归理论中，我们知道这三个函数属于初始递归函数，所有原始递归函数都是通过这三个初始递归函数的有限组合、迭代和最小化操作获得的。从可计算理论可以看出，每个原始递归函数都可以由图灵机计算。4.1计算模型和二进制，4.1.2二进制，计算机的数字系统，计算机使用二进制数字系统。基本符号：0，1进制原则：2进制方法的优点：在物理上容易实现二进制运算的简单机器可靠性高的共性缺点：对人的可读性差。十进制数的表示法，把你的数字和它的权重相乘，再加上乘积。例如，对于：597.63=21 * 104 7 * 103 9 * 102 9 * 101 7 * 100 6

8、* 10-1 3 * 10-2任意小数：s=kn * 10n kn-1，计算机的数字系统，计算机使用二进制数字系统。二进制数与十进制数一样，表示数字的符号(数字)根据其在写入中的位置具有不同的值。基本符号：0，一进制原则：二进制方法的优点：在物理上容易实现二进制运算简单机器可靠性高的共性缺点：对人的可读性较差。二进制数字skn-1k 0 . k-mknnnnnkn-12n-1k 020k-m2-m-mki 2 in其中2是二进制基数，ki0，1，m，n是正整数。此外，读者除了基数不同外，还可以从小数和二进制数的一般表达式中获得灵感。二进制，二进制运算规则比十进制运算规则简单得多。只要设置两个二

9、进制数据之间的转换方法，二进制文件就有更多的优点。计算机的理论基础是逻辑和代数。当二进制数与仅使用“真”和“假”两个值的相同逻辑代数相连接时，为计算机的逻辑设计提供了方便的工具。乘以不同舍入系数之间的转换r进制数、数字及其权重，然后将乘积相加。例如，(111111.11)2=1 * 27 1 * 26 1 * 25 1 * 24 1 * 23 1 * 22 1 * 21 1 * 20 1 * 2-1 * 2-2=将十进制整数转换为二进制的整数“r商”方法(例如，268剩馀2340低217021702121001父级，因此，6810100002，二进制和十进制之间的转换十进制数，将十进制小数转换

10、为二进制“乘以r整数”方法，) 父0.31252=0.6250 . 6252=1 . 250 . 252=0 . 50 . 52=1.0因此，0.312510=0.01012，其他二进制计数之间的转换2，8，十六进制相互转换，每个八进制数对应3位二进制数。每个十六进制数是4位二进制数(1011010.10)2=(0011010.100)2=(132.4)8(1010.10)2=(01011010.1000)2=()字节：由8位二进制数字组成(byte=8bit)。k字节1K=1024byteM字节1M=1024KG字节1G=1024MT字节1T=1024G，非数字信息的表示法；西方字符：ASC

11、II代码：以7位二进制表示的字符；27=128个字符EBCDIC代码：以8位二进制表示的字符更广泛使用的是用于国家标准信息交换的汉字编码(GB2312-80标准)，是国家国家国家代码(GB 2312-80标准)。是双字节代码，用两个7位二进制代码表示一个汉字。4.2基于存储程序的计算机的基本结构和工作原理，4.2.1基于冯诺依曼的计算机，基于冯诺依曼的计算机，图灵机的出现为现代计算机的发明提供了重要的思路。图灵机的磁带可以看作是计算机的存储设备，数据可以存储在上面，也可以根据需要擦除。图灵机的命令对应于一系列预先设计和存储的过程，它们决定了控制器计划下读取和写入头部的每个步骤。这种数学机器不考

12、虑其实用性，在思想或原理上确实包含了存储程序的重要思想。计算机程序是指可以在计算机系统上运行的程序。今天的计算机都称为存储程序式通用电子数字计算机。意思是计算机用数字代码(例如指令、数字数据、文字、图像等)显示各种信息。在物理机制中，数字代码表示为数字信号。信息表示数字化-理解计算机工作原理的基本起点。冯诺依曼计算机是当前模拟信号的两种类型，它是时间上连续的信号，使用信号的特定参数(如振幅)模拟信息。数字信号：在时间或空间中不连续(不连续)的信号。基于冯诺依曼的计算机，以数字方式表示信息：抗干扰能力，高可靠性。数字增加时，数字的表示范围会扩大，以表示更准确的数字。可以在物理上轻松实现和存储。表

13、示信息的类型和范围很广。可以用逻辑代数等数字逻辑技术处理。ENIAC的结构有基于von neumann的计算机、主线结构和其他问题，该计算机根据机械和电气系统设计得很大。受图灵等工作的影响，1946年6月，美国杰出数学家冯诺依曼和他的同事撰写了一份研究报告，称电子计算机和程序设计的新想法存储程序、顺序控制迄今为止，大部分计算机仍然采用基于冯诺依曼的计算机的组织结构，只做了一些改进。因此冯诺依曼被称为“计算机器之父”。von neumann计算机的组织结构、输入和输出设备、输入和输出设备、角色：将信息输入计算机并将信息输出到计算机。常用的字符输入设备(包括扫描仪、打孔卡读取器、鼠标等专用输入设备

14、)在键盘上按下下一个键时，所按的键通过代码转换为机器可读的数据形式。例如，文字“a”转换为ASCII代码“100001”，此编码数据保存以供保存，并通过与“100001”对应的文字光栅数据在屏幕上显示文字“a”。输出设备包括打印机、显示器、绘图仪和磁记录设备。存储、存储和存储是数据或信息的存储组件，它们分为多个存储单元，以一定的方式排列。每个单元都有一个编号，称为存储地址。指令和数据存储在阵列中，指令和数据不分大小地发送到运算。默认情况下，指令按执行顺序存储，指令计数器指示要执行的指令在阵列上的地址。存储、存储通常分为两类：内部存储和外部存储。内存通常安装在主板上，可以分为随机内存(RAM)和

15、只读内存(ROM)，具体取决于材料和工作方式。控制器和运算器只接受存储在内存中的指令和数据。附件通常安装在主板外部。例如，磁盘是典型的外部存储。上面的信息可以长期保存，但在用于控制器和计算计量器之前，必须先读入内存。磁盘可以根据材料分为软盘和硬盘。CPU(操作符和控制器)、centralprocessingunit、Register、控制单元、控制计算机中数据操作的电路没有直接连接到主存储。这些电路包含在CPU中，作为其自己的存储单元(register)Register存储CPU上运行数量的临时空间利用总线CPU提供存储单元目标地址和读取信号以选择数据；读取CPU提供存储单元目标地址和写入信号

16、以部署；信号写入谁发明了什么程序存储；概念：根据宾夕法尼亚大学Moore electronics institute的J.P.Echert，Johnson首先发表了程序存储的概念，在CPU和主存储通过总线连接的情况下4.3数字逻辑构成计算机的逻辑部件可以分为组合逻辑电路和顺序逻辑电路两种。组合逻辑电路：与门电路(而不是门、门和门)组合的逻辑电路。顺序逻辑电路：具有记忆体功能的逻辑电路，由触发器和闸电路组成。门电路，and门电路：2个以上输入，1个输出。仅当所有输入均为1时，输出为1。P=ABC”或“门回路：多个输入，一个输出。仅当一个输入为1时，输出为1。P=A B C“非”浇口回路：一个输入，一个输出。如果输入为1，则输出为0。如果输入0，则输出为1。门电路、“和”、“或”、“不”三门电路图PPABCABCA(a)(b)(c)、4.4机器命令和装配语言、4.4.1机器命令和机器命令程序由指令组成。每个