1.2. Разрешимые множества

Множество натуральных чисел X называется разре­шимым, если существует алгоритм, который по любому натуральному п определяет, принадлежит ли оно множе­ству X.

Другими словами, X разрешимо, если его характери­стическая функция х(п) = (if п Є X then 1 else 0 fi) вы­числима.

Очевидно, пересечение, объединение и разность раз­решимых множеств разрешимы. Любое конечное мно­жество разрешимо.

Аналогично определяют разрешимость множеств парнатуральных чисел, множеств рациональных чисел и т. п.

1. Докажите, что множество всех рациональных чисел, меньших числа е (основания натуральных логарифмов), раз­решимо.

2. Докажите, что непустое множество натуральных чисел разрешимо тогда и только тогда, когда оно есть множест­во значений всюду определённой неубывающей вычислимой функции с натуральными аргументами и значениями.

Отметим тонкий момент: можно доказать разреши­мость множества неконструктивно, не предъявляя алго­ритма. Вот традиционный пример: множество тех п, для которых в числе ж есть не менее п девяток подряд, раз­решимо. В самом деле, это множество содержит либо все натуральные числа, либо все натуральные числа вплоть до некоторого. В обоих случаях оно разрешимо. Тем не менее мы так и не предъявили алгоритма, который по п узнавал бы, есть ли в ж не менее п девяток подряд.

3. Использованы ли в этом рассуждении какие-то свойства числа 7Г? Что изменится, если заменить слова «не менее п де­вяток» на «ровно п девяток (окружённых не-девятками)»?

Существуют ли неразрешимые множества? Сущест­вуют — просто потому, что алгоритмов (и поэтому раз­решимых подмножеств натурального ряда) счётное чи­сло, а всех подмножеств натурального ряда несчётное число. Более конкретные примеры мы ещё построим.