Väitös (matematiikka): FM Toni Hotanen
Aika
16.8.2024 klo 12.00 - 16.00
FM Toni Hotanen esittää väitöskirjansa ”On the Topological Entropy and Lyapunov Exponents of Cellular Automata” julkisesti tarkastettavaksi Turun yliopistossa perjantaina 16.08.2024 klo 12.00 (Turun yliopisto, Quantum, Quantumin auditorio, Vesilinnantie 5, Turku).
Yleisön on mahdollista osallistua väitökseen myös etäyhteyden kautta: https://echo360.org.uk/section/76c76eb1-029d-4e00-b283-f0c8f9835d1e/public (kopioi linkki selaimeen).
Vastaväittäjänä toimii tohtori Julien Cassaigne (Centre National Recherche Scientifique, CNRS, Ranska) ja kustoksena professori Jarkko Kari (Turun yliopisto). Tilaisuus on englanninkielinen. Väitöksen alana on matematiikka.
Väitöskirja yliopiston julkaisuarkistossa: https://urn.fi/URN:NBN:fi-fe2024080563697
***
Tiivistelmä väitöstutkimuksesta:
Soluautomaatit ja Turingin koneet ovat laskennan malleja ja näin ollen niitä voidaan ajatella tietokoneiden, ohjelmointikielten tai algoritmien formaaleina matemaattisina malleina. Molempia on myös pitkään tutkittu dynaamisina systeemeinä, jolloin ollaan voitu perehtyä niiden dynaamisiin ominaisuuksiin. Tällaisia ominaisuuksia on esimerkiksi systeemien sensitiivisyys, joka tarkoittaa, että mielivaltaisen pienet eroavuudet voivat aiheuttaa suuria eroja riittävän ajan kuluttua. Tämän voi ajatella myös perhosvaikutuksena.
Päätösongelma on sen muotoinen kysymys, johon vastaus jokaisella syötteellä on aina kyllä tai ei. Esimerkkeinä päätösongelmista ovat seuraavat kysymykset: ”Onko annettu luonnollinen luku alkuluku?” ja ”Onko annettu reitti kahden kaupungin välillä lyhin mahdollinen reitti?”. Päätösongelma on ratkeava, jos on olemassa algoritmi, joka antaa oikean vastauksen ongelmaan sen jokaisella syötteellä ja muussa tapauksessa se on ratkeamaton.
Tässä väitöstutkimuksessa on perehdytty kahteen dynaamisten systeemien kompleksisuutta mittaavan käsitteeseen, jotka ovat entropia ja Lyapunovin eksponentit. Systeemiä, jolle kyseiset arvot ovat nollia, voidaan pitää yksinkertaisena ja vastaavasti monimutkaisena, jos ne ovat nollaa suurempia. Näin ollen on kiinnostava tietää, onko olemassa algoritmia, joka voi aina kertoa ovatko nämä arvot nollia vai eivät. Väitöstutkimuksessa on näytetty monen näitä arvoja koskevan päätösongelman olevan ratkeamattomia, kun ollaan rajoituttu kääntyvien soluautomaattien ja Turingin koneiden joukkoon.
Lyapunovin eksponenttien ja entropian yhteyksiä systeemien dynaamisiin ominaisuuksiin on myös paljon tutkittu entuudestaan. Uutena asiana tässä väitöstutkimuksessa konstruoitiin sensitiivinen soluautomaatti, jonka Lyapunovin eksponentit ovat nollat. Tämä antoi kielteisen vastauksen erääseen avoimeen ongelmaan.
Enimmäkseen väitöskirjassa ollaan tutkittu yksiulotteisia soluautomaatteja. Sen sijaan tutkimuksen lopussa ollaan perehdytty entropian ja Lyapunovin eksponenttien yleistyksiin monimutkaisemmille soluautomaateille ja tutkittu näiden ominaisuuksia.
Yleisön on mahdollista osallistua väitökseen myös etäyhteyden kautta: https://echo360.org.uk/section/76c76eb1-029d-4e00-b283-f0c8f9835d1e/public (kopioi linkki selaimeen).
Vastaväittäjänä toimii tohtori Julien Cassaigne (Centre National Recherche Scientifique, CNRS, Ranska) ja kustoksena professori Jarkko Kari (Turun yliopisto). Tilaisuus on englanninkielinen. Väitöksen alana on matematiikka.
Väitöskirja yliopiston julkaisuarkistossa: https://urn.fi/URN:NBN:fi-fe2024080563697
***
Tiivistelmä väitöstutkimuksesta:
Soluautomaatit ja Turingin koneet ovat laskennan malleja ja näin ollen niitä voidaan ajatella tietokoneiden, ohjelmointikielten tai algoritmien formaaleina matemaattisina malleina. Molempia on myös pitkään tutkittu dynaamisina systeemeinä, jolloin ollaan voitu perehtyä niiden dynaamisiin ominaisuuksiin. Tällaisia ominaisuuksia on esimerkiksi systeemien sensitiivisyys, joka tarkoittaa, että mielivaltaisen pienet eroavuudet voivat aiheuttaa suuria eroja riittävän ajan kuluttua. Tämän voi ajatella myös perhosvaikutuksena.
Päätösongelma on sen muotoinen kysymys, johon vastaus jokaisella syötteellä on aina kyllä tai ei. Esimerkkeinä päätösongelmista ovat seuraavat kysymykset: ”Onko annettu luonnollinen luku alkuluku?” ja ”Onko annettu reitti kahden kaupungin välillä lyhin mahdollinen reitti?”. Päätösongelma on ratkeava, jos on olemassa algoritmi, joka antaa oikean vastauksen ongelmaan sen jokaisella syötteellä ja muussa tapauksessa se on ratkeamaton.
Tässä väitöstutkimuksessa on perehdytty kahteen dynaamisten systeemien kompleksisuutta mittaavan käsitteeseen, jotka ovat entropia ja Lyapunovin eksponentit. Systeemiä, jolle kyseiset arvot ovat nollia, voidaan pitää yksinkertaisena ja vastaavasti monimutkaisena, jos ne ovat nollaa suurempia. Näin ollen on kiinnostava tietää, onko olemassa algoritmia, joka voi aina kertoa ovatko nämä arvot nollia vai eivät. Väitöstutkimuksessa on näytetty monen näitä arvoja koskevan päätösongelman olevan ratkeamattomia, kun ollaan rajoituttu kääntyvien soluautomaattien ja Turingin koneiden joukkoon.
Lyapunovin eksponenttien ja entropian yhteyksiä systeemien dynaamisiin ominaisuuksiin on myös paljon tutkittu entuudestaan. Uutena asiana tässä väitöstutkimuksessa konstruoitiin sensitiivinen soluautomaatti, jonka Lyapunovin eksponentit ovat nollat. Tämä antoi kielteisen vastauksen erääseen avoimeen ongelmaan.
Enimmäkseen väitöskirjassa ollaan tutkittu yksiulotteisia soluautomaatteja. Sen sijaan tutkimuksen lopussa ollaan perehdytty entropian ja Lyapunovin eksponenttien yleistyksiin monimutkaisemmille soluautomaateille ja tutkittu näiden ominaisuuksia.
Viestintä