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

Study on restricted universal fuzzy Turing machine

作　　者：李永明[1] 

机构地区：[1]陕西师范大学计算机科学学院,陕西西安710062

出　　处：《陕西师范大学学报（自然科学版）》2007年第3期1-8,共8页Journal of Shaanxi Normal University：Natural Science Edition

基　　金：国家自然科学基金资助项目(10571112);国家重点基础研究项目(973)专项经费资助项目(2002CB312200);教育部科学研究重点资助项目(107106)

摘　　要：给出了模糊图灵机的几种等价形式,包括具有分明转移函数的模糊图灵机(FNTMc)、模糊图灵机(FNTM)以及模糊多带图灵机.利用模糊图灵机,定义了模糊递归枚举语言与模糊递归语言,并给出它们的层次刻画,证明了不存在通用模糊图灵机;如果限制模糊集的隶属函数为单位区间[0,1]的固定有限子集D,对应的模糊图灵机称为限制型模糊图灵机,则存在通用的限制型模糊图灵机,而且这类图灵机可以以任意给定精度模拟其他模糊图灵机,从而通用模糊图灵机在逼近意义下是存在的.Several equivalent formulations of fuzzy Turing machines, including fuzzy nondeterministic Turing machines （FNTM）, fuzzy nondeterministic Turing machines with crisp transition function （FNTMc） and multi-tape fuzzy Turing machines, are given. Then the notions of fuzzy recursively enumerable languages and fuzzy recursive languages are defined in terms of FNTMs. The level characterizations of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited. It is shown that there is no universal fuzzy Turing machine that can simulate any fuzzy Turing machine on it. But if the membership degree of fuzzy sets is restricted to a fixed finite subset D of [0,1], there is a （restricted） universal fuzzy Turing machine which can simulate any restricted fuzzy Turing machine （with membership degrees in D） on it. Furthermore, the restricted universal fuzzy Turing machine can approximate any fuzzy Turing machine with a given accuracy, that is to say, a universal fuzzy Turing machine exists in the approximate sense.

关 键 词：模糊算法 模糊计算 模糊图灵机 通用模糊图灵机 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]