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 thing nobody asks is why do people take drugs of any sort?... Why do we have these accessories to normal living to live? I mean, is there something wrong with society that’s making us so pressurized, that we cannot live without guarding ourselves against it?”
—John Lennon (1940–1980)
“The chief benefit, which results from philosophy, arises in an indirect manner, and proceeds more from its secret, insensible influence, than from its immediate application.”
—David Hume (1711–1776)