«Fixed-point tile sets and their applications$ Bruno Durand1, Andrei Romashchenko1,2,∗, Alexander Shen1,2,∗ Abstract An aperiodic tile set was ...»
Fixed-point tile sets and their applications$
Bruno Durand1, Andrei Romashchenko1,2,∗, Alexander Shen1,2,∗
An aperiodic tile set was ﬁrst constructed by R. Berger while proving the undecidability of the
domino problem. It turned out that aperiodic tile sets appear in many ﬁelds, ranging from logic
(the Entscheidungsproblem) to physics (quasicrystals).
We present a new construction of an aperiodic tile set that is based on Kleene’s ﬁxed-point
construction instead of geometric arguments. This construction is similar to J. von Neumann’s self-reproducing automata; similar ideas were also used by P. G´ cs in the context of errora correcting computations.
This construction is rather ﬂexible, so it can be used in many ways. We show how it can be used to implement substitution rules, to construct strongly aperiodic tile sets (in which any tiling is far from any periodic tiling), to give a new proof for the undecidability of the domino problem and related results, to characterize effectively closed one-dimensional subshifts in terms of twodimensional subshifts of ﬁnite type (an improvement of a result by M. Hochman), to construct a tile set that has only complex tilings, and to construct a “robust” aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors.
For the latter, we develop a hierarchical classiﬁcation of points in random sets into islands of different ranks. Finally, we combine and modify our tools to prove our main result: There exists a tile set such that all tilings have high Kolmogorov complexity even if (sparse enough) tiling errors are allowed.
Some of these results were included in the DLT extended
 and in the ICALP extended abstract .
