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 >>>

We study different notions of descriptive complexity of computable sequences. Our main result states that if for almost all n the Kolmogorov complexity of the n-prefix of an infinite binary sequence x conditional to n is less than m then there is a program of length m^2+O(1) that for almost ... more >>>