– O rozhodovacom probléme P sa hovorí, že je polorozhodnutý (t. j. má semi-algoritmus), ak jazyk L všetkých prípadov áno voči P je r.e. – (Problém ekvivalencie pre DFA) Prijímajú vzhľadom na dve DFA rovnaký jazyk? Dôkaz: Pripomeňte si Cantorov argument z prvej prednášky.
Keď sa o probléme hovorí, že je čiastočne rozhodnutý?
Polorozhodniteľné problémy sú problémy ktoré sa Turingov stroj zastaví na vstupe, ktorý akceptuje, ale môže sa zastaviť alebo navždy zacykliť na vstupe, ktorý Turingov stroj zamietne. Takéto problémy sa nazývajú Turingovo rozpoznateľné problémy.
Čo je čiastočne rozhodnuteľný problém?
Definícia: Jeden ktorého pridružený jazyk je rekurzívne spočítateľný jazyk. Ekvivalentne existuje algoritmus, ktorý sa zastaví a vydá 1 pre každý prípad s odpoveďou „áno“, ale pre prípady s odpoveďou „nie“je povolené buď nezastaviť, alebo zastaviť a vydať 0.
Je problém zastavenia čiastočne rozhodnutý?
Alan Turing v roku 1936 dokázal, že všeobecný algoritmus bežiaci na Turingovom stroji, ktorý rieši problém zastavenia pre všetky možné páry program-vstup, nevyhnutne nemôže existovať. Preto je problém zastavenia pre Turingove stroje nerozhodnuteľný.
Prečo je problém zastavenia čiastočne rozhodnutý?
O jazyku sa hovorí, že je polorozhoditeľný, ak existuje Turingov stroj, ktorý zastaví, ak slovo patrí do jazyka (prípady ÁNO) a môže odmietnuť alebo prejsť do nekonečna slučka, ak slovo nepatrí do jazyka (žiadne veľké a malé písmená).
