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?
AI is a complex beast, but it is based on some very simple and very powerful ideas that deserve to be better known as they throw much light not only on the way AI works but on the way the universe wor [ ... ]
It may be the depths of winter, but now is the time for Open Source organizations to be preparing their applications for Google Summer of Code. After a record-breaking year in 2025, Google is hop [ ... ]
