– O rozhodovacím problému P se říká, že je semirozhoditelný (tj. má semi-algoritmus), pokud jazyk L všech instancí ano vůči P je r.e. – (Problém ekvivalence pro DFA) Přijímají dvě DFA stejný jazyk? Důkaz: Připomeňte si Cantorův argument z první přednášky.
Když se o problému říká, že je částečně rozhodnutelný?
Polorozhoditelné problémy jsou ty pro které se Turingův stroj zastaví na jím přijatém vstupu, ale může se buď zastavit nebo navždy zacyklit na vstupu, který Turingův stroj odmítne. Takové problémy se nazývají Turingovy rozpoznatelné problémy.
Co je částečně rozhodnutelný problém?
Definice: Jeden jehož přidružený jazyk je rekurzivně vyčíslitelný jazyk. Ekvivalentně existuje algoritmus, který se zastaví a vydá 1 pro každou instanci s odpovědí "ano", ale pro případy s odpovědí "ne" je povoleno buď nezastavit, nebo zastavit a vydat 0.
Je problém zastavení částečně řešitelný?
Alan Turing v roce 1936 dokázal, že obecný algoritmus běžící na Turingově stroji, který řeší problém zastavení pro všechny možné dvojice program-vstup, nutně nemůže existovat. Proto je problém zastavení pro Turingovy stroje nerozhodnutelný.
Proč je problém zastavení částečně rozhodnutelný?
O jazyku se říká, že je polorozhoditelný, pokud existuje Turingův stroj, který se zastaví, pokud slovo patří do jazyka (případy ANO) a může odmítnout nebo přejít do nekonečna smyčka, pokud slovo nepatří k danému jazyku (ŽÁDNÁ malá a velká písmena).
