|
Помогите, пожалуйста, доказать: Докажите, что пара вычислимо перечислимых множеств {n|φn (0) ↓= 0} и {n|φn (0) ↓= 1} неотделима, где φ - универсальная частично вычислимая функция. задан 7 Май '20 17:14 
DEGoZ |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
7 Май '20 17:14
показан
478 раз
обновлен
9 Май '20 15:33
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
По-моему, это есть в параграфе 2.4 книги Верещагина и Шеня "Вычислимые функции".
Пример в книге действительно похож, но там функция d изначально дана как не имеющая всюду определенного продолжения, в данном случае, я пока не смог доказать или опровергнуть это для ф(n, 0). Пытаюсь доказывать от противного, но из-за фиксированного аргумента пока не выходит.