Является ли множество {(p,q) | U(p,q) не равно U(q,p)} а) разрешимым б) перечислимым? Мы счита- ем, что U(p,q) не равно U(q,p) только если обе функции определены в соответствующих точках. (Пункты оцениваются как две отдельные задачи.)

задан 18 Фев '18 0:13

10|600 символов нужно символов осталось
1

б) Будем перечислять все тройки вида (p,q,n). Для каждой такой тройки запускаем программу с номером p для числа x=q на n шагов, и то же делаем с программой номер q при x=p. Если обе программы за это время остановились и дали разные результаты, то пару (p,q) печатаем. Это даёт перечислимость.

а) Если указанное множество разрешимо, то мы располагаем алгоритмом, который проверяет принадлежность ему пар вида (p,p). Последнее означает, что мы умеем решать проблему самоприменимости, то есть выяснять, останавливается ли программа номер p для числа x=p (если U(p,p) определено, то имеет место равенство значений, и пара множеству не принадлежит, и наоборот). Но эта проблема неразрешима, поэтому множество также неразрешимо.

ссылка

отвечен 18 Фев '18 1:07

1

@falcao Так а если U(p, p) не определено, то пара (p, p) тоже не принадлежит множеству, разве не так?

(20 Фев '18 21:49) FrostABC

@FrostABC: видимо, Вы правы. Я с этим "не равно" малость запутался. Тогда надо чуть модифицировать рассуждение. Пусть p0 -- номер программы для всюду определённой функции -- например, нулевой. Тогда попадание пары (p0,q) в множество означает, что U(q,p0) либо не определено, либо определено, но не равно нулю. Для любой машины Тьюринга можно написать программу, которая работает одинаково на всех входах. При остановке машины выдаётся 0. Тогда через попадание пары в наше множество мы умеем распознавать, останавливается ли машина.

(21 Фев '18 1:30) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,481

задан
18 Фев '18 0:13

показан
542 раза

обновлен
21 Фев '18 1:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru