FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 | 4 | 5 |   ...   | 12 |

«Fixed-point tile sets and their applications$ Bruno Durand1, Andrei Romashchenko1,2,∗, Alexander Shen1,2,∗ Abstract An aperiodic tile set was ...»

-- [ Page 1 ] --

Fixed-point tile sets and their applications$

Bruno Durand1, Andrei Romashchenko1,2,∗, Alexander Shen1,2,∗


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 fields, ranging from logic

(the Entscheidungsproblem) to physics (quasicrystals).

We present a new construction of an aperiodic tile set that is based on Kleene’s fixed-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 flexible, 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 finite 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 classification 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


[10] and in the ICALP extended abstract [11].

Keywords: tilings, Kleene’s fixed 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 finite 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

in [3]:

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 [3] as the main tool to prove Berger’s theorem: The domino problem (to find out whether or not a given tile set has tilings) is undecidable.

The first tile set of Berger was rather complicated. Later, many other constructions were suggested. Some of them are simplified versions of Berger’s construction ([29]; see also the expositions in [1, 8, 22]). Some others are based on polygonal tilings (including the famous Penrose and Ammann tilings; see [15]). An ingenious construction suggested in [19] is based on multiplication in a kind of positional number system and gives a small aperiodic set of 14 tiles (and in [6] 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 [27].

In this paper, we present yet another construction of an aperiodic tile set. It does not provide

a small tile set; however, we find 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 fixed-point (recursion) theorem, in von Neumann’s self-reproducing automata [26], 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 flexible enough to achieve some additional properties of the tile set. We illustrate this flexibility 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 fixed-point construction of an aperiodic tile set (new proof of Berger’s theorem), and we illustrate the flexibility 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 fixed fraction of tiles).

• The fixed-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 difficulty 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 configuration (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 [7], 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 [17] and Myers [25] as a corollary). The construction in [7] 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 [32] and Hochman [18] about effectively closed subshifts: Every one-dimensional effectively closed subshift can be obtained as a projection of some two-dimensional subshift of finite type (in an extended alphabet). Our construction provides a solution of Problem 9.1 from [18]. (Another solution, based on the classical Robinson-type construction, was independently suggested by Aubrun and Sablik; see [2].)

• To prove the robustness of tile sets against sparse errors we use a hierarchical classification 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 defia 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 definition of an island by allowing two (but not three!) islands of the same rank to be close to each other. This more complicated definition 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 fixed-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 difficult 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: fixed-point construction with variable zoom factors, splitting of a random set into doubled islands (we shall call them bi-islands), and “robustification” with filling 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 conflicts 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 define 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

properties hold:

• 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 first and second conditions are true, but the third one is false: The placement of cutting lines is not unique.

–  –  –

Pages:   || 2 | 3 | 4 | 5 |   ...   | 12 |

Similar works:

«The World Changers’ Library God’s Troubadour – Francis and the birth of a movement The Middle Ages is regarded as and age of faith. It was also a period of mounting crisis. Into this world came Francis of Assisi—rich playboy, soldier of fortune and one of the greatest movement founders of all time. by Steve Addison www.steveaddison.net The World Changers’ Library I n 529 Benedict founded Monte Cassino, the first monastery to live under his Rule. For centuries, monasticism, guided by...»

«A Wagner Matinee Willa Cather Author : Short Stories Category : andrewtan94 December 2009 Submit by : Read this on Full Online Books Link : www.fullonlinebooks.com Source : I received one morning a letter, written in pale ink on glassy, blue-lined notepaper, and bearing the postmark of a little Nebraska village. This communication, worn and rubbed, looking as though it had been carried for some days in a coat pocket that was none too clean, was from my Uncle Howard and informed me that his wife...»

«c 2004 RAS(DoM) and LMS Izvestiya: Mathematics 68:3 607–618 Izvestiya RAN : Ser. Mat. 68:3 181–194 DOI 10.1070/IM2004v068n03ABEH000490 Rationality of an Enriques–Fano threefold of genus five I. A. Cheltsov Abstract. We prove the rationality of a non-Gorenstein Fano threefold of Fano index one and degree eight having terminal cyclic quotient singularities and Picard group Z. This threefold can be described as the quotient of a double covering of P3 ramified in a smooth quartic surface by...»

