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.