计算机科学导论-计算思维程序实践 课件 扩展第3、4讲-计算机的基础理论模型-图灵机、机器是怎样处理符号与小数点的

扩展第3讲

计算机的理论模型-图灵机战德臣哈尔滨工业大学计算学部教学委员会主任国家教学名师理解图灵机模型

图灵机与算法和可计算性的关系图灵机模型对现代计算机的启示图灵机的一个重要应用—形式语言及其识别本讲讲什么内容提要图灵(AlanTuring,1912~1954)，出生于英国伦敦，19岁入剑桥皇家学院，22岁当选为皇家学会会员。1937年，发表了论文《论可计算数及其在判定问题中的应用》，提出了图灵机模型，后来，冯·诺依曼根据这个模型设计出历史上第一台电子计算机。1950年，发表了划时代的文章：《机器能思考吗?》,成为了人工智能的开山之作。计算机界于1966年设立了最高荣誉奖：ACM图灵奖。图灵是谁图灵及其贡献图灵的贡献重要在哪里呢？你能查阅一下哪些人获得图灵奖了吗？因为什么贡献而获奖呢？所谓计算就是计算者(人或机器)对一条两端可无限延长的纸带上的一串0或1，执行指令一步一步地改变纸带上的0或1，经过有限步骤最后得到一个满足预先规定的符号串的变换过程。…10001110110011010110001…0110101由“程序”控制，一步步将输入“转换”为输出输入输出程序通用机器图灵机的基本思想什么是计算—图灵的观点关于数据、指令、程序及程序/指令自动执行的基本思想。输入被制成一串0和1的纸带，送入机器中----数据。如00010000100011…机器可对输入纸带执行的基本动作包括：“翻转0为1”，或“翻转1为0”,“前移一位”,“停止”。对基本动作的控制----指令，机器是按照指令的控制选择执行哪一个动作，指令也可以用0和1来表示：01表示“翻转0为1”(当输入为1时不变)，10表示“翻转1为0”(当输入0时不变),11表示“前移一位”,00表示“停止”。输入如何变为输出的控制可以用指令编写一个程序来完成,如:011110110111011100…

机器能够读取程序，按程序中的指令顺序读取指令，读一条指令执行一条指令。由此实现自动计算。图灵机的基本思想什么是计算—图灵的观点基本的图灵机模型为一个七元组,如右图几点结论:(1)图灵机是一种思想模型，它由一个控制器(有限状态转换器)，一条可无限延伸的带子和一个在带子上可完成读写的读写头构成，纸带可以向右或向左移动，或者说，读写头可以向左或向右移动。(2)

一个图灵机就是一个程序。程序是五元组<q,X,Y,R(或L或N),p>形式的指令集。其定义了机器在一个特定状态q下从方格中读入一个特定字符X时所采取的动作为在该方格中写入符号Y,然后纸带向右移一格R(或向左移一格L或不移动N),同时将机器状态设为p供后续操作使用。图灵机模型图灵机是什么M=（Q，

，

，

，S，B，F）其中：Q:状态的有穷集合

：输入字母表

：带符号表

S:开始状态F：终止状态集合B或b:空白符号

：移动函数，&(q,X)=(p,Y,R或L或N)表示M在状态q时读入符号X,则将状态改为p,并在X所在的带方格中印刷符号Y，然后将纸带向右/向左移动一格或者不动；（注：也可定义读写头向右/向左移动一格。读写头向右移动即纸带向左移动。这里定义是纸带向右/向左移动，便于后续示例一致性）…bb11100bb…状态qi控制器(有限状态转换器)读写头一个具体的图灵机示例(q1,0,0,L,q1)(q1,1,1,L,q2)(q2,1,1,L,q2)(q2,0,1,R,q3)(q3,1,1,R,q3)(q3,0,0,N,q4)q1q2q3q41,1,L1,1,L0,1,R1,1,R0,0,NQ={q1,q2,q3,q4}其中q1：开始状态q2：右移状态q3：左移状态q4：停机状态

={0,1}

带字符集={0,1,b}S={q1}F={q4}B/b空白字符&--移动函数/指令集0,0,L理解图灵机模型图灵机【示例1】指令集（移动函数）状态图（或状态输入转换图）

(注:(q,X,Y,L,p),状态图中圆圈内的是状态，箭线上的是<X,Y,L>,表示读出X时则写入Y并向左移动。L位置也可以是R(向右移动)或N(不动))。M=（Q，

，

，

