Probabilistic computation and verification beyond Turing machines

Abstract

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.

Our aim is to investigate different bounded-error probabilistic models that can define uncountably many languages. We begin with stronger condition - we first consider minimal models that can recognize all languages. We consider probabilistic Turing machines, probabilistic counter automata, and probabilistic finite state automata with various restrictions on the input head. We also consider constant-space verifiers that interact with one and two provers and verify all languages. After that we consider the recognition and verification of uncountably many languages with bounded error for these models. We also present new results for quantum automata models and ultrametric finite automata (which use p-adic numbers as amplitudes) that recognize uncountably many languages.