Бесконечное разрешимое подмножество бесконечного перечислимого множества/Решение

Материал из DISCOPAL
< Бесконечное разрешимое подмножество бесконечного перечислимого множества
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Подзадача: что любое бесконечное перечислимое множество M может быть записано в виде {f(1), f(2), ...}, где f - вычислимая функция, все значения которой различны. Решение подзадачи: пусть A - алгоритм, перечисляющий M. Алгоритм B, вычисляющий f: на входе n B запускает алгоритм A, причем каждый раз при возврате алгоритмом А нового числа m алгоритм B сравнивает m со всеми напечатанными ранее числами. Если m уже было напечатано, то повторно его не выводим. Как только напечатано n чисел, алгоритм возвращает последнее из них. Ясно, что таким образом в последовательности {f(1), f(2), ...} будут перечислены все элементы M. Подзадача решена.

Рассмотрим следующую бесконечную возрастающую подпоследовательность в {f(n)}: g(1) = f(1) g(m) = "первый элемент после g(m-1), превышающий g(m)".

Пусть . Покажем: L разрешим. Пусть на вход поступило число s. Определим, принадлежит ли оно L. модифицируем алгоритм B: храним в памяти последнее (на данном шаге) число t из последовательности g(m). Для каждого следующего числа, возвращаемого B, сравниваем его с t, и если это g(m+1), то обновляем t. Если t = s, то возврат: да. если t > s, то возврат: нет