Content deleted Content added
Fixed improper wording Tags: Reverted Mobile edit Mobile web edit |
Undid revision 1237037293 by 71.89.163.119 (talk): keep sharper proposition |
||
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
==Definition==
| |||