Найдите тотальную вычислимую функцию f: N → N и разрешимое множество A ⊂ N, для которых множество f(A) неразрешимо.

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

1

Задача фактически равносильна предъявлению перечислимого, но не разрешимого множества. Берём любой известный нам пример (скажем, множество номеров машин Тьюринга, останавливающихся за конечное время). Тогда за f(n) принимаем номер машины, которое перечисляющее устройство печатает на n-м шаге.

(30 Сен '19 20:26) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×53

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

показан
620 раз

обновлен
30 Сен '19 20:26

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

по почте:

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

по RSS:

Ответы

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

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