"doominokivi" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

Ei leidu algoritmi, mis etteantud suvalise arvutatava funktsiooni f põhjal teeks kindlaks, kas võrrand f (x ) = 0 on arvutatav või mitte. 26 Posti vastavuse probleemi mittelahenduvus. Mittelahenduvate ülesannete näited. vt punkt 17 Teoreem: Posti vastavuse probleem on mittelahenduv. T: Kui oleks lahenduv, leiduks predikaat P(α,β) = 1, kui leidub; 0, kui ei leidu. Peaksime tegema karakteristliku TM. Iga ülemineku jaoks võtame ühe doominokivi ja teeme vastavuste süsteemi: Kui masin peatub, on sõne kujul: ♯C0♯C1♯…♯Cm♯Cm’♯Cm’'♯...♯qa♯♯
 C0…Cm on konfiguratsioonide jada x aktsepteerimisel. 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