Content deleted Content added
Undid revision 1237037293 by 71.89.163.119 (talk): keep sharper proposition |
m Added extra information about incomputability of kolmogorov complexity (and added citation to that information) Tags: Visual edit Mobile edit Mobile web edit Advanced mobile edit |
||
Line 5:
The notion of Kolmogorov complexity can be used to state and [[Proof of impossibility|prove impossibility]] results akin to [[Cantor's diagonal argument]], [[Gödel's incompleteness theorem]], and [[halting problem|Turing's halting problem]].
In particular, no program ''P'' computing a [[lower bound]] for each text's Kolmogorov complexity can return a value essentially larger than ''P''<nowiki>'</nowiki>s own length (see section {{slink||Chaitin's incompleteness theorem}}); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts. 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.<ref>{{Cite journal |last=Vitányi |first=Paul M. B. |date=2020-04 |title=How Incomputable Is Kolmogorov Complexity? |url=https://www.mdpi.com/1099-4300/22/4/408 |journal=Entropy |language=en |volume=22 |issue=4 |pages=408 |doi=10.3390/e22040408 |issn=1099-4300}}</ref>
==Definition==
| |||