NOTE: This is the summary of the entire Chapter 7 of Programmer's Guide to Theory. The content in italics is not included in this extract.
The algorithmic, or Kolmogorov, complexity of a string of symbols is the size of the smallest program that will generate it.
Kolmogorov complexity clearly depends on the machine used to host the program, but it is defined up to a constant which allows for the variation in implementation.
Most irrationals don’t have programs that generate them and hence their Kolmogorov complexity is infinite.
Kolmogorov complexity isn’t computable in the sense that there isn’t a single function or Turing machine that will return the complexity of an arbitrary string.
A C compressible string can be reduced by C symbols by a compression program.
A string that cannot be reduced by even one symbol is said to be incompressible. Such strings have to exist by a simple counting principle. This means that the majority of strings have a high Kolmogorov complexity.
A string with a high Kolmogorov complexity is algorithmically random.
Most random numbers are pseudo random in that they are theoretically predictable if not practically predictable. This includes examples of systems that are usually considered to be truly random, such as the toss of a coin. Clearly, with enough data, you can predict which face the coin will come down.
The only example of true randomness is provided by quantum mechanics where the randomness is built into the theory – there is no way of predicting the outcome with more information.
A Programmers Guide To Theory
Now available as a paperback and ebook from Amazon.
Contents
What Is Computer Science? Part I What Is Computable?
Linus Torvalds seems to have had a bit of a relapse lately in his efforts to moderate his comments on code. One of his latest outbursts merits more than a surface analysis.
Apache has unveiled its new logo to replace the long-standing feather logo. The organization will also be moving to using the name "ASF" rather than "Apache Software Foundation".
