0
1

Помогите, пожалуйста, доказать:

Докажите, что пара вычислимо перечислимых множеств {n|φn (0) ↓= 0} и {n|φn (0) ↓= 1} неотделима, где φ - универсальная частично вычислимая функция.

задан 7 Май 17:14

изменен 9 Май 15:33

По-моему, это есть в параграфе 2.4 книги Верещагина и Шеня "Вычислимые функции".

(8 Май 13:48) falcao

Пример в книге действительно похож, но там функция d изначально дана как не имеющая всюду определенного продолжения, в данном случае, я пока не смог доказать или опровергнуть это для ф(n, 0). Пытаюсь доказывать от противного, но из-за фиксированного аргумента пока не выходит.

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

Ваш ответ

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

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

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

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

отмечен:

×649
×619
×153
×43
×3

задан
7 Май 17:14

показан
134 раза

обновлен
9 Май 15:33

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

по почте:

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

по RSS:

Ответы

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

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