"matiyasevich" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

peatu” korral viiksid ta lõppolekusse. uSellise masina saaksime ühendada selle sama masina sisendisse. Nüüd oleks paradoks: kui masin ei peatu, siis ta peatub, kui peatub, siis ei peatu jne. Hilberti 10. probleem: Kas täisarvuliste kordajatega polünoomi P(x1,...,xn) korral on võrrandil P(x1,...,xn)=0 täisarvulisi lahendeid? Seda lahendati 21 aastat. Sellest on film tehtud. Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson. Ja ei ole lahendeid. Posti vastavuse probleem: Olgu antud sõnede järjendid α = ⟨α1,...,αn⟩ ja β = ⟨β1,...,βn⟩. Kas leidub selline indeksite lõplik jada i1,...,ik, et αi1...αik =βi1…βik? nt α = ⟨aa, bb, abb⟩ ja β = ⟨aab, ba, b⟩ Kui võtame indeksite järjestuse 1,2,1,3, siis α-sõnedest saame: aa bb aa abb ja β-sõnedest: aab ba aab b. KV-keelte ühesuse probleem pole algoritmiliselt lahenduv