Entropy and Kolmogorov complexity

This thesis is dedicated to studying the theory of entropy and its relation to the Kolmogorov complexity. Originating in physics, the notion of entropy was introduced to mathematics by C. E. Shannon as a way of measuring the rate at which information is coming from a data source. There are, however, a few different ways of telling how much information there is: an alternative approach to quantifying the amount of information is the Kolmogorov complexity, which was proposed by A. N. Kolmogorov. The Shannon entropy is the key ingredient in the definition of the Kolmogorov-Sinai entropy of a measure-preserving systems. Roughly speaking, the Kolmogorov-Sinai entropy is the expected amount of information in `Shannon sense' that one obtains per unit of time by observing the evolution of a measure-preserving system. In topological dynamics, the topological entropy takes place of the Kolmogorov-Sinai entropy. For metrizable systems, the topological entropy measures the exponential growth rate of the number of distinguishable partial orbits of length n as n tends to infinity. Originally defined for Z-actions, the 'classical' theories of entropy were later extended to actions of amenable groups.We provide a necessary background on amenable groups, topological/measurepreserving dynamics and the entropy theory in Chapters 1, 2, 3 and 5.The main focus of this thesis is extending the following results. First of all, a common generalization of the topological and the Kolmogorov-Sinai entropy theories for Z-systems was suggested by G. Palm. We provide an abstract generalization of the work of Palm for actions of discrete amenable groups in the language of measurement functors in Chapter 6.Secondly, we investigate the connection of entropy and Kolmogorov complexity.Originally, the equality between the topological entropy and a certain quantity measuring maximal asymptotic Kolmogorov complexity of the trajectories was established by A. A. Brudno for subshifts over Z. Later, he proved the equality of the Kolmogorov-Sinai entropy and the asymptotic Kolmogorov complexity of almost every trajectory for ergodic subshifts over Z. We provide a generalization of these results as follows. Firstly, in Chapter 4 we give a background on computability and Kolmogorov complexity and, further, introduce computable Fölner monotilings, which are central in our extensions of Brudno's results. We treat the 'first' and the 'second' theorems of Brudno in Chapter 7.The first theorem is generalized for subshifts over computable groups admitting computable Fölner monotilings, while the second theorem is proved under the assertion of regularity of the monotiling, which we introduce in Chapter 7 as well