turingmachine.doc_第1页
turingmachine.doc_第2页
turingmachine.doc_第3页
turingmachine.doc_第4页
turingmachine.doc_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

问题的种类：判定问题计算问题二者的关系1. p(x)-f(x)2. f(x)-f(x)n0f(n)cg(n)或者记为fg等价于nn2, n0.5n2-1010, nk=O(2n)可判定的语言，可枚举语言A*的一个子集L称为一个语言。语言L称为可判定的（可计算的），如果存在图灵机M满足x(xLM(x)到接受状态) x(xLM(x)到拒绝状态)语言L称为可枚举的（可接受的），如果存在图灵机M满足x(xLM(x)到接受状态) x(xLM(x)例子：L=w0,1*，w为偶数L=w0,1*且w中至少含有两个连续的0L=wwR: w0,1*.图灵机计算的函数设f(x1,x2,xm)为一m元部分函数。我们说f可计算当且进当存在图灵机M满足对于任意的自变量(x1,x2,xm)dom(f)，有M(x1,x2,xm)=f(x1,x2,xm)对于任意的自变量(x1,x2,xm)dom(f)， 有M(x1,x2,xm)。例子：f(x)=x/2f(x)=x+1f(x,y)=x+yf(x)无定义。f(x,y)=x/y。图灵机的其他形式五元组图灵机单向无穷带多带图灵机离线图灵机且输入带只能读，输出带只能写。L=wwR: w0,1*.非确定性图灵机基本模型基本组成1有限字符表C 2有限状态集Q3 状态转移空白字符B，初始状态q1，输入字母表AC-B，接受状态集FQ。非确定图灵机的执行过程输入开始状态q1初始格局q1a0a1an计算过程：d(q1,a0)=(ak, qk),(am,qm),(R, q)d(q1,a0)=重复上述过程输出：?例子：1: C=￥,$,B, F= q1d￥$Bq1($, q1) (R, q1)（￥, q1）(R, q1)格局，初始格局，后继格局，停机格局，接受格局。NTM可判定的语言。语言L称为NTM可判定的，如果存在非确定图灵机NTM满足x(xL存在一个计算路径停机到接受状态) x(xL所有的计算路径都停机到拒绝状态)语言L称为NTM可枚举的，如果存在非确定图灵机NTM满足x(xL存在一个计算路径停机到接受状态) x(xL所有的计算路径都不停机)例子：L=(x, y):x, y0,1*, 且x是y的子串NTM的计算时间分析。当L为NTM可判定的语言时，xL Time(NTM(
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论