|
Почему выбран неверный вариант? 1) Это точно верно. 2) Натуральные числа разрешимы, но множество программ, останавливающихся на себе - нет. Это контрпример. 3) Это тоже верно. Просто надо "swap" ответ. 4) Тоже верно.
1) Верно. Если А конечно, то оно даже разрешимо, а тогда и перечислимо. 2) Наверное, верно? Если А перечислимо, то оно есть область определения вычислимой функции. Рассмотрим ограничение этой функции на B. Получится вычислимая функция с областью определения В. То есть В перечислимо. 3) Не знаю, но подозреваю, что неверно. Какой контрпример? 4) Это точно верно. задан 22 Май '20 2:22 
logic |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
22 Май '20 2:22
показан
81 раз
обновлен
22 Май '20 2:32
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Непонятно, что не так с первым вопросом. В условии требуется выбрать НЕверные утверждения. Такое там одно, его и выбрали.
В пункте 4 второе утверждение про B < A, конечно, неверно. Ведь можно взять A=N, а в качестве подмножества B любой пример неперечислимого. Рассуждение ошибочно, так как функция ограничения не будет вычислимой. Чтобы сузить область определения и сделать f не определённой вне B, надо уметь распознавать элементы из B.
Пример перечислимого с неперечислимым дополнением стандартен. Надо взять перечислимое, но не разрешимое (множество номеров останавливающихся машин).