Matematiikan väittelijä valotti ratkeamattomuuden suota (Väitös: FM Ilkka Törmä 31.7.2015, diskreetti matematiikka)
Tiilitysten eli eri muotoisista kuvioista koottujen äärettömien muodostelmien rakennetta rajoittavat vain laskennalliset ehdot. Tämän havaitsi filosofian maisteri Ilkka Törmä Turun yliopistoon tekemässään väitöstutkimuksessa. Diskreetin matematiikan alaan lukeutuva väitös täydentää jo pidempään tutkitun ”ratkeamattomuuden suon” tutkimussuuntausta yhdistämällä siihen logiikan ja atomaattiteorian aloja.
Turun yliopiston tiedote 24.7.2015
Törmä tutkii matematiikan väitöskirjassaan "Structural and Computational Existence Results for Multidimensional Subshifts" ("Rakenteellisia ja laskennallisia olemassaolotodistuksia moniulotteisille siirtoavaruuksille") tiilitysten matemaattista teoriaa ja sen suhdetta laskettavuuteen.
– Tiilitysten teoria on diskreetin matematiikan ala, joka tutkii eri muotoisista kuvioista koottujen äärettömien muodostelmien rakennetta. Kaikille tuttu esimerkki ovat palapelit, sillä erotuksella että käytössä on äärettömän paljon palasia. Tämä teoria on yleisempi versio yksiulotteisesta symbolidynamiikasta, joka käsittelee äärettömän pituisia symbolijonoja. Symbolidynamiikalla on sovelluksia tiedonsiirtoon, ja sen matemaattista teoriaa on kehitetty pitkälle, Törmä selventää.
Törmä tutkii erilaisten tiilitysten luokkien rakennetta ja suhdetta toisiinsa yhdistäen tutkimuksessaan diskreetin matematiikan eri osa-alueita.
– Nämä luokat ovat tunnettujen symbolidynaamisten luokkien yleistyksiä, ja tutkimuksen tavoitteena oli selvittää, mitkä niiden ominaisuuksista säilyvät moniulotteisissa tiilityksissä. Väitöskirjan tulokset osoittavat, että tiilitysten rakennetta rajoittavat vain laskennalliset ehdot. Toisin sanoen luokat ovat erittäin monimutkaisia ja yleensä sisältävät täsmälleen samat tiilitykset, vaikka vastaavat symbolijonojen luokat ovat hyvin yksinkertaisia, Törmä sanoo.
Erityisen huomion tutkimuksessa saavat numeroituvat tiilitykset, joiden sisäistä
rakennetta Törmä selvittää.
– Vaikka numeroituvien tiilitysten rakenne on periaatteessa säännöllisempi kuin yleisten, niiden analysointi osoittautuu yhtä vaikeaksi, Törmä sanoo.
Törmä käsittelee myös luokkia, joiden määritelmät liittyvät matemaattiseen logiikkaan ja automaattiteoriaan, ja todistaa niille tarkat luonnehdinnat laskettavuuden teorian avulla. Näiden luokkien kokonaisrakennetta ei ole aiemmin selvitetty.
– Kun tiilitysten teoriaa lähdettiin kehittämään 1960-luvulla, huomattiin nopeasti, että äärettömien tiilitysten ominaisuuksia on hyvin vaikea päätellä yksittäisten tiilien muodoista. Ei esimerkiksi ole olemassa tietokoneohjelmaa, joka voisi analysoida mitä tahansa tiilijoukkoa ja ratkaista, voiko siitä koota äärettömän tiilityksen. Tätä ilmiötä on kutsuttu "ratkeamattomuuden suoksi", sillä tiilitysten teoria näytti liian monimutkaiselta tutkittavaksi matematiikan keinoin, Törmä sanoo.
Viime vuosikymmenen aikana on havaittu, että ratkeamattomuus on seurausta vahvoista kytköksistä laskettavuuden teoriaan. Törmän väitöskirjan tulokset ovat jatkoa tälle tutkimussuuntaukselle, ja yhdistävät siihen logiikan ja automaattiteorian aloja.
---
Perjantaina 31. heinäkuuta 2015 kello 12 esitetään Turun yliopistossa (Calonia, Cal1-luentosali, Caloniankuja 3, Turku) julkisesti tarkastettavaksi filosofian maisteri Ilkka Törmän väitöskirja Structural and Computational Existence Results for Multidimensional Subshifts (Rakenteellisia ja laskennallisia olemassaolotodistuksia moniulotteisille siirtoavaruuksille). Virallisena vastaväittäjänä toimii tutkimusjohtaja Alexander Shen Montpellierin yliopistosta Ranskasta ja kustoksena professori Jarkko Kari Turun yliopistosta.
FM Ilkka Törmä on syntynyt vuonna 1989 Järvenpäässä ja kirjoittanut ylioppilaaksi 2008 Juhana Herttuan lukiosta Turusta. Filosofian maisteriksi Törmä valmistui 2012 Turun yliopistosta. Väitös kuuluu diskreetin matematiikan alaan.