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

Еще одним видом стандартных объектов, к которым применяются алгоритмы, являются разрешимые множества.

Будем рассматривать упорядоченные наборы натуральных чисел , где x_i определены на подмножествах M_i множества натуральных чисел N. Как и раньше, обозначим

, .

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

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

Приведем примеры разрешимых множеств.

Пример 1.2.6 Множество четных натуральных чисел.

Алгоритм проверки (в десятичной кодировке): если последняя цифра числа четная (0, 2, 4, 6, 8) – то и само число – четное.

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

Приведем алгоритм, разрешающий это множество. Он основан на алгоритме из примера 1.2.4.

Шаг 1. Вводится число x.

Шаг 2. Числу i присваивается значение 0.

Шаг 3. Вычисляется число y = i².

Шаг 4. Проверяется условие «y < x». Если условие истинно, то числу i присваивается значение i+1 и выполняется переход к Шагу 3, иначе выполняется переход к Шагу 5.

Шаг 5. Проверяется условие «y = x». Если условие выполнено, то записывается результат: «число x – полный квадрат». Если условие не выполнено, то записывается результат: «число x – не является полным квадратом».

Следующий пример – множество, состоящее из упорядоченных наборов трех натуральных чисел.

Пример 1.2.8 Множество пифагоровых троек .

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

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

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

Характеристической функцией множества называется функция , такая что

Для разрешимых множеств выполняется следующая очевидная теорема.

Теорема 1.2.1

Множество M разрешимо тогда и только тогда, когда его характеристическая функция – тотальная вычислимая.

Помимо разрешимых множеств часто рассматриваются так называемые перечислимые множества, которые часто называют графиками вычислимых функций.

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

Множество называется перечислимым, если все его элементы являются значениями некоторой вычислимой функции и все значения этой функции принадлежат множеству M.

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

Приведем примеры перечислимых множеств.

Пример 1.2.9 Множество чисел, кратных натуральному числу n₀.

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

Естественно рассмотреть связь между перечислимыми и разрешимыми множествами. Эта связь выражается следующей теоремой.

Теорема 1.2.2

Множество является разрешимым тогда и только тогда, когда оно само и его дополнение до N – перечислимы.

Как следует из теоремы – перечислимость и разрешимость – не эквивалентные свойства множеств. Приведем пример перечислимого, но не разрешимого множества.

Пример 1.2.10

Пусть M₀, …, M_n, … – эффективное перечисление всех перечислимых множеств, то есть такое перечисление, что по любому заданному числу r можно восстановить само множество M_r. Рассмотрим теперь алгоритм , который последовательно порождает все элементы следующего множества U: на шаге с номером C(m,n) этот алгоритм вычисляет m-тый элемент множества M_n, и если этот элемент совпадает с n, то он относит его к множеству U:

.

Таким образом, множество U порождается с помощью алгоритма . С другой стороны, дополнение этого множества состоит из всех таких n, что . Поэтому оно отличается от любого другого перечислимого множества по крайней мере одним элементом. Значит, оно не перечислимо, так как не вошло в список M₀, …, M_n, …. Но тогда, согласно теореме 1.2.2, множество U неразрешимо.

Более подробно примеры неразрешимых множеств и невычислимых функций будут рассмотрены во второй главе.