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?
After a period of inactivity, the EC Open Source Programme Office (EC OSPO) has awarded a contract for organizing bug bounties on open source software.
As one door opens another closes. Just as we start to see some opening of the Android and Apple walled gardens Google is making a move to restrict who can create code for Android.
