Methods and applications of algorithmic complexity. Beyond statistical lossless compression (Q2122124)

According to traditional probability theory, when we flip a coin \(n\) times, we can get all \(2^n\) possible binary sequences with equal probability \(2^{-n}\). However, we will get suspicious if a coin falls heads 100 times in a row: we know that the resulting sequence 00\ldots0 is not random, while the sequence that we obtain from the actual flipping is random. This intuitive notion of randomness was formalized by algorithmic information theory based on the following natural idea: the sequence 00\ldots0 can be generated by a very short computer program, while any program that produces the actual flipping sequence 01\ldots cannot be much shorter than a program print(01\ldots) that simply prints this sequence bit by bit. To capture this difference, we can use Kolmogorov complexity \(K(x)\) -- defined as the shortest length \(|p|\) of a program \(p\) that generates the given string \(x\) (which is denoted as \(T(p)=x\)). A sequence is considered random if it cannot be generated by a program which is much shorter than the length \(|x|\), i.e., if \(K(x)\ge |x|-C\) for some small constant \(C\). This definition is not easy to use in practice, since \(K(x)\) is not algorithmically computable. To make this definition more practical, people take into account that \(p\) is, in effect, the lossless compression of \(x\), so Kolmogorov complexity \(K(x)\) can be viewed as the length of the shortest possible compression. From this viewpoint, a reasonable approximation to \(K(x)\) is the length of what we get if we apply one of the known lossless compression algorithms to the state \(x\). This idea provides reasonable results, but it has two serious limitations: first, it only works for sufficiently long sequences, and, second, it is not clear what to do if we want a more accurate approximation for \(K(x)\). To estimate \(K(x)\) for a short sequence, the authors propose the following natural idea: actually try all possible programs \(p\) of given length for a fixed amount of time, and choose the shortest program that produces \(x\). Clearly, as we increase the limits on length and time, we get closer and closer to \(K(x)\). A similar method is also used to estimate the conditional Kolmogorov complexity. Instead of the usual Turing machine with a 1-D tape, we can use Turing machines with 2-dimensional (and higher-dimensional) tapes (or even cellular automata -- which also, like Turing machines, can emulate all possible algorithms). The authors come up with ingenious algorithms that make this simulation feasible. For shorter time bounds, we get an approximation to time-bounded Kolmogorov complexity. This enables us to also distinguish strings obtained by a complex algorithm (for which the usual \(K(x)\) is small) from easy-to-compute ones. Another problem is that the value \(K(x)\) depends on what universal computational device we use. This is not critical for long strings, but it is essential for short ones. To avoid this problem, the authors use the universal semi-measure \(m(x)=\sum_{p: T(p)=x}2^{-|p|}\) instead of \(K(x)\). Asymptotically, \(-\log_2(m(x))\) is equivalent to \(K(x)\), but its between-devices difference is smaller. This is easy to explain: instead of selecting the program \(p\) with the smallest \(|p|\), this method averages over several programs, and averaging usually smoothes and thus decreases the differences. For the proposed method, the estimation time grows exponentially with the length \(|x|\), so this method cannot be directly applied to long strings \(x\). So, the authors propose to divide a long string \(x\) into smaller chunks, and estimate \(K(x)\) as the sum of estimates over these chunks -- taking into account possible correlation. This new estimate is used to gauge complexity of real-life graphs and networks. This estimate is also well correlated with human perception of complexity and randomness -- e.g., what people view as accidental coincidence and when they become suspicious. It is also correlated with human perception of beauty. The book starts practically from scratch: it defines Turing machines, Kolmogorov complexity, etc. So this book can be recommended not only to researchers in this area, but also to students and to researchers from other areas interested in complexity issues. Caution: the book is, at places, not well edited: e.g., Section 1.2.5 about Pearson correlation coefficient \(\rho\) first says (correctly) that \(\rho=0\) means the absence of correlation, but then says (wrongly) that \(\rho=0.001\) indicates a strong correlation.