基本图灵机及图灵机的构造技术 0分课件.ppt

《基本图灵机及图灵机的构造技术 0分课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实现均衡的防护，系统防护效果以最薄弱处计算。防护的水平与风险和安全需求相适应，系统的防护级别与被防护对象的风险等级相适应。主要内容nTM的基本定义nTM的格局nTM接受的语言nTM的构造技术nTM的变形；n重点:TM的定义、TM的构造。n难点:TM的构造。SchoolofComputerScience&Technology,BUPT1实现均衡的防护，系统防护效果以最薄弱处计算。防护的水平与风险和安全需求相适应，系统的防护级别与被防护对象的风险等级相适应。Finitecontrol图灵机的基本模型带（tape）XXXXBB...12in单元格（cell）带符

2、（tapesymbol）n读写头在每一时刻扫描带上的一个单元n带有一个最左单元，向右则是无限的。n带的每个单元可容纳一个带符号开始时，最左边n个单元装着输入（n>＝0，n为有限数），它是一个字符串，符号都选自“带符号”的一个子集，即所谓的“输入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但不是S输choo入lof符Com号put。erScience&Technology,BUPT2实现均衡的防护，系统防护效果以最薄弱处计算。防护的水平与风险和安全需求相适应，系统的防护级别与被防护对象的风险等级相适应。图灵机的工作机制在一个图灵机的动作中

3、，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作n改变状态n在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.n将带头向左或者右移一个单元。*图灵机和双向有限自动机的区别：图灵机能改变它带上的符号。SchoolofComputerScience&Technology,BUPT3实现均衡的防护，系统防护效果以最薄弱处计算。防护的水平与风险和安全需求相适应，系统的防护级别与被防护对象的风险等级相适应。图灵机的形式化描述²形式定义一个图灵机TM(Turingmachine)是一个七元组M=(Q,T,,,q0,B,F).有限状态集有

4、限输入符号集有限带符号集q0Q转移函数T开始状态B–T特殊带符:空白符FQ终态集合转移函数:QQ{L,R}SchoolofComputerScience&Technology,BUPT4实现均衡的防护，系统防护效果以最薄弱处计算。防护的水平与风险和安全需求相适应，系统的防护级别与被防护对象的风险等级相适应。图灵机的函数与格局nδ函数示例：Q×∑→Q×∑×{L,R}δ(q,a)=(p,B,L)q,p∈Qiδ(q,a)=(p,b,R)a∈∑b∈∑iin格局用wqw描述图灵机的瞬间工作状态12q为M的当前状态，ww∈∑*12ww是当前时

5、刻从开始端（因为可写）到右边空白符号为止12的内容当读写头已达到带的右端，则ww为读写头以左的内容。12约定：wqw表示读写头正扫描w的最左字符122w＝则表示读写头正扫描一个空白字符。2SchoolofComputerScience&Technology,BUPT5实现均衡的防护，系统防护效果以最薄弱处计算。防护的水平与风险和安全需求相适应，系统的防护级别与被防护对象的风险等级相适应。图灵机的格局²给定图灵机M=(Q,T,,,q0,B,F)，定义格局之间的推导关系├M如下：1.设(q,Xi)=(p,Y,L)，则有X1X2…Xi-1qXiXi+1…

6、Xn├MX1X2…Xi-2pXi-1Y…Xn，但有如下两个例外：（1）i=1时，qX1X2…Xn├MqYX2…Xn，和（2）i=n及Y=B时，X1X2…Xn-1qXn├MX1X2…Xn-2pXn-1B.2.设(q,Xi)=(p,Y,R)，则有X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-1YpXi+1…Xn，但有如下两个例外：（1）i=n时，X1X2…Xn-1qXn├MX1X2…Xn-1YpB，和（2）i=1及Y=B时，qX1X2…Xn├MBpX2…Xn-1Xn.SchoolofComputerScience&Technology,BUPT6

7、实现均衡的防护，系统防护效果以最薄弱处计算。防护的水平与风险和安全需求相适应，系统的防护级别与被防护对象的风险等级相适应。图灵机接受的语言L(M)={ω│ω∈T*且qω├*αpα,p∈F,αα∈∑*}01212图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在M的带上，M处于状态q，且M的带头处0在最左单元上，这些字符串将使M进入某个终止状态。假定：当输入被接受时，图灵机将停止，没有下一个动作。SchoolofComputerScience&Technology,BUPT7实现均衡的防护，系统防护效果以最薄弱处计算。防护的水平与风险

8、和安全需求相适应，系统的防护级别与被防护对象的风险等级相适应。图灵