On the topological entropy and lyapunov exponents of cellular automata : decision problems, dynamical properties and generalizations

Abstract

A dynamical system is a pair made out of a space of points and a function that determines how the points move in the space. Usually some extra properties are required from the space and the function to make them susceptible for studying. Topological dynamical systems require the space to be a compact metric space, meaning we can measure distances between the points and all sequences of points contain subsequences that converge to a single point. A function is required to be continuous meaning close enough points remain close to each other after one iteration of the function.

Cellular automata are examples of such systems. The space, called the configuration space, is made out of a regular lattice of symbols. Usually the lattice gets its structure from a group and the set of symbols is finite. The elements of the group are called cells and the symbols are called states. The continuous function, called the global rule, is made out of a neighbourhood vector and a local rule. The global rule applies the local rule for each cell independently and simultaneously and its value depends on the value of the cells in the neighbourhood of each cell.

Topological entropy is a measure of complexity of a given topological dynamical system. Simple systems tend to often have low or even zero entropy and by contrast complex systems often have high entropy. Two systems are called conjugate if they are equivalent in some sense. For example they have the same orbits and they share many dynamical properties. Conjugate systems have the same topological entropy, which makes it an useful value if we want to show that two given systems are not conjugate. The topological entropy has its measure-theoretic counterpart which we will also study. The entropies are related to each other by a variational principle.

Another measure of complexity are Lyapunov exponents. They can be thought of as the speed of the propagation of differences in a given system. The connections between Lyapunov exponents and various dynamical properties have been widely studied. In this dissertation we give an answer to the conjecture which states that a sensitive cellular automaton must have a configuration with a non-zero Lyapunov exponent. We construct a cellular automaton, which has no such configurations. The Lyapunov exponents are also related to measure-theoretic entropy. One can for instance calculate an upper bound for the measure-theoretic entropy of a given cellular automaton by first calculating the Lyapunov exponents. The Lyapunov exponents are only defined for one-dimensional cellular automata. In this dissertation we generalize the Lyapunov exponents for cellular automata over finitely generated groups and the measure-theoretic entropy for cellular automata over amenable groups and show that an analogous connection exists between them in the more general case.

A decision problem is a question with two possible answers: Yes or no. For example: ”Is a given natural number a prime number?” and ”Is a given route between two cities the shortest possible route?” are examples of decision problems. A decision problem is called decidable if there exists an algorithm (one can think of it as a computer program) that always gives the right answer to the problem for every possible input. The problem is called undecidable if no such algorithm exists. In this dissertation we study several decision problems related to reversible Turing machines, reversible cellular automata and group cellular automata. Namely these problems ask for example: ”Is the topological entropy of a given system zero?” and ”Are the Lyapunov exponents of a given system zero?”. Some related decision problems are also considered.

---- Dynaaminen systeemi on pari, joka muodostuu pisteistä koostuvasta avaruudesta sekä funktiosta, joka määrittelee miten kyseiset pisteet liikkuvat avaruudessa. Usein sekä avaruudelta että funktiolta vaaditaan joitakin ominaisuuksia, jotta niitä pystytään tutkimaan paremmin. Topologisten dynaamisten systeemien tapauksessa avaruuden täytyy olla kompakti metrinen avaruus, joka tarkoittaa sitä, että pystymme mittaamaan pisteiden välistä etäisyyttä ja jokaisesta pisteiden jonosta löytyy alijono, joka suppenee yksittäistä pistettä kohti. Funktion vaaditaan olevan jatkuva, joka tarkoittaa sitä, että tarpeeksi lähellä olevat pisteet kuvautuvat lähelle toisiaan kun funktiota toistetaan kerran.

Soluautomaatit ovat esimerkkejä tällaisista systeemeistä. Avaruus, jota kutsutaan konfiguraatioavaruudeksi, muodostuu säännöllisestä symbolien hilasta. Hila saa yleensä rakenteensa ryhmältä ja symboleja on äärellinen määrä. Ryhmän alkioita kutsutaan soluiksi ja symboleja kutsutaan tiloiksi. Jatkuva funktio, jota kutsutaan globaaliksi säännöksi, muodostuu naapurustovektorista ja lokaalista säännöstä. Glo-baali sääntö käyttää lokaalia sääntöä joka solulle itsenäisesti ja samanaikaisesti ja sen arvo määräytyy jokaiselle solulle niiden naapurustojen solujen arvosta.

Topologinen entropia on kompleksisuuden mitta topologisille dynaamisille systeemeille. Yksinkertaisilla systeemeillä on usein matala tai jopa nolla entropia, kun taas monimutkaisilla systeemeillä on usein korkea entropia. Kaksi systeemiä ovat konjugaatteja, jos ne ovat tietyssä mielessä ekvivalentteja. Esimerkiksi niillä on samat kiertoradat ja niillä on monta samaa dynaamista ominaisuutta. Konjugaateilla systeemeillä on sama topologinen entropia ja siitä syystä kyseinen arvo on hyödyllinen jos halutaan näyttää, että kaksi annettua systeemiä eivät ole konjugaatteja. Topologisella entropialla on mittateoreettinen vastine, jota me myös tutkimme. Entropiat ovat yhteydessä toisiinsa variaatioperiaatteen nojalla.

Muita kompleksisuuden mittoja ovat Lyapunovin eksponentit. Niitä voi ajatella muutosten leviämisen nopeuksina annetussa systeemissä. Lyapunovin eksponenttien yhteyksiä erilaisiin dynaamisiin ominaisuuksiin on tutkittu laajasti. Tässä väitöskirjassa vastaamme konjektuuriin, joka väittää, että herkillä soluautomaateilla on aina olemassa jokin konfiguraatio, jonka Lyapunovin eksponentit eivät ole nollia. Me konstruoimme soluautomaatin, jolla tällaisia konfiguraatioita ei ole olemassa. Lyapunovin eksponentit liittyvät mittateoreettiseen entropiaan. Mittateoreettiselle entropialle voidaan esimerkiksi laskea yläraja laskemalla ensin Lyapunovin eksponentit. Lyapunovin eksponentit ovat määritelty vain yksiulotteisille soluautomaateille. Tässä väitöskirjassa yleistämme Lyapunovin eksponentit soluautomaateille yli äärellisesti generoitujen ryhmien ja mittateoreettisen entropian "myöntyvien" ryhmien yli. Tämän lisäksi näytämme, että niiden välillä on vastaavanlainen yhteys yleisem-mässäkin tapauksessa.

Päätösongelma on kysymys, jolle on kaksi mahdollista vastausta: Kyllä tai ei. Esimerkiksi: "Onko annettu luonnollinen luku alkuluku?" ja "Onko annettu reitti kahden kaupungin välillä lyhyin mahdollinen reitti?" ovat esimerkkejä päätösongel-mista. Päätösongelma on ratkeava, jos on olemassa algoritmi (joka voidaan ajatella tietokoneohjelmana), joka antaa aina oikean vastauksen ongelmaan sen jokaisella syötteellä. Ongelma on ratkeamaton, jos sellaista algoritmia ei ole olemassa. Väi-töskirjassa tutkimme joitakin päätösongelmia, jotka liittyvät kääntyviin Turingin ko-neisiin, kääntyviin soluautomatteihin ja ryhmäsoluautomaatteihin. Tarkemmin sanottuna ongelmiin kuuluvat esimerkiksi: "Onko annetun systeemin topologinen entropia nolla?" ja "Onko annetun systeemin Lyapunovin eksponentit nollat?". Myös joitakin näihin liittyviä ongelmia tarkastellaan.