Пусть f : N → N тотальная вычислимая функция. Докажите, что множество всех натуральных чисел x таких, что f(y) < f(x) для некоторого y > x, является рекурсивно перечислимым.

задан 30 Май '20 1:15

Перечисляем все пары (x,y), вычисляем значения f в этих точках. Если f(x) > f(y) и при этом y > x, то x печатаем.

Обращаю внимание, что это задача-"одноходовка".

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

Ваш ответ

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

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

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

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

отмечен:

×1,825
×178
×32

задан
30 Май '20 1:15

показан
211 раз

обновлен
30 Май '20 2:16

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

по почте:

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

по RSS:

Ответы

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

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