alt text

задан 18 Фев '15 20:55

10|600 символов нужно символов осталось
1

Элементы бесконечного разрешимого множества $%A$% представимы в виде членов возрастающей последовательности $%a_1 < a_2 < \cdots < a_n < \cdots$%, где функция $%f(n)=a_n$% вычислима. Этот факт в одном из упражнений уже обсуждался. Теперь рассмотрим перечислимое, но не разрешимое подмножество $%X$% в $%\mathbb N$% -- в курсе теории алгоритмов доказывается, что такие множества существуют. Теперь рассмотрим множество $%f(X)\subset A$%, то есть множество членов последовательности вида $%a_m$%, где $%m\in X$%. Очевидно, что это множество перечислимо: к каждому элементу перечислимого множества $%X$% применяется вычислимая функция $%f$%, что даёт перечисление множества $%f(X)$%.

Проверим, что множество не разрешимо. Если бы мы располагали алгоритмом, который по заданному числу проверяет, принадлежит ли оно $%f(X)$%, то применение этого алгоритма к числу $%f(n)$% позволило бы алгоритмически проверять условие $%f(n)\in f(X)$%, равносильное условию $%n\in X$% с учётом монотонности функции $%f$%. А наличие такого алгоритма означало бы разрешимость множества $%X$%.

ссылка

отвечен 18 Фев '15 23:42

@falcao а не могли бы вы указать ссылку на упражнение, где обсуждался факт, упомянутый в начале доказательства?

(27 Фев '17 20:03) tofikk

@tofikk: попробуйте найти через поиск по ключевым словам. Можно посмотреть вопросы от того же участника по списку, звучавшие примерно тогда же (февраль 2015). Но вообще-то сам факт очевиден, доказывается от так. Мы проверяем числа 1, 2, ... подряд на предмет принадлежности A. Алгоритм для такой проверки есть по условию. Каждое число из A учитываем, то есть заводим счётчик. Таких чисел бесконечно много. Рано или поздно (за конечное время) нам попадётся n-е по счёту. Оно и есть значение f(n), то есть мы умеем его алгоритмически находить.

(27 Фев '17 21:19) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,062
×488

задан
18 Фев '15 20:55

показан
1107 раз

обновлен
27 Фев '17 21:19

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

по почте:

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

по RSS:

Ответы

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

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