Maksims Dimitrijevs - jaunais datorzinātņu doktors

Recenzenti: prof. Dr.sc.comp. J.Vīksna (LU), prof. Dr.rer.nat. M.Holcers (Gīsenes Justus-Lībiga Universitāte, Vācija), prof. Dr. M.Vilagra (Nacionālā Universitāte, Paragvaja).

Promocijas darba anotācija

Tjūringa mašīnas var atpazīt sanumurējami daudz valodu. No otras puses, varbūtiskas un kvantu Tjūringa mašīnas, izmantojot reālu skaitļu pārejas, var ar ierobežotu kļūdu atpazīt nesanumurējami daudz valodu. Mūsu motivācija ir izpētīt varbūtiskus modeļus ar ierobežotiem skaitļošanas resursiem, kas definē visas valodas vai nesanumurējami daudz valodu.

Mūsu mērķis ir izpētīt dažādus ierobežotas kļūdas varbūtiskus modeļus, kas spēj definēt nesanumurējami daudz valodu. Mēs sākam ar stingrāko nosacījumu - sākumā apskatām minimālus modeļus, kas var atpazīt visas valodas. Mēs apskatām varbūtiskas Tjūringa mašīnas, varbūtiskus automātus ar skaitītājiem un varbūtiskus galīgus automātus ar dažādiem ierobežojumiem uz ievadgalviņu. Mēs apskatām arī konstantas telpas pārbaudītājus (verifiers), kas mijiedarbojas ar vienu un diviem pierādītājiem (provers) un pārbauda (verify) visas valodas. Pēc tam mēs pieminētajos modeļos apskatām nesanumurējami daudzu valodu atpazīšanu un pārbaudi ar ierobežotu kļūdu. Mēs pierādām arī jaunus rezultātus par kvantu automātu modeļiem un ultrametriskiem galīgiem automātiem (kuri izmanto p-adiskus skaitļus kā amplitūdas), kas atpazīst nesanumurējami daudz valodu.