，S，B，F）与通常【程序】（一条接一条执行的指令集合）的差异依据【当前状态】和【输入】决定执行哪条指令功能：将一串连续1的后面再加一位1001111000控制器q1q2q3q41,1,L1,1,L0,1,R1,1,R0,0,N0,0,L001100011你能否用另一个输入模拟一下这个程序的执行呢?001111000001111000(q1,0,0,L,q1)(q1,1,1,L,q2)001111000(q2,1,1,L,q2)001111000(q2,0,1,R,q3)001111100(q3,1,1,R,q3)001111100(q3,0,0,N,q4)理解图灵机模型图灵机计算过程【示例1】纸带向左移，读写头向右移该图灵机能处理完给定的输入吗？后面再讨论图灵机模型示例另一个示例（空白输入开始）0101

0101

1101

1001

1011

1010(q1,b,b,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)q1q2q3b,b,L1,0,Lb,b,N1,0,R0,1,R0,1,L注：纸带的左移(相当于读写头的右移)，纸带的右移(相当于读写头的左移)。状态图中标示的是纸带的移动.(q1,1,0,R,q1)(q1,0,1,R,q2)(q1,b,b,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)图灵机模型示例另一个示例（从纸带1处开始）q1q2q3b,b,L1,0,Lb,b,N1,0,R0,1,R0,1,L注：纸带的左移(相当于读写头的右移)，纸带的右移(相当于读写头的左移)。状态图中标示的是纸带的移动.(q1,1,0,R,q1)(q1,0,1,R,q2)(q1,b,b,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)1101

1001

0001

0001

1001

110111111110(q1,1,0,R,q1)(q1,1,0,R,q1)(q1,b,b,L,q2)(q2,0,1,L,q2)(q2,0,1,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)图灵机模型示例另一个示例（从纸带0处开始）q1q2q3b,b,L1,0,Lb,b,N1,0,R0,1,R0,1,L注：纸带的左移(相当于读写头的右移)，纸带的右移(相当于读写头的左移)。状态图中标示的是纸带的移动.(q1,1,0,R,q1)(q1,0,1,R,q2)(q1,b,b,L,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)1100111011111111110111100(q1,0,1,R,q2)(q2,0,1,L,q2)(q2,1,0,L,q2)(q2,1,0,L,q2)(q2,b,b,N,q3)图灵机模型被认为是计算机的基本理论模型图灵机从初始状态开始对纸带上的输入符号进行处理，如果能够到达终止状态，则被认为是成功地完成一次计算，此时纸带上的符号就是输出。

当图灵机的输入纸带为X，运行指令集，如果能够到达终止状态且输出纸带变为期望的M(X)，则说图灵机求解了X。有一类特殊的问题，其输入为X，而输出是1（接受）或0（拒绝），则被称为【判定问题】。例如输入一个字符串，如果输出为1表明该字符串是可接受的符合规则的字符串，否则为不可接受的或者说不符合规则的字符串。图灵机从初始状态开始对纸带上的输入符号进行处理，如果输入处理完毕，且能够到达{接受、拒绝}等某一终止状态，则被认为是成功地完成了一次判定：输入被接受，或者输入被拒绝。图灵机是一种离散的、有穷的、构造性的问题求解思路，一个问题的求解可以通过构造其图灵机(即程序或算法)来解决。计算机是使用相应的程序或算法来完成任何设定好的任务。图灵可计算性继续看图灵机是什么q1q2q3b,b,L1,0,Lb,b,N1,0,R0,1,R0,1,L图灵机怎样才算结束并给出答案图灵可计算问题

一个问题“能否由A计算出B？”，利用图灵机做一个判定，即：如果能在A与B之间找到或设计出一个图灵机，使输入A停机得到的结果是B，就说明这个问题可解；否则就说明这个问题不可解。

图灵机根据指令集对输入进行处理，有的输入（初始状态与初始输入）可能导致停机（即能够到达某一终止状态）。有的输入则可能导致无限的执行序列（即不能够到达任一终止状态或停留在非终止状态）。【停机问题】：是否存在一个算法，对于任意给定的图灵机都能判定任意的【初始状态+初始输入】是否会导致停机。已经证明，这样的算法是不存在的，即停机问题是不可判定的。假设纸带上的符号串为与自然数n相关的编码。如果机器以此为输入，到达终止状态时，纸带上的符号串已改造为m相关的编码，则称机器计算了函数f(n)=m。如果一个函数以自然数为值域和定义域，并且有一个图灵机计算它，则称此函数为“可计算函数“。已有的关于可计算函数的另一些定义，如递归函数、λ可定义函数等，都等价于图灵机定义的可计算函数（为什么？同学可继续学习相关课程来回答）凡是能用算法方法解决的问题也一定能用图灵机解决;凡是图灵机解决不了的问题任何算法也解决不了。（为什么？同学可继续学习相关课程来回答）图灵可计算性继续看图灵机是什么q1q2q3b,b,L1,0,Lb,b,N1,0,R0,1,R0,1,L图灵机一定能停机吗？能否判定按计算规则(程序)对输入进行变换得到输出输入程序&指令(计算规则)输入/输出都是0和1的形式表达输出程序和指令也是0和1的形式表达程序可用状态转换图来表达图灵机模型对现代计算机的启示现代计算机的基本思想是否是图灵机的思想呢？图灵机模型对现代计算机的启示冯.诺依曼计算机:思想与构成M=（Q，

