Matriisien vapausongelmasta
Peltola, Antti (2018-01-29)
Matriisien vapausongelmasta
Peltola, Antti
(29.01.2018)
Tätä artikkelia/julkaisua ei ole tallennettu UTUPubiin. Julkaisun tiedoissa voi kuitenkin olla linkki toisaalle tallennettuun artikkeliin / julkaisuun.
Turun yliopisto
Tiivistelmä
Matriisien vapausongelmassa tutkitaan, onko annetun matriisijoukon generoiman puoliryhmän alkiolla yksikäsitteinen tekijöihinjako. Tässä tutkielmassa esitetään todistus ongelman ratkeamattomuudelle 3_3-matriiseilla ja erilaisia tuloksia 2_2-matriisien tapauksessa.
3_3-matriisien vapausongelma osoitetaan ratkeamattomaksi osoittamalla ensin Postin vastaavuusongelman muunnelma MMPCP ratkeamattomaksi ja redusoimalla se 3_3-matriisien vapausongelmaan.
2_2-matriiseille osoitetaan ensin, ettei niiden tapauksessa voida hyödyntää Postin vastaavuusongelmaa 3_3-matriisien tapaan. Tarkastellaan sitten 2_2- rationaalilukumatriisien vapausongelmaa, kun tarkasteltavan joukon kardinaliteetti rajoitetaan ensin yhteen ja sitten kahteen alkioon. Yhden alkion tapaus saadaan ratkeavaksi rationaalilukumatriiseilla ja kahden alkion tapaus jää avoimeksi, vaikka rajoitutaan yläkolmiomatriiseihin. Lopuksi tutkitaan tiettyä muotoa olevien matriisitulojen yksikäsitteisyyttä rajoitettujen kielten avulla.
3_3-matriisien vapausongelma osoitetaan ratkeamattomaksi osoittamalla ensin Postin vastaavuusongelman muunnelma MMPCP ratkeamattomaksi ja redusoimalla se 3_3-matriisien vapausongelmaan.
2_2-matriiseille osoitetaan ensin, ettei niiden tapauksessa voida hyödyntää Postin vastaavuusongelmaa 3_3-matriisien tapaan. Tarkastellaan sitten 2_2- rationaalilukumatriisien vapausongelmaa, kun tarkasteltavan joukon kardinaliteetti rajoitetaan ensin yhteen ja sitten kahteen alkioon. Yhden alkion tapaus saadaan ratkeavaksi rationaalilukumatriiseilla ja kahden alkion tapaus jää avoimeksi, vaikka rajoitutaan yläkolmiomatriiseihin. Lopuksi tutkitaan tiettyä muotoa olevien matriisitulojen yksikäsitteisyyttä rajoitettujen kielten avulla.