1.3. Перечислимые множества

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

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

Существует много эквивалентных определений пере­числимого множества. Вот некоторые из них:

Перечислимые множества

1) Множество перечислимо, если оно есть область определения вычислимой функции.

2) Множество перечислимо, если оно есть область зна­чений вычислимой функции.

3) Множество X перечислимо, если его (как иногда говорят) «полухарактеристическая» функция, рав­ная 0 на элементах X и не определённая вне X, вы­числима.

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

Пусть X перечисляется некоторым алгоритмом А. Покажем, что полу характеристическая функция множе­ства X вычислима. В самом деле, алгоритм её вычисле­ния таков: получив на вход число п, пошагово выполнять алгоритм А, ожидая, пока он напечатает число п. Как только он это сделает, выдать на выход 0 и закончить работу.

Наоборот, пусть X есть область определения (вычи­слимой) функции /, вычисляемой некоторым алгорит­мом В. Тогда X перечисляется таким алгоритмом А:

Параллельно запускать В на входах 0,1,2,..., делая всё больше шагов работы алгоритма В (сначала один шаг работы на входах 0 и 1; потом по два шага работы на входах 0,1,2, потом по три на входах 0,1, 2, 3 и так далее). Все аргументы, на которых алгоритм В закан­чивает работу, печатать по мере обнаружения.

Итак, мы установили эквивалентность исходного оп­ределения определениям 1 и 3. Если в только что при­ведённом описании алгоритма А печатать не аргументы, на которых В заканчивает работу, а результаты этой ра­боты, то получается алгоритм, перечисляющий область значений функции /. Осталось ещё убедиться, что всякое перечислимое множество есть область значений вычисли­мой функции. Это можно сделать, например, так: пусть

X есть область определения вычислимой функции, вычи­сляемой некоторым алгоритмом А. Тогда X есть область значений функции

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

Ещё одно эквивалентное определение перечислимого множества: множество натуральных чисел перечислимо, если оно либо пусто, либо есть множество значений всю­ду определённой вычислимой функции (другими словами, его элементы можно расположить в вычислимую после­довательность) .

В самом деле, пусть перечислимое множество X, пе­речисляемое алгоритмом А, непусто. Возьмём в нём ка­кой-то элемент хд. Теперь рассмотрим такую всюду опре­делённую функцию а: если на п-м шаге работы алгоритма А появляется число I, то положим а(п) = t•, если же ничего не появляется, то положим а(п) = хд. (Мы пред­полагаем, что на данном шаге работы алгоритма может появиться только одно число — в противном случае ра­боту надо разбить на более мелкие шаги.)

Заметим, что это рассуждение неконструктивно — имея алгоритм А, мы можем не знать, пусто ли пере­числяемое им множество или нет.

Теорема 1. Пересечение и объединение перечислимых множеств перечислимы.

<] Если X и У перечисляются алгоритмами А ж В, то их объединение перечисляется алгоритмом, который параллельно выполняет по шагам А и В и печатает всё, что печатают Аш В. С пересечением немного сложнее — результаты работы А ж В надо накапливать и сверять друг с другом; что появится общего — печатать. >

4. Проведите это рассуждение, используя какое-либо дру­гое эквивалентное определение перечислимости.

Как мы увидим, дополнение перечислимого множе­ства не обязано быть перечислимым.

 

не определено в противном случае.

х, если А заканчивает работу на х

Перечислимые и разрешимые множества

5. Иногда говорят о так называемых «недетерминирован­ных алгоритмах» (оксюморон, но распространённый) — такой алгоритм включает в себя команды тина

п := произвольное натуральное число

(достаточно, впрочем, команды «п := 0 или 1», так как произ­вольное число можно формировать но битам). Недетермини­рованный алгоритм (при одном и том же входе) может дей­ствовать по-разному, в зависимости от того, какие «произ­вольные» числа будут выбраны. Докажите, что перечислимое множество можно эквивалентно определить как множество чисел, которые могут появиться на выходе недетерминиро­ванного алгоритма (при фиксированном входе).

6. Докажите, что если множества А С N и В С N перечи­слимы, то их декартово произведение А х В С N х N также перечислимо.