Rekursiooni ja keerukusteooria eksami konspekt
Teoreem: KV grammatikate ühesuse probleem pole lahenduv. T: selle saab redutseerida Posti vastavuse
probleemile. Oletame, et grammatika G on ühene. Keel L (G) on kahe ühese keele La (G) ja Lb (G) ühend.
Kui L(G) pole ühene, siis sõnedel, mis kuuluvad La ja Lb ühisossa, on kaks erinevat tuletuspuud
(vasaktuletust). Kas aga neil keeltel on ühisosa? See on Posti vastavuse probleem, mis pole lahenduv.
28 Algoritmide keerukuse hindamine. Algoritmi keerukuse sõltuvus arvutamismudelist.
DEF: Algoritmi keerukus on funktsioon f : N → N, mis seab sisendandmete mahule n vastavusse algoritmi
sammude arvu (ajaline keerukus) või kasutatava mälu mahu (mahuline keerukus).
ajaline keerukus – taktide / konfiguratsioonide arv;
mahuline keerukus – kasutatud lindipositsioonide arv.
Teoreem: Olgu t(n) > n. Iga mitme lindiga Turingi masinal ajalise keerukusega O(t(n)) töötava programmi
annaabi.ee 
