..,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 Church-Turingi tees: Iga efektiivselt (algoritmiliselt) arvutatav funktsioon on realiseeritav (arvutatav) Turingi masinal. Ehk iga asja, mida saab normaalse aja jooksul välja arvutada, saab arvutada ka Turingi masinal. 18 Lihtrekursiivsed funktsioonid, nende arvutatavus Turingi mõttes. DEF: Lihtrekursiivsed funktsioonid on konstrueeritavad elementaarfunktsioonidest superpositsiooni- ja rekursioonioperaatori abil. Lihtrekursiivsed funktsioonid on kõikjal määratud. nt summa, korrutis, x!, sign Elementaarfunktsioonideks loetakse järgmised funktsioonid: • konstantne funktsioon On : Nn → N, mis iga väärtuste komplekti x1,...,xn ∈ N korral omab väärtust 0.
JMP Rj = Ri JMP if NULL CONTINUE Iga Turingi masinal arvutatav f.-n on realiseeritav registermasinal. Tõestus kirjutame Turingi masina üleminekufunktsiooni registermasina mällu. Iga registermasina programm on realiseeritav Turingi masinal: Esitame registermasina kõigi nullist erinevate registrite sisu Turingi masina lindil Turingi masin ja registermasin on arvutatavuse mõttes ekvivalentsed. Church-Turingi tees: iga efektiivselt arvutatav funktsioon on realiseeritav Turingi masinal 24. Lihtrekursiivsed funktsioonid, nende arvutatavus Turingi mõttes. Arvtatavuseks piisab kolmest operaatorist: · superpositsioon (f.-nide järjest rakendamine) · rekursioon (f.-ni rakendamine iseenda sees omaenese eelmistele väärtustele) · minimeerimine arvutamine teatud tingimuse täitumiseni Superpositsioon: n-kohaline f.-n f on saadud m kohalisest f.-nist g ja n kohalistest f.-nidest hi (i = 1,..,m) superpositsioonioperaatori rakendamisel, kui f = Sm+1(g;h1,.
annaabi.ee 
