Rekursiooni ja keerukusteooria eksami konspekt
Cm’ jne on saadud Cm-i algusest 1, 2 jne sümboli
kustutamisel. Konfiguratsioonide jada, mille puhul TM aktsepteerib ja peatub, ei saa ette teada. Turingi
masina määramispiirkond on sisendite hulk, mille puhul see TM peatub. See hulk ei ole määratud.
27 Ülesannete redutseeritavus. KV keelte ühesuse mittelahenduvus.
Ülesannete lahenduvuse üle otsustamiseks kasutasime nende taandamist ülesannetele, mille lahenduvus
on teada. Olgu A ja B ülesanded. Öeldakse, et ülesanne A on reduseeritav ülesandele B, kui B iga
lahendus annab lahenduse ka A-le.
DEF: Keel A on m-redutseeritav keelele B, mida tähistatakse A <=m B, kui leidub selline arvutatav
funktsioon f : Σ* → Σ*, nii et iga w ∈ Σ* korral w ∈ A f (w) ∈ B.
Teoreem: Kui A on redutseeritav B-le ja hulk B on lahenduv, siis hulk A on lahenduv.
T: Kui M on B karakteristlikku funktsiooni realiseeriv TM (B on seega lahenduv) ja f: A → B redutseeriv f, siis
annaabi.ee 