Keywords: tilings, Kleene’s ﬁxed point theorem, Kolmogorov complexity $ Supported in part by ANR EMC ANR-09-BLAN-0164-01, NAFIT ANR-08-EMER-008-01, and RFBR 09-01a grants.
∗ Corresponding author 1 Laboratoire d’Informatique Fondamentale de Marseille, CNRS & Univ. Aix–Marseille 2 On leave from the Institute for Information Transmission Problems of RAS, Moscow.
Preprint submitted to Elsevier September 17, 2011 Contents 1 Introduction 3 2 Fixed-point aperiodic tile set 5
2.1 Macro-tiles and simulation............................. 5
2.2 Simulating a tile set........
1. Introduction In this paper, tiles are unit squares with colored sides. Tiles are considered as prototypes: we may place translated copies of the same tile into different cells of a cell paper (rotations are not allowed). Tiles in the neighbor cells should match (i.e., the common sides should each have the same color).
Formally speaking, we consider a ﬁnite set C of colors. A tile is a quadruple of colors (left, right, top, and bottom ones), i.e., an element of C4. A tile set is a subset τ ⊂ C4. A tiling of the plane with tiles from τ (τ-tiling) is a mapping U : Z2 → τ that respects the color-matching condition.
A tiling U is periodic if it has a period, i.e., a nonzero vector T ∈ Z2 such that U(x + T ) = U(x) for all x ∈ Z2. Otherwise, the tiling is aperiodic. The following classical result was proved
Theorem 1. There exists a tile set τ such that τ-tilings exist and all of them are aperiodic.
The construction from the proof of Theorem 1 was used in  as the main tool to prove Berger’s theorem: The domino problem (to ﬁnd out whether or not a given tile set has tilings) is undecidable.
The ﬁrst tile set of Berger was rather complicated. Later, many other constructions were suggested. Some of them are simpliﬁed versions of Berger’s construction (; see also the expositions in [1, 8, 22]). Some others are based on polygonal tilings (including the famous Penrose and Ammann tilings; see ). An ingenious construction suggested in  is based on multiplication in a kind of positional number system and gives a small aperiodic set of 14 tiles (and in  an improved version with 13 tiles is presented). Another nice construction with a short and simple proof (based explicitly on ideas of self-similarity) was recently proposed in .
In this paper, we present yet another construction of an aperiodic tile set. It does not provide
a small tile set; however, we ﬁnd it interesting for the following reasons:
• The existence of an aperiodic tile set becomes a simple application of the classical construction used in Kleene’s ﬁxed-point (recursion) theorem, in von Neumann’s self-reproducing automata , and, more recently, in G´ cs’ reliable cellular automata [12, 13]; we a do not use any geometric tricks. An aperiodic tile set is not only an interesting result but an important tool (e.g., this construction was invented to prove that the domino problem is undecidable); our construction makes this tool easier to use.
• The construction is rather general, so it is ﬂexible enough to achieve some additional properties of the tile set. We illustrate this ﬂexibility by providing new proofs for several known results and proving new results; these new results add robustness (resistance to sparse enough errors) to known results about aperiodic tile sets and tile sets that have only complex tilings.
It is unclear whether this kind of robustness can be achieved for previously known constructions of tile sets. On the other hand, robustness properties appear to be important. For example, mathematical models for processes such as quasicrystal growth or DNA computation should take errors into account. Note that our model (with its independent choice of places where errors are allowed) has no direct physical meaning; it is just a simple mathematical model that can be used as a playground to develop tools for estimating the consequences of tiling errors.
The paper is organized as follows:
• In Section 2, we present the ﬁxed-point construction of an aperiodic tile set (new proof of Berger’s theorem), and we illustrate the ﬂexibility of this construction by several examples.
• In Section 3, we show that any “uniform” substitution rule can be implemented by a tile set (thus providing a new proof for this rather old result).
• In Section 4, we use substitutions to show that there are strongly aperiodic tile sets (which means that any tiling is strongly aperiodic, i.e., any shift changes at least some ﬁxed fraction of tiles).
• The ﬁxed-point construction of Section 2 provides a self-similar tiling: Blocks of size n×n (“macro-tiles”) behave exactly as individual tiles, so on the next level we have n2 × n2 blocks made of n × n macro-tiles that have the same behavior, etc. In Section 5, we make some changes in our construction that allow us to get variable zoom factors (the numbers of tiles in macro-tiles increase as the level increases).
Variable zoom factor tilings can be used for simulating computations (with higher levels performing more computation steps); we use them to give a simple proof of the undecidability of the domino problem. The main technical difﬁculty in the standard proof was to synchronize computations on different levels. In our construction this is not needed. We show also that other undecidability results can be obtained in this way.
• This technique can be used to push the strong aperiodicity to its limits: The distance between every tiling and every periodic conﬁguration (or between every tiling and its nontrivial shift) can be made arbitrarily close to 1, not only separated from 0. This is done in Section 6 using an additional tool: error-correcting codes.
• In , a tile set was constructed such that every tiling has maximal Kolmogorov complexity of fragments (Ω(n) for n × n squares); all tilings for this tile set are noncomputable (thereby implying a classical result of Hanf  and Myers  as a corollary). The construction in  was rather complicated and was based on a classical construction of an aperiodic tile set. In Section 7, we provide another proof of the same result that uses variable zoom factors. It is simpler in some respects and can be generalized to produce robust tile sets with complex tiling, which is our main result (Section 13).
• In Section 8, we use the same technique to give a new proof for some results by Simpson  and Hochman  about effectively closed subshifts: Every one-dimensional effectively closed subshift can be obtained as a projection of some two-dimensional subshift of ﬁnite type (in an extended alphabet). Our construction provides a solution of Problem 9.1 from . (Another solution, based on the classical Robinson-type construction, was independently suggested by Aubrun and Sablik; see .)
• To prove the robustness of tile sets against sparse errors we use a hierarchical classiﬁcation of the elements of random sets into islands of different levels (a method that goes back to G´ cs [13, 14]). This method is described in Section 9.1. In Section 9.2, we give deﬁa nitions and establish some probabilistic results about islands that are used later to prove robustness. We show that a sparse random set on Z2 with probability 1 (for Bernoulli distribution) can be represented as a union of “islands” of different ranks. The higher the rank, the bigger is the size of an island; the islands are well isolated from each other (i.e., in some neighborhood of an island of rank k, there are no other islands of rank ≥ k). Then, in Section 9.3, we illustrate these tools using standard results of percolation theory as a model example. In Section 9.4, we modify the deﬁnition of an island by allowing two (but not three!) islands of the same rank to be close to each other. This more complicated deﬁnition is necessary to obtain the most technically involved result of the paper in Section 13 but can be skipped if the reader is interested in the other results.
• In Section 10, we use a ﬁxed-point construction to get an aperiodic tile set that is robust in the following sense: If a tiling has a “hole” of size n, then this hole can be patched by changing only an O(n)-size zone around it. Moreover, we do not need for this a tiling of the entire plane. An O(n) zone (with bigger constant in O notation) around the hole is enough.
• In Section 11, we explain how to get robust aperiodic tile sets with variable zoom factors.
Again, this material is used in Section 13 only.
• In Section 12, we combine the developed techniques to establish one of our main results:
There exists a tile set such that every tiling of the plane minus a sparse set of random points is far from every periodic tiling.
• Finally, Section 13 contains our most technically difﬁcult result: a robust tile set such that all tilings, even with sparsely placed holes, have linear complexity of fragments. To this end we need to combine all our techniques: ﬁxed-point construction with variable zoom factors, splitting of a random set into doubled islands (we shall call them bi-islands), and “robustiﬁcation” with ﬁlling of holes.
2. Fixed-point aperiodic tile set
2.1. Macro-tiles and simulation Fix a tile set τ and an integer N 1 (zoom factor). A macro-tile is an N × N square tiled by τ-tiles matching each other (i.e., a square block of N 2 tiles with no color conﬂicts inside).
We can consider macro-tiles as “preassembled” blocks of tiles; instead of tiling the plane with individual tiles, we may use macro-tiles. To get a correct τ-tiling in this way, we need only to ensure that neighbor macro-tiles have matching macro-colors, so there are no color mismatches on the borders between macro-tiles. More formally, by macro-color we mean a sequence of N colors on the side of a macro-tile (i.e., the right macro-color is a sequence of the right colors of the tiles on the right edge of a macro-tile, and the same for the left, the top, and the bottom macro-color). Each macro-tile has four macro-colors (one for each side). We always assume that macro-tiles are placed side to side, so the plane is split into N × N squares by vertical and horizontal lines.
In the following we are interested in the situation when τ-tilings can be split uniquely into macro-tiles that behave like tiles from some other tile set ρ. Formally, let us deﬁne the notion of a simulation.
Let τ and ρ be two tile sets, and let N 1 be an integer. By simulation of ρ by τ with zoom factor N we mean a mapping S of ρ-tiles into N × N τ-macro-tiles such that the following
• S is injective (i.e., different tiles are mapped into different macro-tiles).
• Two tiles r1 and r2 match if and only if their images S(r1 ) and S(r2 ) match. This means that the right color of r1 equals the left color of r2 if and only if the right macro-color of S(r1 ) equals the left macro-color of S(r2 ), and the same is true in the vertical direction.
• Every τ-tiling can be split by vertical and horizontal lines into N × N macro-tiles that belong to the range of S, and such a splitting in unique.
The second condition guarantees that every ρ-tiling can be transformed into a τ-tiling by replacing each tile r ∈ ρ by its image, macro-tile S(r). Taking into account other conditions, we conclude that every τ-tiling can be obtained in this way, and the positions of grid lines as well as the corresponding ρ-tiles can be reconstructed uniquely.
Example 1 (negative). Assume that τ consists of one tile with four white sides. Fix some N 1. There exists a single macro-tile of size N × N. Does this mean that τ simulates itself (when its only tile is mapped to the only macro-tile)? No. The ﬁrst and second conditions are true, but the third one is false: The placement of cutting lines is not unique.