– Problem decyzyjny P jest uważany za częściowo rozstrzygalny (tj. ma półalgorytm), jeśli język L wszystkich wystąpień tak do P jest r.e. – (Problem równoważności dla DFA) Biorąc pod uwagę dwa DFA, czy akceptują ten sam język? Dowód: Przypomnij sobie argument Cantora z pierwszego wykładu.
Kiedy mówi się, że problem jest częściowo rozstrzygający?
Problemy półrozstrzygalne to te, dla których maszyna Turinga zatrzymuje się na danych wejściowych przez nią zaakceptowanych, ale może albo zatrzymać się, albo zapętlić w nieskończoność na wejściu, które zostało odrzucone przez maszynę Turinga. Takie problemy są określane jako problemy rozpoznawalne przez Turinga.
Co to jest problem częściowo rozstrzygalny?
Definicja: Jeden powiązany język jest językiem rekurencyjnie przeliczalnym. Równoważnie istnieje algorytm, który zatrzymuje i wyświetla 1 dla każdego przypadku z odpowiedzią "tak", ale w przypadkach z odpowiedzią "nie" można albo nie zatrzymywać się, albo zatrzymać i wypisać 0.
Czy problem z zatrzymaniem jest częściowo rozstrzygalny?
Alan Turing udowodnił w 1936 roku, że ogólny algorytm działający na maszynie Turinga, który rozwiązuje problem zatrzymania dla wszystkich możliwych par program-wejście, koniecznie nie może istnieć. Stąd problem zatrzymania jest nierozstrzygnięty dla maszyn Turinga.
Dlaczego problem zatrzymania jest częściowo rozstrzygający?
Język jest określany jako częściowo rozstrzygający, jeśli istnieje maszyna Turinga, która zatrzymuje się, jeśli słowo należy do języka (przypadki TAK) i może odrzucić lub przejść w nieskończoność pętla, jeśli słowo nie należy do języka (brak przypadku).
