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

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

Подзадача: что любое бесконечное перечислимое множество 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)".

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