Полиномиальная иерархия/Задачи/P\poly contains unsolvable

Ссылки сюда (6) →

Показать, что содержит некоторые невычислимые функции.

Остапенко Максим, 975 группа.

Переформулируем задачу в эквивалентную форму:

Класс содержит неразрешимые языки.

Действительно, если язык - неразрешим, то предикат , невычислим.

Рассмотрим произвольный неразрешимый язык . Построим язык A следующим образом: | бинарное представление принадлежит. Язык , но то же время A неразрешим, иначе можно было бы разрешить .

Получается, что содержит неразрешимые языки.

Значит содержит невычислимые функции.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.