Rozstrzygalność języka
Nazywa się język Decidable lub Recursive jeśli istnieje maszyna Turinga, która akceptuje i zatrzymuje się na każdym ciągu wejściowym w. Każdy możliwy do rozstrzygnięcia język jest akceptowalny metodą Turinga.
Problem decyzyjny P jest rozstrzygalny, jeśli język L wszystkich instancji tak do P jest rozstrzygalny.
W przypadku języka rozstrzygalnego dla każdego ciągu wejściowego baza TM zatrzymuje się w stanie akceptacji lub odrzucenia, jak pokazano na poniższym diagramie -
Przykład 1
Dowiedz się, czy następujący problem jest rozstrzygalny, czy nie -
Czy liczba „m” jest pierwsza?
Rozwiązanie
Liczby pierwsze = {2, 3, 5, 7, 11, 13, ………… ..}
Podziel liczbę ‘m’ wszystkimi liczbami od „2” do „√m”, zaczynając od „2”.
Jeśli którakolwiek z tych liczb daje resztę zera, to przechodzi do „stanu odrzuconego”, w przeciwnym razie przechodzi do „stanu zaakceptowanego”. Tak więc tutaj odpowiedź można by udzielić „Tak” lub „Nie”.
Hence, it is a decidable problem.
Przykład 2
Biorąc pod uwagę zwykły język L i ciąg w, jak możemy sprawdzić, czy w ∈ L?
Rozwiązanie
Weź DFA, który akceptuje L i sprawdź, czy w jest akceptowane
Niektóre bardziej rozstrzygające problemy to -
- Czy DFA akceptuje pusty język?
- Czy L 1 ∩ L 2 = ∅ dla regularnych zestawów?
Note -
Jeśli język L jest rozstrzygalny, to jego uzupełnienie L' jest również rozstrzygalny
Jeśli język jest rozstrzygalny, istnieje dla niego moduł wyliczający.