– Se spune că o problemă de decizie P este semi-decidabilă (adică are un semi-algoritm) dacă limbajul L al tuturor instanțelor da la P este r.e. – (Problemă de echivalență pentru DFA) Având în vedere două DFA, acceptă aceeași limbă? Dovada: Amintiți-vă argumentul lui Cantor din prima prelegere.
Când se spune că o problemă este semi-decidabilă?
Problemele semi-decidabile sunt cele pentru pe care o mașină Turing le oprește pe intrarea acceptată de ea, dar poate fie să se oprească, fie să circule pentru totdeauna pe intrarea care este respinsă de către mașina Turing. Astfel de probleme sunt denumite probleme Turing Recognizable.
Care este o problemă parțial decidabilă?
Definiție: Unul a cărui limbă asociată este o limbă enumerabilă recursiv. În mod echivalent, există un algoritm care oprește și emite 1 pentru fiecare instanță care are un răspuns „da”, dar pentru cazurile cu un răspuns „nu” este permis fie să nu se oprească, fie să se oprească și să scoată 0.
Problema de oprire este parțial decidabilă?
Alan Turing a demonstrat în 1936 că un algoritm general care rulează pe o mașină Turing care rezolvă problema opririi pentru toate perechile posibile de intrare program nu poate exista în mod necesar. Prin urmare, problema opririi este indecidabilă pentru mașinile Turing.
De ce problema opririi este semi-decidabilă?
Se spune că o limbă este semi-decidabilă dacă există o mașină Turing care se oprește dacă un cuvânt aparține limbii (cazuri DA) și poate respinge sau merge la infinit buclă dacă cuvântul nu aparține limbii (Fără caz).
