Väittelijä tutki tunnetun ratkeamattoman ongelman muunnelmia ja sovelluksia (Väitös: FM Esa Sahla, 4.3.2022, matematiikka)
FM Esa Sahla tutki Turun yliopistoon tekemässään väitöskirjassa tunnettua algoritmisesti ratkeamatonta Postin vastaavuusongelmaa. Tutkimuksessaan Sahla esittää ongelmalle uusia muunnelmia ja soveltaa sitä muiden ongelmien ratkeamattomuuden osoittamiseen.
Postin vastaavuusongelma on päätösongelma, joka on yksinkertaisen kuvauksensa ansiosta usein käytetty työkalu muiden päätösongelmien tarkastelussa. Yksinkertaistettuna Postin vastaavuusongelma kysyy, voidaanko kahdesta annetusta osasanojen listasta muodostaa kaksi samaa sanaa asettamalla listoissa samoilla paikoilla esiintyviä osasanoja peräkkäin.
– Ratkaisua voi alkaa rakentaa kuin yksiulotteista palapeliä, missä palasina ovat osasanoista muodostuvat parit. Osoittautuu, että ei ole olemassa tietokoneohjelmaa, joka kertoisi annetuille listoille, onko ratkaisua olemassa vai ei. Tällaista ongelmaa kutsutaan ratkeamattomaksi, Esa Sahla kertoo.
Alkuperäisen ongelman asetteluun on esitetty erilaisia rajoituksia ja muunnelmia, jotka on edelleen osoitettu joko ratkeaviksi tai ratkeamattomiksi. Erilaisia Postin vastaavuusongelman muunnelmia voidaan hyödyntää, kun halutaan osoittaa toisia päätösongelmia ratkeamattomiksi eri matematiikan osa-alueilla.
Sahlan väitöstutkimuksen eräs päätulos on ratkeamattomuuden osoittaminen muunnelmalle, jossa ratkaisuun vaadittavat sanat ovat kahteen suuntaan äärettömiä.
– Äärelliset ja äärettömät muunnelmat vaativat oman tarkastelunsa, sillä äärellisten ratkaisujen olemassaolo ei takaa äärettömien olemassaoloa, ja päinvastoin, Sahla sanoo.
Väitöskirjassaan Sahla osoittaa Postin vastaavuusongelman avulla eräät sanojen sekoittamiseen sekä funktioiden kiintopisteisiin liittyvät ongelmat ratkeamattomiksi.
***
FM Esa Sahla esittää väitöskirjansa ”On Some Modifications and Applications of the Post Correspondence Problem” julkisesti tarkastettavaksi Turun yliopistossa perjantaina 4.3.2022 klo 12.00 (Turun yliopisto, päärakennus, Säästöpankki-sali, Turku).
> Seuraa väitöstilaisuutta etänä
Vastaväittäjänä toimii tohtori Paul Bell (Liverpool John Moores University, Iso-Britannia) ja kustoksena professori Vesa Halava (Turun yliopisto). Tilaisuus on englanninkielinen. Väitöksen alana on matematiikka.
Turun yliopisto seuraa aktiivisesti koronavirustilannetta ja viranomaisten ohjeita. Yliopisto päivittää ohjeitaan tilanteen mukaan. Ohjeet ja linkit löytyvät osoitteesta: utu.fi/koronavirus
Väittelijän yhteystiedot: estasa@utu.fi
