Функция f : N → N называется строго возрастающей на множестве B ⊆ N, если f определена на множестве B (т.е. для любого x ∈ B значение f(x) определено) и для любых x, y ∈ B, если x < y, то f(x) < f(y). Докажите, что множество

A = {x | φx не является строго возрастающей на Wx}, где Wx = dom φx = {y | φx(y)↓}, рекурсивно перечислимо, но не рекурсивно.

задан 30 Май '20 1:23

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

Если $%\phi_x$% не является строго возрастающей на своей области определения, то этому имеется свидетельство в виде двух чисел $%a < b$%, для которых $%\phi_x$% определена, и при этом $%\phi_x(a)\ge\phi_x(b)$%. Каждое вычисление оканчивается за конечное число шагов. Поэтому, перебирая тройки вида $%(a,b,n)$% и прогоняя программу $%\phi_x$% на элементах $%a$% и $%b$% на глубину $%n$% шагов, мы такое свидетельство обнаружим. Тогда у нас будет основание напечатать число $%x$%. Это доказывает перечислимость $%A$%.

Разрешимость множества означает, что оно перечислимо вместе со своим дополнением. Поэтому второй факт равносилен тому, что дополнение $%A$% не перечислимо. Это доказывается от противного. Достаточно взять подходящую алгоримтически неразрешимую проблему, и показать, что она решается в предположении перечислимости дополнения $%A$%.

Возьмём проблему остановки машин Тьюринга на пустой ленте. По каждой такой машине строим программу, которая на любом входе запускает эту машину. Если происходит остановка, то программа выдаёт значение $%0$%. Такая функция является тождественно нулевой, если машина останавливается, и нигде не определённой, если не останавливается. В последнем случае функция читается возрастающей на своей области определения (пустой). Тогда её номер даст процедура, перечисляющая дополнение $%A$%. Получается, что множество номеров не останавливающихся машин перечислимо, а это не так.

ссылка

отвечен 30 Май '20 2:35

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,866
×180
×33

задан
30 Май '20 1:23

показан
310 раз

обновлен
30 Май '20 2:35

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

по почте:

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

по RSS:

Ответы

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

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