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?
Itential, which specializes in intelligent network and infrastructure orchestration, has announced FlowAI. This is an extension to the existing Intential Automation Platform which is intended to [ ... ]
It could have been good news that Qualcomm had taken over Arduino. Adding its financial muscle and processor resources to the very popular development environment could have, and still could, produce [ ... ]