，

，

，S，B，F）其中：Q:状态的有穷集合

：输入字母表

：带符号表

S:开始状态F：终止状态集合B或b:空白符号

：移动函数，&(q,X)=(p,Y,R或L或N)表示M在状态q时读入符号X,则将状态改为p,并在X所在的带方格中印刷符号Y，然后将纸带向右/向左移动一格或者不动；（注：也可定义读写头向右/向左移动一格。读写头向右移动即纸带向左移动。这里定义是纸带向右/向左移动，便于后续示例一致性）…bb11100bb…状态qi控制器(有限状态转换器)读写头【存储程序】怎样能看出图灵机的影子呢计算机的基本部件CPU：中央处理单元(CentralProcessUnit)，将运算器和控制器集成在一块芯片上，形成微处理器。CPU、主存储器、I/O设备及总线成为现代计算机的四大核心部件。总线现代计算机里面，一个微处理器(芯片)可能包含多个CPU，即多核.图灵机模型对现代计算机的启示现代计算机运算器中央处理单元CPU控制器(主或内)存储器程序数据程序与数据的保存程序执行与数据计算图灵机模型对现代计算机的启示计算机非常简单：数据与程序，存储器与CPU形式计算理论课程：形式语言与自动机形式计算的基础是符号化和语言。形式语言与自动机是研究符号化表达(即形式语言)以及符号化识别与处理(即自动机)的理论。形式语言：字母表∑上满足一定条件的字符串的集合L，称为∑上的一种语言。例如，若是由26个英文字母(包括大小写)、标点符号和空格组成的字母表，则∑上那些符合英文单词组成规则和句子生成规则的字符串的集合，便是英语。再如，全部二进制整数也可看作一种语言，它是字母表{0，1}上所有字符串的集合。文法：文法是一类语言发生器。从一个文法G可以产生出一个语言L的各个句子，这些句子实际上是字符串。文法即是形式语言定义中需要满足的“条件”，即按文法产生的字符串(或说句子)才是该语言的字符串。自动机：自动机是一种符号处理系统，或者说语言识别器，即它能识别出符合一个语言文法的各个字符串(句子)。它根据状态、输入和规则决定下一个状态和输出。即：状态＋输入＋规则

状态迁移

+输出。典型系列课程介绍

计算机数学理论系列课程图灵机的重要作用—形式语言及其识别形式语言与自动机“模式”化语句的识别(形式语言的识别-符合一定文法的字符串的识别)V=C+C;标识符=常量+常量(形式语言的文法规则)S1S2S3S4V,V,R空格,null,R=,=,RC,C,RS5S6+,+,R空格,null,R空格,null,R空格,null,R空格,null,RS7;,null,NC,C,R空格,null,R;,null,N能识别两种模式“V=C;”和“V=C+C;”并能去除空格的图灵机示意图字母表{V，C，=，+，空格,;}；S1起始状态；S7终止状态；null表示什么也不写回。Result=7+10;(V,1)=(C,1)+(C,2);(V,2)=(C,3)+(C,4);图灵机的重要作用—形式语言及其识别语句模式的识别M=（Q，

，

，

，S，B，F）Value=8+20;形式计算理论课程：形式语言与自动机(Cont.1)典型系列课程介绍

计算机数学理论系列课程2型文法上下文无关语言1型文法上下文相关语言3型文法正则语言0型文法递归可枚举语言图灵机线性界限自动机下推自动机有限自动机语言规则语言识别和计算状态变换与控制图灵机的重要作用—形式语言及其识别形式语言的类别与识别机器【图灵机】是有更少约束的自动机理解图灵机模型

图灵机与算法和可计算性的关系图灵机模型对现代计算机的启示图灵机的一个重要应用—形式语言及其识别计算机的理论模型-图灵机为什么图灵机是计算机的理论模型你理解得怎么样呢？形式语言与自动机可计算性-计算理论设计语言并识别语言问题可计算性判断与算法需进一步学习扩展第4讲机器是怎样处理符号与小数点的？--机器数与定浮点数哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣信息表示[T]数值信息表示[T]非数值信息表示[K]进位制[K]机器数(有符号与无符号数)

