alt text

Верны ли рассуждения?

1) Нет, множество программ, останавливающихся на себе перечислимо, но не разрешимо.

2) Да, это чья-то теорема.

3) Да, А есть объединение этих двух множеств, а объединение двух разрешимых множеств разрешимо.

4) Нет, Если $%B\subset A$% бесконечно, то $%A-B$% может быть бесконечным тоже. Если бы оно было конечным, то A было бы разрешимо. Но т.к. нет гарантии, что это дополнение конечно, нельзя гарантировать его разрешимость. Есть какой-то простой контрпример к этому пункту?

alt text

Какие контрпримеры можно привести? Тут без понятия.

задан 22 Май 2:35

Опять тест :( Делали бы хоть из него "выжимку".

В 5.4 я бы взял "плохое" подмножество X, заменил его на 2X и добавил к нему все нечётные.

В 6 нужно знать стандартные примеры типа перечислимого, но не разрешимого. А также предыдущий "трюк" с перенесением "плохого" множества с N на 2N.

(22 Май 2:45) falcao

Насчет 5.4, множеством А будет результат описанных действий? (Т.е. нечетные числа объединенные с 2Х) Или что? Тогда почему оно не разрешимо? Или для начала, что такое "плохое" подмножество Х? Имеется ли в виду, что Х неразрешимо, тогда 2Х неразрешимо, и тогда множество 2X u (2N+1) тоже неразрешимо?

(22 Май 3:01) logic

@logic: я подал идею, и её достаточно для построения примера. "Плохое" в разном контексте может быть неразрешимое, неперечислимое, и так далее. Такого уровня вещи надо сначала воспринимать "спинным" мозгом, а потом уже "головным" :) То есть на уровне "много-мало", "горячо-холодно". Вот Вы в конце эти соображения "включили", и сразу поняли, в чём дело. Проверка неразрешимости тут тривиальна.

(22 Май 3:16) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×870

задан
22 Май 2:35

показан
20 раз

обновлен
22 Май 3:16

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

по почте:

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

по RSS:

Ответы

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

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