Темирлан: Новая страница: «*Бесконечное разрешимое подмножество бесконечного перечислимого множества Подзадач…»

2017-05-10T22:58:33Z

Новая страница: «*Бесконечное разрешимое подмножество бесконечного перечислимого множества Подзадач…»

Новая страница

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

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

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

Темирлан: Новая страница: «*Бесконечное разрешимое подмножество бесконечного перечислимого множества Подзадач…»