Structural and Computational Existence Results for Multidimensional Subshifts - Törmä, Ilkka (Turku Centre for Computer Science, 2015)
Symbolic dynamics is a branch of mathematics that studies the structure of inﬁnite sequences of symbols, or in the multidimensional case, inﬁnite grids of symbols. Classes of such sequences and grids deﬁned by collections of forbidden patterns are called subshifts, and subshifts of ﬁnite type are deﬁned by ﬁnitely many forbidden patterns. The simplest examples of multidimensional subshifts are sets of Wang tilings, inﬁnite arrangements of square tiles with colored edges, where adjacent edges must have the same color. Multidimensional symbolic dynamics has strong connections to computability theory, since most of the basic properties of subshifts cannot be recognized by computer programs, but are instead characterized by some higher-level notion of computability. This dissertation focuses on the structure of multidimensional subshifts, and the ways in which it relates to their computational properties. In the ﬁrst part, we study the subpattern posets and Cantor-Bendixson ranks of countable subshifts of ﬁnite type, which can be seen as measures of their structural complexity. We show, by explicitly constructing subshifts with the desired properties, that both notions are essentially restricted only by computability conditions. In the second part of the dissertation, we study diﬀerent methods of deﬁning (classes of ) multidimensional subshifts, and how they relate to each other and existing methods. We present deﬁnitions that use monadic second-order logic, a more restricted kind of logical quantiﬁcation called quantiﬁer extension, and multi-headed ﬁnite state machines. Two of the deﬁnitions give rise to hierarchies of subshift classes, which are a priori inﬁnite, but which we show to collapse into ﬁnitely many levels. The quantiﬁer extension provides insight to the somewhat mysterious class of multidimensional soﬁc subshifts, since we prove a characterization for the class of subshifts that can extend a soﬁc subshift into a nonsoﬁc one.

Symbolidynamiikka on matematiikan ala, joka tutkii äärettömän pituisten symbolijonojen ominaisuuksia, tai moniulotteisessa tapauksessa äärettömän laajoja symbolihiloja. Siirtoavaruudet ovat tällaisten jonojen tai hilojen kokoelmia, jotka on määritelty kieltämällä jokin joukko äärellisen kokoisia kuvioita, ja äärellisen tyypin siirtoavaruudet saadaan kieltämällä vain äärellisen monta kuviota. Wangin tiilitykset ovat yksinkertaisin esimerkki moniulotteisista siirtoavaruuksista. Ne ovat värillisistä neliöistä muodostettuja tiilityksiä, joissa kaikkien vierekkäisten sivujen on oltava samanvärisiä. Moniulotteinen symbolidynamiikka on vahvasti yhteydessä laskettavuuden teoriaan, sillä monia siirtoavaruuksien perusominaisuuksia ei ole mahdollista tunnistaa tietokoneohjelmilla, vaan korkeamman tason laskennallisilla malleilla. Väitöskirjassani tutkin moniulotteisten siirtoavaruuksien rakennetta ja sen suhdetta niiden laskennallisiin ominaisuuksiin. Ensimmäisessä osassa keskityn tiettyihin äärellisen tyypin siirtoavaruuksien rakenteellisiin ominaisuuksiin: äärellisten kuvioiden muodostamaan järjestykseen ja Cantor-Bendixsonin astelukuun. Halutunlaisia siirtoavaruuksia rakentamalla osoitan, että molemmat ominaisuudet ovat olennaisesti laskennallisten ehtojen rajoittamia. Väitöskirjan toisessa osassa tutkin erilaisia tapoja määritellä moniulotteisia siirtoavaruuksia, sekä sitä, miten nämä tavat vertautuvat toisiinsa ja tunnettuihin siirtoavaruuksien luokkiin. Käsittelen määritelmiä, jotka perustuvat toisen kertaluvun logiikkaan, kvanttorilaajennukseksi kutsuttuun rajoitettuun loogiseen kvantiﬁointiin, sekä monipäisiin äärellisiin automaatteihin. Näistä kolmesta määritelmästä kahteen liittyy erilliset siirtoavaruuksien hierarkiat, joiden todistan romahtavan äärellisen korkuisiksi. Kvanttorilaajennuksen tutkimus valottaa myös niin kutsuttujen soﬁsten siirtoavaruuksien rakennetta, jota ei vielä tunneta hyvin: kyseisessä luvussa selvitän tarkasti, mitkä siirtoavaruudet voivat laajentaa soﬁsen avaruuden ei-soﬁseksi.