Neodlučive modalne logike

Modalne logike su proširenja logike sudova različitim modalnim operatorima, od kojih su najpoznatija proširenja modalnim operatorima kojima izričemo mogućnost i nužnost. Ovisno o izboru modalnih operatora i njihovoj interpretaciji, modalna logika obuhvaća još i logiku znanja, deontičku logiku, temporalnu logiku i dr. U ovom radu osim osnovnog modalnog jezika i proširenja sustava K, definirana je sintaksa i semantika propozicionalne dinamičke logike. Glavni rezultat u radu je neodlučivost modalne logike KRA, koja je fragment propozicionalne dinamičke logike DPDL proširen globalnim modalnim operatorom A. To je sadržaj drugog poglavlja. Prvo poglavlje je posvećeno problemu popločavanja. Wangove pločice su kvadratne pločice obojenih rubova koje se mogu složiti jedna do druge samo ako se boje na zajedničkim rubovima podudaraju. Ne postoji algoritam koji za proizvoljan konačan skup tipova Wangovih pločica daje odgovor može li se tim pločicama popločati čitava ravnina, niti ne postoji algoritam za problem popločavanja prvog kvadranta. Dan je dokaz neodlučivosti problema popločavanja ravnine korištenjem dinamičkih sustava afinih funkcija s racionalnim koeficijentima te dokaz neodlučivosti problema popločavanja prvog kvadranta pomoću neodlučivosti problema zaustavljanja Turingovih strojeva. Ova dva naizgled nepovezana poglavlja se povezuju tako da neodlučivost modalne logike KRA slijedi iz neodlučivosti problema popločavnja redukcijom problema popločavanja na problem ispunjivosti za KRA.