有限制的通用模糊图灵机研究new

有限制的通用模糊图灵机研究new

ID:34612127

大小:360.39 KB

页数:8页

时间:2019-03-08

有限制的通用模糊图灵机研究new_第1页
有限制的通用模糊图灵机研究new_第2页
有限制的通用模糊图灵机研究new_第3页
有限制的通用模糊图灵机研究new_第4页
有限制的通用模糊图灵机研究new_第5页
资源描述:

《有限制的通用模糊图灵机研究new》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第35卷第3期陕西师范大学学报(自然科学版)Vo1.35No.32007年9月JournalofShaanxiNormalUniversity(NaturalScienceEdition)Sep.2007·专题研究·文章编号:1672—4291(2007)03—0001—08有限制的通用模糊图灵机研究李永明(陕西师范大学计算机科学学院,陕西西安710062)摘要:给出了模糊图灵机的几种等价形式,包括具有分明转移函数的模糊图灵机(FNTMc)、模糊图灵机(FNTM)以及模糊多带图灵机.利用模糊图灵机,

2、定义了模糊递归枚举语言与模糊递归语言,并给出它们的层次刻画,证明了不存在通用模糊图灵机;如果限制模糊集的隶属函数为单位区间[0,1]的固定有限子集D,对应的模糊图灵机称为限制型模糊图灵机,则存在通用的限制型模糊图灵机,RAg_这类图灵机可以以任意给定精度模拟其他模糊图灵机,从而通用模糊图灵机在逼近意义下是存在的.关键词:模糊算法;模糊计算;模糊图灵机;通用模糊图灵机中图分类号:TP301.6文献标识码:AStudyonrestricteduniversalfuzzyTuringmachineLIYo

3、ng—ming(CollegeofComputerScience,ShaanxiNormalUniversity,Xian710062,Shaanxi,China)Abstract:SeveralequivalentformulationsoffuzzyTuringmachines,includingfuzzynondeterministicTuringmachines(FNTM),fuzzynondeterministicTuringmachineswithcrisptransitionfunct

4、ion(FNTMc)andmulti—tapefuzzyTuringmachines,aregiven.ThenthenotionsoffuzzyrecursivelyenumerablelanguagesandfuzzyrecursivelanguagesaredefinedintermsofFNTMs.Thelevelcharacterizationsoffuzzyrecursivelyenumerablelanguagesandfuzzyrecursivelanguagesareexploit

5、ed.hisshownthatthereisnouniversalfuzzyTuringmachinethatcansimulateanyfuzzyTuringmachineonit.ButifthemembershipdegreeoffuzzysetsiSrestrictedtoafixedfinitesubsetDof[0,1J,thereisa(restricted)universalfuzzyTuringmachinewhichcansimulateanyrestrictedfuzzyTur

6、ingmachine(withmembershipdegreesinD)onit.Furthermore,therestricteduniversalfuzzyTuringmachinecanapproximateanyfuzzyTuringmachinewithagivenaccuracy,thatistosay,auniversalfuzzyTuringmachineexistsintheapproximatesense.Keywords:fuzzyalgorithm;fuzzycomputat

7、ion;fuzzyTuringmachine;universalfuzzyTuringmachineMRSubjeetclassification:68Qo5;03D10英国数学家图灵(AlanTuring)在1936年发表机,也就是以他名字命名的称之为图灵机的计算模的著名论文[宣告了现代计算机科学的形成.图灵型.图灵证明了存在一个通用图灵机可以模拟任何以一种抽象的方式描述了现在所说的可编程计算其他图灵机;进而,他宣称通用图灵机完全刻画了算收稿Et期:2007—03—21基金项目:国家自然科学基金资

8、助项目(10571112);国家重点基础研究项目(973)专项经费资助项目(2002CB312200);教育部科学研究重点资助项目(107106)作者简介:李永明,男,教授,博士研究生导师,主要从事拓扑学、格论和计算智能的研究.2陕西师范大学学报(自然科学版)第35卷法手段所能完成的所有任务,即所有可以用硬件执集,代表终状态(或接受状态)集;是从Q×r到幂行的算法都有通用图灵机上的等价算法完成相同的集Q×r×{L,尺})的映射,其中x)代表集合任务.这个称为邱奇一图灵

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。