«Department of Environmental Conservation Response to Comments For Spring Creek Correctional Center Wastewater Treatment Facility APDES Permit No. AK0053724 Public Noticed June 24, 2016 – July 25, 2016 PROPOSED FINAL, 2016 Spring Creek Correctional Center Wastewater Treatment Facility AK0053274 Alaska Department of Environmental Conservation Wastewater Discharge Authorization Program 555 Cordova Street Anchorage, AK 99501 1 Introduction 1.1 Summary of Facility / Permit The City of Seward (City...»

«General and specific report National Chengchi University Meike Mulder S2331896 Exchange to Taipei, Taiwan Exchange fall semester 2015 Written on: 01/02/2015 Marco polo fund General report Host institution and exact dates of semester abroad The name of the host institution is National Chengchi University and is situated in Taipei, the capital of Taiwan. I left the Netherlands on the 5th of September and returned on the 22th of January. Contact with home faculty, preparation and journey For...»

«2016 Seed Catalog Farmer Direct Seeds from Virginia “Know Your Seed Grower” Bushel Basket Thai Bottle Tarahaumara Dipper has excellent Downy Mildew resistance! More DMR varieties and trial results inside. Seminole-Waltham Evaluation Barnes Mountain Orange Stocky Red Roaster West Indian Gherkin Grits Tasting TN Red (top), African Drum Gourd Floriani Flint, Bloody Butcher DMR 264 (above) and Marketmore Waltham foreground; 76 (below) in Twin Oaks Downy Seminole x Trial. 8/28/2014 Mildew...»

«1 Changing the Status Quo: Industry Leaders’ Perceptions of Gender in Family Films Executive Summary * Stacy L. Smith, PhD & Amy Granados, Marc Choueiti, Sarah Erickson, Allison Noyes University of Southern California Annenberg School for Communication & Journalism 3502 Watt Way, Suite 222 Los Angeles, CA 90089 stacysmi@usc.edu One of our recent studies showed that females were grossly underrepresented across 122 G, PG, and PG-13 films theatrically released between 2006 and 2009.1 That is,...»

«Archeo-rapport 47 Het archeologische bureauonderzoek van het begijnhof te Lier Kessel-Lo, 2010 Studiebureau Archeologie bvba Archeo-rapport 47 Het archeologische bureauonderzoek van het begijnhof te Lier Kessel-Lo, 2010 Studiebureau Archeologie bvba Colofon Archeo-rapport 47 Het archeologisch bureauonderzoek van het begijnhof te Lier Opdrachtgever: Stad Lier Projectleiding: Maarten Smeets Uitvoering veldwerk: Maarten Smeets Patrick Moreau Auteur: Maarten Smeets Patrick Moreau Foto’s en...»

«Electrician’s Tricks of the Trade Use wirenut to correct threads: To correct messed up threads on all-thread, take a red wirenut on 1/4-20 thread, screw it on tight then unscrew. The threads will now be like new. Use a blue wirenut on 3/8-16 thread. Amps. By Multiplication: Dividing shortcut, Hey if your like me, when you’re trying to figure out how many amps. a piece of Equipment draws, long division is a hassle and I usually get it wrong, but multiplying is a lot easier. Well with this...»

«National Terrazzo & Mosaic Association 2015 Honor Awards San Joaquin Community Hospital MOB (Imaging & Cancer Center) Bakersfield, CA The design of this 6,700-square-foot terrazzo installation in nine colors responds well to the architecture of the space, providing a skilled response to the different scales of the entries and the smaller spaces. The soothing harmony of the color palette welcomes visitors with a calming environment. Two adjacent entry lobbies are united by intricate design...»

«SEMANA DE LA MIEL 8 AL 14 DE AGOSTO “SUMALE MIEL A TU VIDA” CRONOGRAMA NACIONAL DE ACTIVIDADES 4 de Agosto: Televisión Pública – 14hs Lanzamiento de la semana de la miel en el programa Cocineros Argentinos CABA – (Ciudad Autónoma de Buenos Aires) Organiza: Ministerio de Agroindustria de la Nación apicultura@magyp.gob.ar 8 de Agosto de 10 a 18hs Tráiler institucional del Ministerio de Agroindustria de la Nación Plaza Congreso Actividades: Degustaciones de mieles de las distintas...»

«QC 945.2.E456.H8 1962 c.2 U S, Weather Bureau,. Hurricane E l l a, October Lll-22, 1962; preliniiriary report; w i t h advisories and b u l l e t i n s is sued. U. S. DEPARTMENT OF COMMERCE OCTOBER I 4 2 2 1962 9 Preliminary Report with Advisories and Bulletins fssued. 121 654 National Oceanic and Atmospheric Administration Weather Bureau Hurricane Series ERRATA NOTICE One or more conditions of the original document may affect the quality of the image, such as: Discolored pages Faded or...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.