Content deleted Content added
Citation bot (talk | contribs) Removed URL that duplicated identifier. Removed access-date with no URL. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Algorithmic information theory | #UCB_Category 17/22 |
Sentence was copy-pasted from paper and was suggesting the topic was going to be developed but it isn't, instead now points out to the relevant review papers. |
||
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.
==Definition==
| |||