柯尔莫哥洛夫复杂性有多不可计算？
How Incomputable Is Kolmogorov Complexity?
作者信息
Vitányi Paul M B
机构信息
The National Research Center for Mathematics and Computer Science in the Netherlands (CWI), 1098XG Amsterdam, The Netherlands.
Department of Computer Science, University of Amsterdam, 1012 WX Amsterdam, The Netherlands.
出版信息
Entropy (Basel). 2020 Apr 3;22(4):408. doi: 10.3390/e22040408.
Abstract
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.
摘要
柯尔莫哥洛夫复杂度是文件（即任何可存入计算机的内容）最终压缩版本的长度。形式上，它是能够重构该文件的最短程序的长度。我们将讨论柯尔莫哥洛夫复杂度的不可计算性、由此留下的形式漏洞、计算或近似柯尔莫哥洛夫复杂度的最新方法、哪些方法存在问题以及哪些方法可行。
相似文献
1
How Incomputable Is Kolmogorov Complexity?柯尔莫哥洛夫复杂性有多不可计算？
Entropy (Basel). 2020 Apr 3;22(4):408. doi: 10.3390/e22040408.
2
Fuzzy Kolmogorov Complexity Based on a Classical Description.基于经典描述的模糊柯尔莫哥洛夫复杂性
Entropy (Basel). 2020 Jan 4;22(1):66. doi: 10.3390/e22010066.
3
Approximate entropy (ApEn) as a complexity measure.近似熵（ApEn）作为一种复杂性度量。
Chaos. 1995 Mar;5(1):110-117. doi: 10.1063/1.166092.
4
Methods of information theory and algorithmic complexity for network biology.网络生物学的信息论与算法复杂性方法
Semin Cell Dev Biol. 2016 Mar;51:32-43. doi: 10.1016/j.semcdb.2016.01.011. Epub 2016 Jan 21.
5
An Additively Optimal Interpreter for Approximating Kolmogorov Prefix Complexity.一种用于逼近柯尔莫哥洛夫前缀复杂度的加法最优解释器。
Entropy (Basel). 2024 Sep 20;26(9):802. doi: 10.3390/e26090802.
6
Analysis of Solar Irradiation Time Series Complexity and Predictability by Combining Kolmogorov Measures and Hamming Distance for La Reunion (France).结合柯尔莫哥洛夫测度和汉明距离对留尼汪岛（法国）太阳辐射时间序列的复杂性和可预测性进行分析
Entropy (Basel). 2018 Aug 1;20(8):570. doi: 10.3390/e20080570.
7
Discovering Neural Nets with Low Kolmogorov Complexity and High Generalization Capability.发现具有低柯尔莫哥洛夫复杂度和高泛化能力的神经网络。
Neural Netw. 1997 Jul;10(5):857-873. doi: 10.1016/s0893-6080(96)00127-x.
8
Prediction of protein structural features from sequence data based on Shannon entropy and Kolmogorov complexity.基于香农熵和柯尔莫哥洛夫复杂度从序列数据预测蛋白质结构特征。
PLoS One. 2015 Apr 9;10(4):e0119306. doi: 10.1371/journal.pone.0119306. eCollection 2015.
9
The complexity of proving chaoticity and the Church-Turing thesis.证明混沌性和图灵论文的复杂性。
Chaos. 2010 Sep;20(3):037103. doi: 10.1063/1.3489096.
10
Complexity measurement based on information theory and kolmogorov complexity.基于信息论和柯尔莫哥洛夫复杂度的复杂性度量。
Artif Life. 2015 Spring;21(2):205-24. doi: 10.1162/ARTL_a_00157. Epub 2015 Jan 26.
引用本文的文献
1
An Additively Optimal Interpreter for Approximating Kolmogorov Prefix Complexity.一种用于逼近柯尔莫哥洛夫前缀复杂度的加法最优解释器。
Entropy (Basel). 2024 Sep 20;26(9):802. doi: 10.3390/e26090802.
2
Information Theory Opens New Dimensions in Experimental Studies of Animal Behaviour and Communication.信息论为动物行为与交流的实验研究开辟了新维度。
Animals (Basel). 2023 Mar 26;13(7):1174. doi: 10.3390/ani13071174.
3
Ladderpath Approach: How Tinkering and Reuse Increase Complexity and Information.阶梯路径方法：试错与复用如何增加复杂性和信息。
Entropy (Basel). 2022 Aug 5;24(8):1082. doi: 10.3390/e24081082.
4
Consistent Quantification of Complex Dynamics via a Novel Statistical Complexity Measure.通过一种新型统计复杂性度量对复杂动力学进行一致量化。
Entropy (Basel). 2022 Apr 4;24(4):505. doi: 10.3390/e24040505.
5
A Multiscale Partition-Based Kolmogorov-Sinai Entropy for the Complexity Assessment of Heartbeat Dynamics.一种基于多尺度划分的柯尔莫哥洛夫- Sinai熵用于心跳动力学复杂性评估
Bioengineering (Basel). 2022 Feb 16;9(2):80. doi: 10.3390/bioengineering9020080.
6
Computational Creativity and Aesthetics with Algorithmic Information Theory.基于算法信息论的计算创造力与美学
Entropy (Basel). 2021 Dec 8;23(12):1654. doi: 10.3390/e23121654.
7
Kolmogorov Basic Graphs and Their Application in Network Complexity Analysis.柯尔莫哥洛夫基本图及其在网络复杂性分析中的应用。
Entropy (Basel). 2021 Nov 29;23(12):1604. doi: 10.3390/e23121604.
8
A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions.算法复杂度估计方法综述：选项、挑战与新方向
Entropy (Basel). 2020 May 30;22(6):612. doi: 10.3390/e22060612.
本文引用的文献
1
Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines.从小型图灵机的输出频率分布计算柯尔莫哥洛夫复杂度。
PLoS One. 2014 May 8;9(5):e96223. doi: 10.1371/journal.pone.0096223. eCollection 2014.
2
Similarity and denoising.相似性与去噪。
Philos Trans A Math Phys Eng Sci. 2012 Dec 31;371(1984):20120091. doi: 10.1098/rsta.2012.0091. Print 2013 Feb 13.
Zotero 插件