Рабочее множество¶

Рабочее множество — в математике, в частности в теории алгоритмов и теории вычислимости, термин, обозначающий перечислимое множество, которое является «трудным» для перечисления в том смысле, что любой алгоритм, перечисляющий его элементы, неизбежно выдаёт элементы из дополнения этого множества. Понятие введено советским математиком Владимиром Андреевичем Успенским в 1957 году для иллюстрации различий между различными определениями перечислимости и для характеризации свойств вычислимых нумераций.

¶Определение

Пусть \(A\) — бесконечное перечислимое подмножество множества натуральных чисел \(\mathbb{N}\). Множество \(A\) называется рабочим, если существует такая вычислимая функция \(f\), что для любого \(n\) значение \(f(n)\) принадлежит либо \(A\), либо дополнению \(A\), причём \(f(n)\) не может быть вычислено «слишком быстро» относительно некоторой меры сложности. В классическом определении Успенского используется понятие времени вычисления: множество \(A\) рабочее, если существует вычислимая функция \(f\) и всюду определённая вычислимая функция \(t(n)\) (ограничение времени) такие, что для любого \(n\):

1. \(f(n) \in A \cup \overline{A}\);
2. если \(f(n) \in A\), то время вычисления \(f(n)\) превышает \(t(n)\);
3. если \(f(n) \in \overline{A}\), то время вычисления \(f(n)\) не превышает \(t(n)\).

Иными словами, алгоритм \(f\) «угадывает» принадлежность числа к множеству, но для элементов самого множества ему требуется «много времени», тогда как для элементов дополнения — «мало времени». Это создаёт асимметрию: перечисление элементов \(A\) затруднено, а элементов дополнения — облегчено.

¶Свойства

• Всякое рабочее множество является перечислимым, но не является разрешимым (рекурсивным). Действительно, если бы \(A\) было разрешимым, то существовал бы алгоритм, мгновенно определяющий принадлежность любого числа, что противоречило бы условию о «долгом» времени для элементов \(A\).
• Рабочее множество не является просто перечислимым в смысле наличия «быстрой» нумерации: любая вычислимая нумерация элементов \(A\) имеет сколь угодно большие задержки.
• Существуют перечислимые множества, которые не являются рабочими (например, разрешимые множества). Также существуют перечислимые неразрешимые множества, не являющиеся рабочими, — это зависит от выбора конкретной меры сложности.
• Понятие рабочего множества тесно связано с понятием творческого множества (креативного множества), введённого Эмилем Постом. Всякое творческое множество является рабочим, но обратное неверно: рабочие множества могут быть не творческими.
• Класс рабочих множеств замкнут относительно некоторых операций, например, относительно объединения с разрешимым множеством, но не замкнут относительно дополнения (дополнение рабочего множества, как правило, не является перечислимым).

¶История и контекст

Термин «рабочее множество» (англ. productive set — в западной традиции, хотя это не совсем точный перевод; в оригинале Успенский использовал термин «продуктивное множество» для другого понятия, а «рабочее» — для описанного выше) возник в рамках дискуссии о различных определениях перечислимости. Успенский в работе «К теории вычислимых операций» (1957) исследовал, как разные формализации «эффективного перечисления» приводят к разным классам множеств. Рабочие множества демонстрируют, что интуитивное представление о «лёгкости» перечисления может быть обманчивым: даже если множество перечислимо, его элементы могут быть «трудно» получить алгоритмически.

Позднее понятие было обобщено в рамках теории сложности вычислений и теории нумераций. В частности, оно используется для характеризации главных нумераций и вычислимых нумераций с точки зрения их «равномерности».

¶Связь с вычислимыми нумерациями

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

¶Пример

Рассмотрим множество \(K = \{ x \mid \varphi_x(x) \downarrow \}\) — классическое творческое множество (проблема остановки). Оно является рабочим: для любого \(n\) можно эффективно найти число \(f(n)\), которое либо принадлежит \(K\), либо нет, но если принадлежит, то вычисление соответствующей функции требует времени, растущего быстрее любой наперёд заданной вычислимой границы. Это следует из того, что \(K\) неразрешимо и его дополнение не перечислимо.

¶Критика и уточнения

Некоторые исследователи отмечали, что определение рабочего множества зависит от выбора конкретной модели вычислений (машины Тьюринга, рекурсивные функции и т. д.) и от способа измерения времени. В разных моделях класс рабочих множеств может различаться. Поэтому в современной литературе чаще используют инвариантные аналоги, такие как продуктивные множества (в смысле Поста) или творческие множества, которые не зависят от временных ограничений.

¶Источники

• Успенский В. А. «К теории вычислимых операций» // Доклады АН СССР, 1957.
• Роджерс Х. «Теория рекурсивных функций и эффективная вычислимость», 1967.
• Ершов Ю. Л. «Теория нумераций», 1977.