1
1

alt text

задан 10 Фев '15 21:23

изменен 10 Фев '15 21:41

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

Известно, что всякое (бесконечное) перечислимое множество $%S$% можно перечислять как с повторениями, так и без. Пусть $%f$% -- рекурсивная функция, перечисляющая $%S$%. Те номера, которые она печатает, алгоритм может запоминать. После этого, прежде чем напечатать очередное значение $%f(n)$%, алгоритм проверяет, не принадлежит ли оно конечному множеству уже напечатанных чисел, и печатает его в случае, если оно ещё не появлялось.

Теперь у нас имеется перечисление всех элементов множества $%S$% без повторений в виде списка: $%S=\{g(0),g(1),g(2),\ldots\}$%, где $%g(n)$% -- некоторая рекурсивная функция. Числа списка идут в произвольном порядке, то есть они могут как увеличиваться, так и уменьшаться.

Построим такое бесконечное подмножество $%T\subseteq S$%: включим в него элемент $%y_0=g(0)$%, и далее возьмём самый первый элемент $%y_1$% из списка, который больше $%g(0)$%. Такой элемент заведомо имеется по причине бесконечности множества. Теперь в качестве $%y_2$% выбираем наименьший элемент списка, который больше $%y_1$%, и так далее. Итогом будет бесконечная возрастающая последовательность $%y_0 < y_1 < y_2 < \ldots$%. Множество её членов обозначим через $%T$%.

Докажем, что $%T$% разрешимо. Укажем алгоритм, который по каждому натуральному $%n$% проверяет, принадлежит ли оно множеству $%T$%. У нас имеется вычислимая функция $%g$%, с помощью которой мы находим $%y_0=g(0)$%. Далее, используя $%\mu$%-оператор, последовательно находим элементы $%g(1)$%, $%g(2)$% , ... , пока не обнаружим элемент $%g(k) > y_0$%. Это значит, что мы нашли значение $%y_1$%. После этого снова применяем $%\mu$%-оператор, вычисляя последовательно $%g(k+1)$%, $%g(k+2)$% , ... , пока не найдем среди них элемент, больший $%y_1$%. Это даёт нам значение $%y_2$%, и так далее.

Процесс оканчивается, если нам среди элементов вида $%y_i$% попалось число $%n$%. В этом случае $%n\in T$% по построению. Если же оно не попадается, то мы продолжаем вычисления вплоть до нахождения значения $%y_n$%. Далее уже $%n$% нам точно не встретится, поскольку $%y_{n+1} > n$%, а остальные элементы ещё больше. В этом случае наш алгоритм выдаёт заключение, что $%n\notin T$%.

Заметим, что число $%n$% вполне может принадлежать множеству $%S$%, но в $%T$% оно при этом всё равно не попадёт.

ссылка

отвечен 11 Фев '15 1:05

@falcao что в данном случае понимается под рекурсивной функцией?

(8 Мар '17 14:56) tofikk

@tofikk: это одно из основных понятий теории алгоритмов. Часто бывает, что изучение курса с него и начинают. Но бывает и по-другому. В этом случае вместо "рекурсивная" следует читать "вычислимая". Это как бы одно и то же: понятие рекурсивной функция -- один из вариантов строгой формализации понятия вычислимой функции.

(8 Мар '17 16:21) falcao

@falcao помогите пожалуйста разобраться

Преподаватель говори, что нужно выразить функцию определяющую Т выразить её через g

вариант "мы отбираем по алгоритму" не подходит ему

Нужно написать формулу определяющую Т.

То есть Т определяется ...

(9 Июн '17 19:43) s1mka

@s1mka: это неправильный подход. Бывает так, что требуется доказать существование какого-то алгоритма, или вычислимость некоторой функции. Тогда можно требовать построения этих объектов в рамках заданного алгоритмического языка, то есть, упрощённо говоря, предъявить "формулу". Здесь же в условии говорится о доказательстве существования множества T, и никаких ограничений на средства, при помощи которых это существование устанавливается, накладываться не должно. А доказательство разрешимости самого T у меня тут есть. Оно проводится на основе понятия рекурсивной функции во всех деталях.

(9 Июн '17 19:51) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,823
×690

задан
10 Фев '15 21:23

показан
1580 раз

обновлен
9 Июн '17 19:51

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

по почте:

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

по RSS:

Ответы

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

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