[K]浮点数(小数)

[K]二进制/十进制/十六进制[K]进制转换[K]机器字长[ETP]减法转加法[K]机器数0的编码[QT]机器数的范围[EK]溢出及其逻辑判断[K]不同类型整数[EK]符号-阶码-尾数[QT]精度与范围[K]单精度与双精度[K]字符编码ASCII[EK]汉字编码[EK]内码(存储)[EK]外码(输入)[EK]字形码(输出)[ET]汉字处理过程[QT]不同编码的异同[K]Unicode[K]等长编码和变长编码[T]万事万物信息表示[KT]采样-量化-编码[T]语音信号编码[T]图像信号编码[K]位图[K]压缩编码[T]编码器（感知器）[T]编码(压缩)-解码(还原)信息变换(程序与算法)

[T]编码效率[K]压缩：有损与无损[T]视频信号编码[T]解码器（显示&输出）[EK]原码与补码[K]编码[K]知识

[T]思维

[S箭头]次序[Q]问题

[E]示例

[P]练习信息在计算机中的基本表示方法概览二进制十六进制十进制有0,1,2,3,4,5,6,7,8,9共十个数码数码的位置规定了数码的等级“权/数位”：10i逢十进一、借一当十。高数位的1相当于低数位的10表示法：128、(128)十、(128)D有0,1共两个数码数码的位置规定了数码的等级“权/数位”：2i逢二进一、借一当二。高数位的1相当于低数位的2表示法：(01001000)二、(01001000)B有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个数码数码的位置规定了数码的等级“权/数位”：16i逢十六进一、借一当十六。高数位的1相当于低数位的16与二进制转换简单：小数点开始向左向右分别处理，1位十六进制数对应为4位二进制数，或4位二进制数对应1位十六进制数。表示法：(15FE)十六、15FEH、0x15FE

0001010111111110日常使用机器内部使用辅助阅读机器数据计数制十进制、二进制、十六进制要熟悉和习惯二进制和十六进制【机器字长】是指机器内部进行数据处理、信息传输等的基本单元所包含的二进制位数，通常是8位、16位、32位、64位等。例：（78）十

转换成二进制数。不同字长的表示，结果是不同的

（1）（78）十

=（1001110）二

（2）（78）十

=（01001110）二

（3）（78）十

=（0000000001001110）二

（4）（78）十

=（00000000000000000000000001001110）二

溢出数的表示范围机器字长未考虑机器字长8位机器字长16位机器字长32位机器字长数值性信息与机器数机器数：机器字长假设：16位机器字长有符号数无符号数无符号机器数的表示范围：0

X<216，即0至65,535（0000000000000000）二

（1111111111111111）二

数的符号也用0和1表达，0表“+”号，1表“-”号（0000000000000000）二

（0111111111111111）二

（1000000000000000）二

（1111111111111111）二

有符号数的表示范围？有符号数的大小？数值性信息与机器数机器数：有符号数和无符号数有符号机器数的表示范围：-215<

X<215，即-32,767至+32,767+244+

111101000

11110100-244-

111101001

111101000

111101001

000010110

111101001

00001100十进制数二进制数机器数-原码机器数-反码机器数-补码加

00000001负数正数不同的机器数表示方法带符号的机器数：原码、反码和补码负数正数原码、反码和补码是一样的原码、反码和补码是不同的表示原码、反码和补码的表示范围也是不同的不同的机器数表示方法机器数：原码、反码和补码为什么要有补码:(1)0只有一种表示，可多表示一个数；(2)运算时符号位可一起参与运算;(3)减法可当作加法进行01010+)1110111100(10)+(-3)=(7)00111+)0001101010(+7)+(+3)=(+10)11001+)1010010110(-7)+(-12)=溢出11011+)1100100101(-5)+(-7)=(-12)5位机器字长（1位符号位，4位数值位）补码再求补即为原码受字长限制自动舍弃减法可用加法实现补码的加减法：符号位与数值位一起参与运算(+245.25)十+11110101.0100011110101.01000111101010100小数点默认在此位置(无需用符号表示)，机器中全部是小数0111101010100小数点默认在此位置(无需用符号表示)，机器中全部是整数定点数小数点的处理定点数：纯小数vs.纯整数(+245.25)十=0.24525103+11110101.0100011110101.0100浮点数00.1111010101002+800.111101010100

20100000

1000111101010100尾数?多少位;?精度指数/阶码?多少位；?数的范围符号小数点的处理浮点数：小数点位置的处理浮点数的指数又被称为阶码小数点如何处理(4)浮点数示例?-0.11101

2-1001

-1.1101

2-1010

S指数(8位)尾数(后23