Basic Results
In the following discussion, let K(s) be the complexity of the string s.
It is not hard to see that the minimal description of a string cannot be too much larger than the string itself - the program GenerateFixedString above that outputs s is a fixed amount larger than s.
Theorem: There is a constant c such that
Read more about this topic: Kolmogorov Complexity
Famous quotes containing the words basic and/or results:
“The basic rule of human nature is that powerful people speak slowly and subservient people quickly—because if they don’t speak fast nobody will listen to them.”
—Michael Caine [Maurice Joseph Micklewhite] (b. 1933)
“The peace conference must not adjourn without the establishment of some ordered system of international government, backed by power enough to give authority to its decrees. ... Unless a league something like this results at our peace conference, we shall merely drop back into armed hostility and international anarchy. The war will have been fought in vain ...”
—Virginia Crocheron Gildersleeve (1877–1965)