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