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

给出了模糊图灵机的几种等价形式,包括具有分明转移函数的模糊图灵机(FNTMc)、模糊图灵机(FNTM)以及模糊多带图灵机.利用模糊图灵机,定义了模糊递归枚举语言与模糊递归语言,并给出它们的层次刻画,证明了不存在通用模糊图灵机;如果限制模糊集的隶属函数为单位区间0,1]的固定有限子集D,对应的模糊图灵机称为限制型模糊图灵机,则存在通用的限制型模糊图灵机,而且这类图灵机可以以任意给定精度模拟其他模糊图灵机,从而通用模糊图灵机在逼近意义下是存在的.

Study on restricted universal fuzzy Turing machine

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 ,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.