Matriisien vapausongelmasta
Tässä tietueessa ei ole tiedostoja, ainoastaan metadata.
Pysyvä osoite
Verkkojulkaisu
DOI
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.