– Otsustusülesannet P peetakse poolotsustatavaks (st omab poolalgoritmi), kui P kõigi jah-juhtumite keel L on r.e. – (DFA ekvivalentsusprobleem) Kas kaks DFA-d aktsepteerivad sama keelt? Tõestus: tuletage meelde Cantori argumenti esimesest loengust.
Kui öeldakse, et probleem on pooleldi lahendatav?
Poollahutavad probleemid on need mille Turingi masin peatab tema poolt vastuvõetud sisendil, kuid see võib kas peatada või igaveseks silmuse teha sisendil, mille Turingi masin tagasi lükkab. Selliseid probleeme nimetatakse Turingi äratuntavateks probleemideks.
Mis on osaliselt lahendatav probleem?
Definitsioon: millega seotud keel on rekursiivselt loendatav keel. Samaväärselt on olemas algoritm, mis peatab ja väljastab 1 iga eksemplari puhul, mille vastus on "jah", kuid "ei" vastuse korral on lubatud kas mitte peatada või peatada ja väljastada 0.
Kas probleemi peatamine on osaliselt lahendatav?
Alan Turing tõestas 1936. aastal, et Turingi masinal töötavat üldist algoritmi, mis lahendab kõigi võimalike programmi-sisendi paaride peatumisprobleemi, ei saa tingimata eksisteerida. Seega on peatamise probleem Turingi masinate jaoks lahendamatu.
Miks on peatamise probleem pooleldi otsustatav?
Keelt peetakse poolotsustatavaks, kui on olemas Turingi masin, mis peatub, kui sõna kuulub keelde (JAH-juhud) ja võib tagasi lükata või minna lõpmatusse tsükkel, kui sõna ei kuulu keelde (MITTE suurtähtedega).
