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.