计算机科学导论-计算思维程序实践 课件 扩展第3讲-计算机的基础理论模型-图灵机

扩展第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,