Kolmogorov Complexity And Algorithmic Randomness

Looking at a sequence of zeros and ones, we often feel that it is not random, that is, it is not plausible as an outcome of fair coin tossing. Why? The answer is provided by algorithmic information theory: because the sequence is compressible, that is, it has small complexity or, equivalently, can be produced by a short program. This idea, going back to Solomonoff, Kolmogorov, Chaitin, Levin, and others, is now the starting point of algorithmic information theory. The first part of this book is a textbook-style exposition of the basic notions of complexity and randomness; the second part covers some recent work done by participants of the “Kolmogorov seminar” in Moscow (started by Kolmogorov himself in the 1980s) and their colleagues. This book contains numerous exercises (embedded in the text) that will help readers to grasp the material.

Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of "algorithmic randomness" and complexity for scientists from diverse fields.

Briefly, we review the basic elements of computability theory and prob ability theory that are required. Finally, in order to place the subject in the appropriate historical and conceptual context we trace the main roots of Kolmogorov complexity. This way the stage is set for Chapters 2 and 3, where we introduce the notion of optimal effective descriptions of objects. The length of such a description (or the number of bits of information in it) is its Kolmogorov complexity. We treat all aspects of the elementary mathematical theory of Kolmogorov complexity. This body of knowledge may be called algo rithmic complexity theory. The theory of Martin-Lof tests for random ness of finite objects and infinite sequences is inextricably intertwined with the theory of Kolmogorov complexity and is completely treated. We also investigate the statistical properties of finite strings with high Kolmogorov complexity. Both of these topics are eminently useful in the applications part of the book. We also investigate the recursion theoretic properties of Kolmogorov complexity (relations with Godel's incompleteness result), and the Kolmogorov complexity version of infor mation theory, which we may call "algorithmic information theory" or "absolute information theory. " The treatment of algorithmic probability theory in Chapter 4 presup poses Sections 1. 6, 1. 11. 2, and Chapter 3 (at least Sections 3. 1 through 3. 4).

Looking at a sequence of zeros and ones, we often feel that it is not random, that is, it is not plausible as an outcome of fair coin tossing. Why? The answer is provided by algorithmic information theory: because the sequence is compressible, that is, it has small complexity or, equivalently, can be produced by a short program. This idea, going back to Solomonoff, Kolmogorov, Chaitin, Levin, and others, is now the starting point of algorithmic information theory. The first part of this book is a textbook-style exposition of the basic notions of complexity and randomness; the second part cover.

Surveys on recent developments in the theory of algorithmic randomness and its interactions with other areas of mathematics.

The mathematical theory of computation has given rise to two important ap proaches to the informal notion of "complexity": Kolmogorov complexity, usu ally a complexity measure for a single object such as a string, a sequence etc., measures the amount of information necessary to describe the object. Compu tational complexity, usually a complexity measure for a set of objects, measures the compuational resources necessary to recognize or produce elements of the set. The relation between these two complexity measures has been considered for more than two decades, and may interesting and deep observations have been obtained. In March 1990, the Symposium on Theory and Application of Minimal Length Encoding was held at Stanford University as a part of the AAAI 1990 Spring Symposium Series. Some sessions of the symposium were dedicated to Kolmogorov complexity and its relations to the computational complexity the ory, and excellent expository talks were given there. Feeling that, due to the importance of the material, some way should be found to share these talks with researchers in the computer science community, I asked the speakers of those sessions to write survey papers based on their talks in the symposium. In response, five speakers from the sessions contributed the papers which appear in this book.

This work extends the theories of algorithmic randomness and Kolmogorov complexity of bitstrings to the quantum realm. Nies and Scholz defined quantum Martin-Löf randomness (q-MLR): the first notion of algorithmic randomness to be defined for infinite sequences of qubits, which are called states. We define a notion of quantum Solovay randomness and show it to be equivalent to q-MLR using purely linear algebraic methods. Quantum Schnorr randomness is then introduced. A quantum analogue of the law of large numbers is shown to hold for quantum Schnorr random states. We next turn to a quantum analogue of Kolmogorov complexity. We introduce quantum-K (QK), a measure of the descriptive complexity of density matrices using classical prefix-free Turing machines and show that the initial segments of weak Solovay random and quantum Schnorr random states are incompressible in the sense of QK. Many properties enjoyed by prefix-free Kolmogorov complexity (K) have analogous versions for QK; notably a counting condition. Several connections between Solovay randomness and (K), including the Chaitin type characterization of Solovay randomness, carry over to those between weak Solovay randomness and QK. Schnorr randomness has a Levin\textendash Schnorr characterization using KcC; a version of K defined using an arbitrary computable measure machine, C. We similarly define QKc, a version of QK. Quantum Schnorr randomness is shown to have a Levin\textendash Schnorr and a Chaitin type characterization using QKc. We then show how classical randomness can be generated from a computable, non-quantum random state. We formalize how `measurement' of a state induces a probability measure on the space of infinite bitstrings. A state is `measurement random' (mR) if the measure induced by it, under any computable basis, assigns probability one to the set of Martin-Löf randoms. I.e., measuring a mR state produces a Martin-Löf random bitstring with probability one. While quantum-Martin-Löf random states are mR, we show that the converse fails by defining a computable mR state p which is not quantum-Martin-Löf random. In fact, something stronger is true. Measuring p in any computable basis yields an arithmetically random sequence with probability one. The work concludes by studying the asymptotic von Neumann entropy of computable states.

The research presented in Aspects of Kolmogorov Complexity addresses the fundamental standard of defining randomness as measured by a Martin-Lof level of randomness as found in random sequential binary strings. A classical study of statistics that addresses both a fundamental standard of statistics as well as an applied measure for statistical communication theory. The research points to compression levels in a random state that are greater than is found in current literature. A historical overview of the field of Kolmogorov Complexity and Algorithmic Information Theory, a subfield of Information Theory, is given as well as examples using a radix 3, radix 4, and radix 5 base numbers for both random and non-random sequential strings. The text also examines monochromatic and chromatic symbols and both theoretical and applied aspects of data compression as they relate to the transmission and storage of information. The appendix contains papers on the subject given at conferences and the references are current.ContentsTechnical topics addressed in Aspects of Kolmogorov Complexity include:• Statistical Communication Theory• Algorithmic Information Theory• Kolmogorov Complexity• Martin-Lof Randomness• Compression, Transmission and Storage of Information