1
1

Докажите, что множества {i | φ_i(0) не определено} и {i | φ_i(0) = 1} не отделимы разрешимым множеством.

задан 30 Сен '19 20:16

@forlan88: без уточнения того, что такое ф_i, задача не имеет смысла.

(30 Сен '19 21:01) falcao

@falcao Через ф_i во всех задачах обозначена главная универсальная функция (нумерация) для для семейства всех частичных вычислимых функций N → N

(30 Сен '19 22:50) forlan88
10|600 символов нужно символов осталось
1

Рассуждение примерно такое. Известно, что проблема применимости фn к 0 неразрешима. Допустим, что мы разделили множества из условия некоторым разрешимым. Программа, вычисляющая фn, может быть видоизменена таким образом, что вместо значения фn(0) в момент остановки она всегда выдаёт 1. Поскольку нумерация главная, мы знаем номер m модифицированной программы. Проверяем, принадлежит ли m разрешимому множеству, содержащему первое множество из условия. Если да, то фm(0) не равно 1, и тогда фn(0) не определено. Если нет, то фm(0) определено, а тогда оно равно 1, и фn(0) определено. Получается решение алгоритмически неразрешимой проблемы, сформулированной выше.

ссылка

отвечен 1 Окт '19 2:52

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×53

задан
30 Сен '19 20:16

показан
488 раз

обновлен
1 Окт '19 2:52

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

по почте:

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

по RSS:

Ответы

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

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