An aperiodic tile set was first constructed by R.Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals) We present a new construction of an aperiodic tile set. The flexibility of this ... more >>>

The information contained in a string $x$ about a string $y$ is defined as the difference between the Kolmogorov complexity of $y$ and the conditional Kolmogorov complexity of $y$ given $x$, i.e., $I(x:y)=\C(y)-\C(y|x)$. From the well-known Kolmogorov--Levin Theorem it follows that $I(x:y)$ is symmetric up to a small additive term ... more >>>

The very first Kolmogorov's paper on algorithmic information theory was entitled `Three approaches to the definition of the quantity of information'. These three approaches were called combinatorial, probabilistic and algorithmic. Trying to establish formal connections between combinatorial and algorithmic approaches, we prove that any linear inequality involving Kolmogorov complexities could ... more >>>