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

《有限制的通用模糊图灵机研究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)代表集合任务．这个称为邱奇一图灵