"usellise" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

• K (ai)=0||···|0=i, kui ai∈Σ; (i = 0…t) • K (;) = 0||…|0 = t + 1; (tähestiku viimane on t) • K (L) = 0||…|0 = t + 2; • K (S) = 0||…|0 = t + 3; • K (R) = 0||…|0 = t + 4; • K (qj)=0||···|0=t+5+j, kui qj∈Σ; Peatumisprobleem: me ei saa ehitada Turingi masinat, mis ütleks, kas masin peatub või ei. Me saaksime sellisele rakendada külge lisaosad, mis “jah, peatub” korral viiksid masina lõpmatusse tsüklisse ja “ei 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,..