alt text

Почему выбран неверный вариант?

1) Это точно верно.

2) Натуральные числа разрешимы, но множество программ, останавливающихся на себе - нет. Это контрпример.

3) Это тоже верно. Просто надо "swap" ответ.

4) Тоже верно.

alt text

1) Верно. Если А конечно, то оно даже разрешимо, а тогда и перечислимо.

2) Наверное, верно? Если А перечислимо, то оно есть область определения вычислимой функции. Рассмотрим ограничение этой функции на B. Получится вычислимая функция с областью определения В. То есть В перечислимо.

3) Не знаю, но подозреваю, что неверно. Какой контрпример?

4) Это точно верно.

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

Непонятно, что не так с первым вопросом. В условии требуется выбрать НЕверные утверждения. Такое там одно, его и выбрали.

В пункте 4 второе утверждение про B < A, конечно, неверно. Ведь можно взять A=N, а в качестве подмножества B любой пример неперечислимого. Рассуждение ошибочно, так как функция ограничения не будет вычислимой. Чтобы сузить область определения и сделать f не определённой вне B, надо уметь распознавать элементы из B.

Пример перечислимого с неперечислимым дополнением стандартен. Надо взять перечислимое, но не разрешимое (множество номеров останавливающихся машин).

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

Ваш ответ

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

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

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

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

отмечен:

×870

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

показан
15 раз

обновлен
22 Май 2:32

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

по почте:

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

по RSS:

Ответы

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

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