Неразрешимые языки

Для неразрешимого языка нет машины Тьюринга, которая принимает язык и принимает решение для каждой входной строки. w(Хотя TM может принять решение для некоторой входной строки). Проблема решенияP называется «неразрешимым», если язык L из всех случаев да Pне разрешима. Неразрешимые языки не являются рекурсивными языками, но иногда они могут быть рекурсивно перечисляемыми языками.

пример

  • Проблема остановки машины Тьюринга
  • Проблема смертности
  • Проблема матрицы смертных
  • Проблема почтовой переписки и т. Д.