Что все известные языки, которые машины Тьюринга не могут принять?

Question

Для example, язык машин Тьюринга, которые не принимают свою собственную кодировку, не может быть принят любой машиной Тьюринга.

Answer 1

Существует бесконечное количество языков, которые не могут решить никакие ТМ. Действительно, «большинство» языков неразрешимы; существует множество разрешимых языков, но несчетно много языков (следовательно, несчетно много неразрешимых).

Теорема Райса позволяет вам придумать множество примеров языков, которые неразрешимы. См. Страницу Википедии: Rice's Theorem

В принципе, если у вас есть набор нетривиальных языков (т. Е. Существуют ТМ, которые распознают языки в наборе и ТМ, которые распознают языки не в наборе), то это неразрешима, является ли произвольный язык ТМ в S. Например, пусть S - множество, состоящее из пустого языка. Тогда невозможно решить, принимает ли произвольная ТМ пустой язык, т. Е. Нет строк. Придумайте любой нетривиальный набор языков, и у вас есть новый неразрешимый язык (все кодировки TMs, распознающих языки в наборе).