Content deleted Content added
Citation bot (talk | contribs) Altered pages. Add: isbn, volume, doi, series, pmid, bibcode, doi-access, authors 1-1. Removed URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. Upgrade ISBN10 to 13. | Use this bot. Report bugs. | Suggested by Jay8g | #UCB_toolbar |
someone tried to clean up an incredibly poor addition from this edit https://en.wikipedia.org/w/index.php?title=Kolmogorov_complexity&diff=prev&oldid=1241693496 but even after cleaning I think it is better to remove it entirely |
||
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.
==Definition==
| |||