Nierozstrzygalne języki

W przypadku nierozstrzygalnego języka nie ma maszyny Turinga, która akceptuje język i podejmuje decyzję dla każdego ciągu wejściowego w(TM może jednak podjąć decyzję dla jakiegoś ciągu wejściowego). Problem decyzyjnyP nazywana jest „nierozstrzygalną”, jeśli język L wszystkich instancji tak do Pjest nierozstrzygalna. Języki nierozstrzygalne nie są językami rekurencyjnymi, ale czasami mogą to być języki rekurencyjnie wyliczalne.

Przykład

  • Problem zatrzymywania maszyny Turinga
  • Problem śmiertelności
  • Problem matrycy śmiertelników
  • Problem z korespondencją pocztową itp.