"arvtatavuseks" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

-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,..,hm) = g(h1,..,hm) Rekursioon: n+1-kohaline f-n f on saadud n-kohalisest f