Max-Lukasiewicz复合推理下的模糊图灵机

研究max-Lukasiewicz复合推理下的模糊图灵机。形式化定义了模糊图灵机——确定型模糊图灵机、非确定型模糊图灵机、带部分转移函数的非确定型模糊图灵机和多带模糊图灵机,研究了这几类模糊图灵机的关系。进而定义模糊图灵机上的模糊递归可枚举语言和模糊递归语言。得出结论:当接受模糊递归可枚举语言时,非确定型模糊图灵机和确定型模糊图灵机不等价;而接受模糊递归语言时,它们等价。

模糊图灵机的逼近性与通用性

模糊图灵机是模糊算法或模糊计算的形式模型.文中研究了模糊图灵机的几种变形,这包括基于max-★复合运算的非确定型模糊图灵机(简写为NFTM★,其中★为t-模),非确定型模糊图灵机(简写为NFTM),确定型模糊图灵机(简写为DFTM),以及这些变形的多带版本.得到了以下一些结论:第1,若t-模★不满足有限生成条件,则NFTM★,NFTM和DFTM一般不等价,这里等价指的是识别相同的模糊语言.但在逼近意义下等价,也即,NFTM★可以被NFTM以任意精度逼近,并给出了相关的构造.引入了模糊递归可枚举语言与模糊递归语言的概念,并利用递归可枚举语言与递归语言对其进行层次刻画.第2,如果限制NFTM★的模糊隶属函数的取值域为单位区间[0,1]的一个固定的有限子集D,则存在通用模糊图灵机,用该通用模糊图灵机可以模拟上述类型的限制型模糊图灵机.一般地,通用模糊图灵机在逼近意义下存在,该通用模糊图灵机可以以给定精度模拟任意类型的模糊图灵机.