丘奇图灵论题.ppt

**第3章丘奇-图灵论题研究内容图灵机图灵机的变形算法的定义**图灵机概述图灵机与有穷自动机相似,但它具有无限大容量的存储且任意访问内部数据,是一种精确的通用计算机模型,能模拟实际计算机的所有计算行为图灵机具有以下两个性质具有有穷描述过程必须是由离散的、可以机械执行的步骤组成**图灵机基本模型基本模型包括一个有穷控制器一条含有无穷多个带方格的输入带一个读写头a1a2a3a4anB输入带读写头有限状态控制器图灵机结构示意图**图灵机的标准图灵机设计必须满足的三条标准它们应该是自动机,即在构造和功能等一般特点上应该和前面研究过的装置相同在描述、形式化定义和讨论方式它们应该尽量简单就可完成的计算而言它们应该尽量简单**图灵机的动作当读写头扫描输入带上一格(即输入一个字符)时,结合图灵机的当前状态,在有限控制器的控制下,图灵机将执行以下三个动作进行状态转移读写头在带上当前格写下新的符号决定读写头向右或者向左移一格**与有穷自动机的区别图灵机在带子上既然读也能写图灵机的读写头既然向左也能向右移动图灵机的带子是无限长的图灵机进入拒绝和接受状态将立即停机**图灵机与语言对于带上一串输入字符,图灵机从初始状态和带上最左边的字符开始,通过连续不断的扫描和执行相关动作,如果在某个时候进入终止状态,图灵机就接受输入串被一个图灵机所接受的全部字符串的集合,就是该图灵机所接受的语言设计图灵机M1,使得如果输入是B={ω#ω|ω∈{0,1}*}的成员,它就接受,否则就拒绝**图灵机的形式化定义图灵机M是一个7元组(Q,,,,q0,ept,qreject),其中Q、、都是有穷集合,并且Q是状态的有穷集合(相当于程序标号)是输入字母表,不包含空白符⊔(或者B)是带符号表,⊔(或者B)作为中除符号之外唯一特殊边界符q0开始状态,q0∈Q,对于一个给定的输入串,M从状态q0启动,eptQ,拒绝状态qrejectQ转移函数:Q\{ept,qreject}Q{L,R}**图灵机M是一个7元组(Q,,,,q0,B,F),其中Q、、都是有穷集合,并且Q是状态的有穷集合是输入字母表,不包含空白符B是带符号集,{B}∪⊆q0∈Q是初始状态F⊆Q是终止状态:QQ{L,R}称为转移函数,对某些状态q和某些带符号a,(q,a)可以定义(进入拒绝状态)图灵机的形式化定义(1)**δ:Q×ΓQ×Γ×{R,L}是,为M的移动函数δ(q,xi)=(p,y,R)表示M在状态q读入符号X,将状态改为p,并在这个X所在的带方格中印刷符号Y,然后将读头向右移一格x1xi-1qxixn⊢x1xi-1ypxi+1xnδ(q,xi)=(p,y,L)表示M在状态q读入符号X,将状态改为p,并在这个X所在的带方格中印刷符号Y,然后将读头向左移一格x1xi-1qxixn⊢x1pxi-1yxi+1xn图灵机所能接受的语言为L(M)={w∈*|q0w⊢M*α1pα2,p∈F}状态转移函数