Kolmogorov Complexity Theory over the Reals
Kolmogorov Complexity Theory over the Reals
复制标题
实数上的柯尔莫哥洛夫复杂性理论
DOI：
10.1016/j.entcs.2008.12.014
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Ziegler
中科院分区：
文献类型：
--
作者：
W.M. Koolen;M. Ziegler
Kolmogorov复杂性是可计算性理论、信息论和计算复杂性理论的一个组成部分--在比特和图灵机的离散设置中。另一方面，在真实的数上，BSS机（又称real-RAM）已经被建立为主要的计算模型。这个真实的领域已经被证明与经典复杂性和递归理论中的许多概念和结果具有自然的对应关系;尽管通常有相当不同的证明。本文研究了Montaña和Pardo（1998）提出的离散和真实的Kolmogorov复杂性之间的异同。
Kolmogorov Complexity constitutes an integral part of computability theory, information theory, and computational complexity theory—in the discrete setting of bits and Turing machines. Over real numbers, on the other hand, the BSS-machine (aka real-RAM) has been established as a major model of computation. This real realm has turned out to exhibit natural counterparts to many notions and results in classical complexity and recursion theory; although usually with considerably different proofs. The present work investigates similarities and differences between discrete and real Kolmogorov Complexity as introduced by Montaña and Pardo (1998).
登录
查看更多内容
实数上的波斯特问题的显式解
DOI：
10.1016/j.jco.2006.09.004
发表时间：
2005
期刊：
ArXiv
影响因子：
--
作者：
K. Meer;M. Ziegler
通讯作者：
M. Ziegler
真实结构复杂性理论综述
DOI：
10.36045/bbms/1105730626
发表时间：
1997
影响因子：
0.5
作者：
K. Meer;C. Michaux
通讯作者：
C. Michaux
多排序代数上的可计算函数和半可计算集
DOI：
10.1093/oso/9780198537816.003.0008
发表时间：
2001
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
J. V. Tucker;J. Zucker
通讯作者：
J. Zucker
真实图灵机环境中的柯尔莫哥洛夫复杂度
DOI：
10.1016/s0020-0190(98)00089-1
发表时间：
1998
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
J. L. Montaña;L. M. Pardo
通讯作者：
L. M. Pardo
透明长证明：NPR 的第一个 PCP 定理
影响因子：
3
作者：
K. Meer
通讯作者：
K. Meer