Докажите, что множество A = {<x,y> | Wx ∪ Wy != ∅} рекурсивно перечислимо и K <_m A, где K = {x | φx(x)↓}.

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

изменен 30 Май '20 2:27

Условие при переписывании превратилось в нечто бессмысленное.

(30 Май '20 2:17) falcao

Исправил условие насколько возможно

(30 Май '20 2:33) kiltonik

@kiltonik: теперь исчез целый ряд бессмысленных символов, включая неуместные цифры 6 и многое другое. Но осознаёте ли Вы, что обозначение Wx без дополнительного разъяснения ничего не значит? Я только что написал ответ по другой задаче, где Wx означало dom ф(x), но здесь-то в условии это ниоткуда не следует, а обозначение совсем не является общепринятым.

Под K<_m A, видимо, понимается m-сводимость: $%K\le_m A$%.

(30 Май '20 2:39) falcao

Да, неравенство Вы правильно поняли (не смог найти как вставить формулы используя дефолтный редактор). Относительно Wx, исходя из общего контекста работы, осмелюсь предположить, что оно равно dom ф(x).

(30 Май '20 2:54) kiltonik

Это не неравенство -- оно лишь внешне имеет такую форму. Это называется m-сводимостью (см. Верещагин и Шень, стр. 64).

(30 Май '20 2:55) falcao
10|600 символов нужно символов осталось
0

Надеюсь, что я правильно понял условие, но задача несколько "левоватая" (то есть искусственная).

Тут надо только вместо пар рассматривать их номера, чтобы m-сводимость относилась к двум (под)множествам натуральных чисел. То есть я буду считать, что A состоит из номеров пар вида N(x,y), где область определения хотя бы одной из программ с номером x или y непуста.

Здесь вполне достаточно было бы брать пары с одинаковыми элементами. Каждой программе с номером x можно вычислимым образом сопоставить программу с одним входом, которая всегда вычисляет значение ф_x(x). Область определения непуста <=> данное значение определено. Пусть номер программы равен y=y(x). Тогда полагаем f(x)=N(y(x),y(x)). Это вычислимое отображение, и x принадлежит K <=> f(x) принадлежит A. Это доказывает m-сводимость.

ссылка

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

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

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

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

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

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

отмечен:

×1,866
×180
×33

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

показан
319 раз

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

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

по почте:

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

по RSS:

Ответы

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

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