机构名称：
¥ 1.0
柯尔莫哥洛夫-所罗门诺夫-柴廷（Kolmogorov，简称 Kolmogorov）复杂度由 Solomonoff [ 1 ] 和 Kolmogorov [ 2 ] 独立提出，后来柴廷 [ 3 ] 也提出了这一复杂度。该复杂度基于可以模拟任何其他图灵机的通用图灵机的发现 [ 4 , 5 ]。单个有限字符串的柯尔莫哥洛夫复杂度是能够正确生成该字符串作为输出的通用图灵机的最短程序的长度，也是对字符串所含信息量的度量。已经证明，虽然存在多种图灵机，但最短程序的长度是不变的，在底层图灵机的选择下，其差异最多为一个加法常数 [ 6 ]。柯尔莫哥洛夫复杂度理论广泛应用于问答系统 [ 7 ]、组合学 [ 8 ]、学习理论 [ 9 ]、生物信息学 [ 10 ] 和密码学 [ 11 , 12 ] 等领域。1985 年，Deutsch [ 13 ] 引入量子图灵机作为量子计算机的理论模型。量子图灵机扩展了经典图灵机模型，因为它们允许在其计算路径上发生量子干涉。Bernstein 和 Vazirani [ 14 ] 表明量子图灵机在近似意义上具有通用性。最近，一些研究者提出了一些柯尔莫哥洛夫复杂度的量子版本。Vitányi [ 15 ] 提出了量子柯尔莫哥洛夫复杂度的定义，它度量近似量子态所需的经典信息量。Berthiaume 等人 [ 16 ] 提出了一种基于柯尔莫哥洛夫复杂度的量子柯尔莫哥洛夫复杂度定义。 [16] 提出了一种新的量子比特串量子柯尔莫哥洛夫复杂度定义，即通用量子计算机输出所需字符串的最短量子输入的长度。Zadeh [17] 提出了模糊计算的第一个公式，他基于图灵机和马尔可夫算法的模糊化，定义了模糊算法的概念。随后，Lee 和 Zadeh [18] 定义了模糊语言的概念。Santos [19] 证明了模糊算法和模糊图灵机之间的等价性。接下来，Wiedermann [20] 考虑了模糊计算的可计算性和复杂性。利用 Wiedermann 的工作，Bedregal 和 Figueira [21] 证明了不存在可以模拟所有模糊图灵机的通用模糊图灵机。随后，李[22,23]研究了模糊图灵机的一些变体。他证明了
基于经典描述的模糊 Kolmogorov 复杂度
主要关键词
相关文件推荐
