Языковая классификация (вычисления)

Question

Мне нужно определить, является ли L:={<M>|HP<=L(M)} рекурсивным языком, и если L является рекурсивно перечислимым языком.

Я думаю, что теорема Райса может помочь доказать, что L не является рекурсивной, но я не думаю, что L рекурсивно перечислимо ...

Answer 1

Если L не в RE, то L также не в R.

Вы должны попытаться свести его к проблеме остановки.Допустим, X - это машина Тьюринга, которая выдает false, если L (X) истинно, и выводит true, если L (X) ложно.

Является ли L (X) истиной?Это если и только если L (X) ложно, что противоречит.

Является ли L (X) ложью?Это если и только если L (X) истинно, что также является противоречием.

Противоречие заключается в неявном предположении, что L вычислима на машине Тьюринга.Следовательно, L не вычислимо.Машина Х Тьюринга не может существовать.И, наконец, L не в RE (и не в R).