|
|||||
|
|
| 模糊图灵机的逼近性与通用性 | |
| 作者姓名： | 李永明 |
| 作者单位： | [1]陕西师范大学计算机科学学院,西安710062 |
| 基金项目： | 国家自然科学基金资助项目（批准号：10551112）和国家重点基础研究（973）项目专项经费（批准号：2002CB312200）及教育部重点研究项目（批准号：107106）资助 |
| 摘 要： | 模糊图灵机是模糊算法或模糊计算的形式模型．文中研究了模糊图灵机的几种变形,这包括基于max-复合运算的非确定型模糊图灵机（简写为NFTM,其中为t-模）,非确定型模糊图灵机（简写为NFTM）,确定型模糊图灵机（简写为DFTM）,以及这些变形的多带版本．得到了以下一些结论：第1,若t-模不满足有限生成条件,则NFTM,NFTM和DFTM一般不等价,这里等价指的是识别相同的模糊语言．但在逼近意义下等价,也即,NFTM可以被NFTM以任意精度逼近,并给出了相关的构造．引入了模糊递归可枚举语言与模糊递归语言的概念,并利用递归可枚举语言与递归语言对其进行层次刻画．第2,如果限制NFTM的模糊隶属函数的取值域为单位区间[0,1]的一个固定的有限子集D3则存在通用模糊图灵机,用该通用模糊图灵机可以模拟上述类型的限制型模糊图灵机．一般地,通用模糊图灵机在逼近意义下存在,该通用模糊图灵机可以以给定精度模拟任意类型的模糊图灵机． |
| 关 键 词： | 模糊图灵机 模糊递归可枚举语言 模糊递归语言 通用模糊图灵机 模糊算法 |
| 本文献已被 维普 等数据库收录！ | |