How Incomputable Is Kolmogorov Complexity?
How Incomputable Is Kolmogorov Complexity?
复制标题
DOI：
10.3390/e22040408
复制
发表时间：
2020-04-03
期刊：
影响因子：
--
通讯作者：
Vitányi PMB
中科院分区：
文献类型：
--
作者：
Vitányi PMB
柯尔莫哥洛夫复杂度是文件的最终压缩版本的长度（即，任何可以放在电脑里的东西）。从形式上讲，它是一个最短的程序的长度，文件可以从该长度重新构建。我们讨论了不可计算的Kolmogorov复杂性，这给我们留下了正式的漏洞，最近的方法来计算或近似Kolmogorov复杂性，哪些方法是有问题的，哪些方法是可行的。
Kolmogorov complexity is the length of the ultimately compressed version of a file (i.e., anything which can be put in a computer). Formally, it is the length of a shortest program from which the file can be reconstructed. We discuss the incomputability of Kolmogorov complexity, which formal loopholes this leaves us with, recent approaches to compute or approximate Kolmogorov complexity, which approaches are problematic, and which approaches are viable.
登录
查看更多内容
影响因子：
--
作者：
RADO, T
通讯作者：
RADO, T
影响因子：
--
作者：
SOLOMONOFF, RJ
通讯作者：
SOLOMONOFF, RJ
DOI：
10.1098/rsta.2012.0091
发表时间：
2013-02-13
影响因子：
5
作者：
Vitanyi, Paul M. B.
通讯作者：
Vitanyi, Paul M. B.
影响因子：
2.3
作者：
Soler-Toscano, Fernando;Zenil, Hector
通讯作者：
Zenil, Hector
影响因子：
2
作者：
BRADY, AH
通讯作者：
BRADY, AH