Бесконечное разрешимое подмножество бесконечного перечислимого множества/Решение
Подзадача: что любое бесконечное перечислимое множество 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, то возврат: нет
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.