A08DPPMAT_UPS2006D00

Примеры разрешимых множеств. Естественность понятия разрешимого множества не вызывает сомнений. Многие математические задачи формулируются в виде «найти алгоритм для выяснения, является или нет элемент x элементом подмножества A». Рассмотрим следующие примеры.

1) Пусть N — множество всех натуральных чисел, A— множество всех простых чисел. Рассматривая вопрос: «указать алгоритм для определения, является ли число x простым или нет», мы тем самым ставим проблему разрешимости для A в N. Ответ положительный, т.е. множество A разрешимо. В качестве необходимого алгоритма можно взять решето Эратосфена [11, с.17].

2) Пусть E— множество всех формул алгебры высказываний, A— множество всех тождественно истинных формул. Если мы ставим проблему разрешимости для A в E, то мы выясняем наличие алгоритма, с помощью которого для произвольной формулы алгебры высказываний F можно выяснить ее тождественную истинность. Такой алгоритм существует. Это составление таблицы истинности.

Установим некоторые свойства разрешимых множеств.

ПРЕДЛОЖЕНИЕ 13.1. Пусть A — конечное подмножество множества E. Тогда A разрешимо в E.

	Доказательство. Установим разрешимость конечного множества
A	a1, a2, . . . , an с помощью следующего алгоритма A. К элементу
x E применяем n инструкций:
	1. Проверить x	a1,
	2. Проверить x	a2,
	. . .
	n. Проверить x	an.

Для произвольного элемента x E одна из инструкций должна давать на выходе «истина». Каждая из этих инструкций выполнима, т.к. мы умеем для конструктивных объектов x и y за конечное число шагов выявить равенство объектов x и y. Например, определяя равенство двух слов u и v в некотором алфавите, мы последовательно сравниваем первые буквы, вторые буквы и т.д. в словах u и v. За конечное число шагов будет получен ответ x y или x y.

Предложение доказано.

131

ПРЕДЛОЖЕНИЕ 13.2 . Пересечение, объединение и разность разрешимых в E множеств также разрешимы.

Доказательство. Пусть множества A и B разрешимы в E. Проверим, что множество A B разрешимо. Существует алгоритм A1 для ответа на вопрос: «пусть x E, верно ли, что x A или нет». Рассмотрим аналогичный алгоритм A2 для множества B. Искомый алгоритм A3 проверяет вначале, что x A инструкциями алгоритма A1. Затем проверяется истинность утверждения x B инструкциями из A2. В итоге алгоритм A3, содержащий как инструкции из A1, так и инструкции из A2, отвечает на вопрос: «верно или нет утверждение x A B». Остальные утверждения проверить самостоятельно.

Предложение доказано.

Обратим внимание, что в данном доказательстве и в других случаях мы используем тезис Черча для упрощения доказательств. Предположим, что в каком-то случае нам нужно установить, что существует некоторый алгоритм A или что некоторая функция f частично рекурсивна. Можно применить непосредственное определение частичной рекурсивности. Однако при этом, как правило, появятся громоздкие и трудные выкладки. Этого можно избежать следующим способом. Конструируем алгоритм A или функцию f в соответствии с интуитивным представлением об алгоритме и вычислимой функции. Затем применяем тезис Черча и получаем, что функция f частично рекурсивна. Разумеется, для строгости рассуждений мы в любой момент можем заменить такое «неформальное» доказательство на доказательство, устанавливающее частичную рекурсивность функции только на основе определения рекурсивности. В таком случае мы не используем тезис Черча.

Заметим, что общее понятие разрешимости A в E, когда E— множество конструктивных объектов, можно свести к случаю, когда E N, т.е. к случаю, когда A — подмножество во множестве натуральных чисел. Так как E эффективно счетно, то мы можем перенумеровать элементы x множества E натуральными числами g x . Вместо элементов x E в алгоритмических процессах можно использовать их номера g x N. При этом мы располагаем алгоритмом A1, вычисляющим по слову x E его номер g x , и алгоритмом A2, вычисляющим по номеру g x элемент x E. Поэтому при рассмотрении вопросов разрешимости можно ограничиться случаем, когда A — подмножество во множестве N.

132

ПРЕДЛОЖЕНИЕ 13.3. Справедливы следующие утверждения: 1 число разрешимых множеств счетно;

2 существует подмножество множества N, которое не является разрешимым множеством.

Доказательство. 1) Число алгоритмов, а поэтому и число разрешимых подмножеств счетно.

2) Пусть все подмножества в N разрешимы. Тогда по пункту 1) число всех подмножеств в N счетно, что не так. Предложение доказано.

Разрешимые предикаты. Мы рассмотрели понятие разрешимости для множеств. Рассмотрим аналогичные понятия для предикатов. Напомним кратко необходимые сведения о предикатах из вводного курса математики. Пусть задано предложение P x1, x2, . . . , xn , содержащее n переменных, принимающих значения из некоторого множества M . Такое предложение названо n-арным предикатом (высказывательной формой) с областью определения M , если при каждой замене переменных x1, x2, . . . , xn на элементы из M получается высказывание. Обычно n- арный предикат при n 1 называется унарным, а при n 2 — бинарным предикатом.

Пример. Рассмотрим предложение x y 7, которое содержит 2 переменные x и y, принимающие значения из множества натуральных чисел. Это предложение нельзя рассматривать как высказывание, поскольку, не зная конкретного значения переменных x и y, нельзя приписать этому предложению значения «истина» или «ложь». Однако при подстановке вместо переменных x, y элементов из множества M N получается высказывание. Поэтому предложение x y 7 — бинарный предикат с областью определения N.

Укажем другие примеры предикатов.

1.Уравнение x y z 1 является предикатом от трех переменных с областью определения R.

2.Предложение «прямая x параллельна прямой y» — бинарный предикат, определенный на множестве M , где M — множество всех прямых некоторой плоскости.

3.Предложение «x — простое число» является унарным предикатом, определенным на множестве натуральных чисел, больших 1.

133

χ a1, . . . , an

Нам потребуется теперь более строгое определение предикатов на основе теории множеств. Пусть, например, M — множество всех людей, P x, y – бинарный предикат: x знает y. Составим список R следующим образом. Просмотрим все a, b , где a, b M . Если человек a знает b, то пару a, b вносим в список R, если a не знает b, то a, b R. Свойство «знает» полностью характеризуется списком R.

Любой n-арный предикат на множестве M (рассматриваемый как предложение с переменными) может быть подвергнут подобному процессу составления списка R M M . Приходим к следующему определению предиката, которое и будем обычно использовать в данном курсе.

ОПРЕДЕЛЕНИЕ 13.1 . n-арным предикатом, определенным на множестве M , называется некоторое подмножество P в декартовом произведении M n M M .

Наряду с записью a1, . . . , an P для n-арного предиката P применяем также запись P a1, . . . , an , которая выражает мысль, что отношение

P истинно для n-ки a1, . . . , an .

Сформулируем понятие разрешающего метода для предиката. Пусть P — n-арный предикат на множестве A, т.е. P An. Разрешающим методом для предиката P называется такой алгоритм, с помощью которого для произвольной строки a1, . . . , an An можно установить, верно или нет утверждение a1, . . . , a1 P . Если такой алгоритм существует, то предикат P называется разрешимым (рекурсивным).

Учтем, что n-арный предикат на множестве A является подмножеством во множестве An, и рассмотрим характеристическую функцию этого подмножества. Получим характеристическую функцию χ преди-

ката P

1, если P a1, . . . , an ,

0, если (P a1, . . . , an .

Отметим, что функция χ является всюду определенной функцией.

В лекции 11 доказана теорема: подмножество A из E является разрешимым в E тогда и только тогда, когда его представляющая функция χ x является рекурсивной.

Рассмотрим аналогичное утверждение для предикатов и другим способом выразим понятие разрешимости предиката.

134

ПРЕДЛОЖЕНИЕ 13.4 . Предикат P разрешим тогда и только тогда, когда его характеристическая функция χ рекурсивна.

Доказательство. То, что мы нашли разрешающий метод A для функции χ, означает, что посредством A мы умеем вычислять 1 или 0 для произвольной строки a1, . . . , an . Это означает, что для строки a1, . . . , an

выявляется факт P a1, . . . , an или факт (P a1, . . . , an . Поэтому A разрешающий метод для предиката P .

Обратно, если A разрешающий метод для предиката P , то очевидно, что A разрешающий метод для функции χ.

Предложение доказано.

В связи с предложением 13.4 естественно возникают следующие два определения. Пусть A N.

ОПРЕДЕЛЕНИЕ 13.2 . Множество A называется примитивно рекурсивным, если его характеристическая функция χ примитивно рекурсивна.

ОПРЕДЕЛЕНИЕ 13.3. Предикат P называется примитивно рекурсивным, если его характеристическая функция χ примитивно рекурсивна.

135

Упражнения к лекции 13

ЗАДАЧА 1. Показать, что множество A разрешимо в E: 1 A — множество четных натуральных чисел, E N;

2 A — множество пар простых чисел близнецов, E	N2;
3 A — множество квадратов натуральных чисел, E	N.

ЗАДАЧА 2. Пусть множества A и B разрешимы. Доказать, что множество A B разрешимо.

ЗАДАЧА 3. Пусть множества A и B разрешимы. Доказать, что множество A B разрешимо.

ЗАДАЧА 4. Пусть E — множество квадратных матриц порядка n с целыми коэффициентами, A — множество матриц из E, имеющих обратную матрицу. Верно ли, что A разрешимо в E?

ЗАДАЧА 5. Пусть множества A и B отличаются конечным числом элементов. Доказать, что множество A разрешимо тогда и только тогда, когда множество B разрешимо.

ЗАДАЧА 6. Доказать разрешимость следующих предикатов:

1)x — простое число;

2)число x четно;

3)числа x и y взаимно просты.

ЗАДАЧА 7. Пусть предикаты P x1, x2, . . . , xn и Q x1, x2, . . . , xn

разрешимы. Доказать разрешимость предикатов

P x1, x2, . . . , xn" Q x1, x2, . . . , xn и P x1, x2, . . . , xn! Q x1, x2, . . . , xn .

ЗАДАЧА 8. Пусть предикат P x1, x2, . . . , xn разрешим. Доказать разрешимость предиката (P x1, x2, . . . , xn " Q x1, x2, . . . , xn .

ЗАДАЧА 9. Пусть E — бесконечное множество конструктивных объектов. Доказать, что в E существует подмножество A, не являющееся разрешимым подмножеством в E.

ЗАДАЧА 10. Пусть A — подмножество в N, причем дополнение N A конечно. Доказать, что множество A разрешимо.

136

Лекция 14. Перечислимые и диофантовы множества

Порождающие процессы и перечислимые множества Рассмотрим работу произвольного алгоритма A. Мы располагаем некоторым множеством E, состоящим из конструктивных объектов, элементы которого поступают на вход алгоритма A. Так как множество E счетно, то его можно представить в виде

E x0, x1, x2, . . . .

(14.1)

Мы используем алгоритм A для создания элементов некоторого множества A. Это создание осуществляется с помощью следующего порождающего процесса. Берем входной объект x0 и с помощью алгоритма получаем объект на выходе A x0 . Помещаем элемент A x0 во множество A. Затем вычисляем A x1 , A x2 и т.д. Представим себе, что данный процесс завершен. Мы получили множество A, элементы которого входят в последовательность

A x0 , A x1 , A x2 , . . . .

Какие события могут возникнуть в этом процессе? Во - первых, некоторый элемент A xi может не существовать, т.к. алгоритм A не применим к xi. Тогда при вычислении A xi мы не добавим новый элемент к множеству A. Кроме того, возможны повторения, например, A x2 A x3 . По определению множества второй экземпляр A x5 нам учитывать не нужно, т.к. уже имеем, что A x2 A. Поскольку порядок записи элементов множества не важен, то элементы из A могут располагаться в произвольном порядке. В результате множество A не зависит от того, в каком порядке перебирались элементы из E. Про алгоритм A мы говорим, что он

перечисляет множество A. Само множество A называется перечислимым множеством.

Рассмотрим следующий пример. Пусть f x1, x2, . . . , xn — вычислимая функция, и A — алгоритм, вычисляющий эту функцию. На вход A поступают произвольные строки x1, x2, . . . , xn , а множество A, которое возникает в порождающем процессе, есть множество значений функции f

Af x1, x2, . . . , xn x1, x2, . . . , xn Nn .

Можно ограничиться случаем n 1. Действительно, мы можем занумеровать как входные объекты, так и объекты на выходе алгоритма натуральными числами. Рассматривая вместо объектов их номера, мы можем так истолковать описанный выше порождающий процесс: мы имеем

137

некоторую частично рекурсивную функцию f x и создаем множество A, состоящее из всех значений функции f . Тогда A f x x N . Итак, мы получили следующее утверждение.

ПРЕДЛОЖЕНИЕ 14.1 . Множество A N является перечислимым множеством тогда и только тогда, когда A является множеством значений некоторой частично рекурсивной функции

f x1, x2, . . . , xn .

Кроме того, множествоA N перечислимо тогда и только тогда, когда для некоторой частично рекурсивной функции f x выполнено равенство

A f x x N .

(14.2)

Рассмотрим функцию f , не определенную ни для какого значения аргумента (т.е. функцию с пустой областью определения). Она, очевидно, вычислима и, по тезису Черча, частично рекурсивна. Множество ее значений пусто. Следовательно, пустое множество перечислимо.

Рассмотрим отличие понятия разрешимого множества от понятия перечислимого множества. Для этого введем понятия полухарактеристической функции и полуразрешимого множества.

Пусть A E. Наряду с определенной ранее характеристической функцией χ x , введем теперь полухарактеристическую функцию χ x множества A.

ОПРЕДЕЛЕНИЕ 14.1. Полухарактеристической функцией множества A называется функция χ , заданная следующим правилом:

χ x 1,	если x A,	(14.3)
не определено,	если x E A.

Рассмотрим теперь множества, являющиеся разрешимыми только наполовину.

ОПРЕДЕЛЕНИЕ 14.2. Пусть A E. Назовем множество A полуразрешимым в E, если существует алгоритм A, который перерабатывает элементы из E, и такой, что выполнены следующие два условия:

138

1 если на входе алгоритма предъявлен элемент x A, то на выходе должно быть число 1 (можно истолковывать как ответ «да» на вопрос x A);

2 если на входе алгоритма имеется элемент x A (т.е. x E A), то алгоритм работает бесконечно (и поэтому ничего нет на его выходе).

Такой алгоритм A вычисляет значения полухарактеристической функции χ x . Поэтому непосредственно получаем следующее утверждение.

ПРЕДЛОЖЕНИЕ 14.2. Множество A полуразрешимо в E тогда и только тогда, когда его полухарактеристическая функция χ x вычислима.

ТЕОРЕМА 14.1. Пусть A — подмножество множества N. Множество A перечислимо тогда и только тогда, когда оно полуразрешимо.

Доказательство. Пусть множество A перечислимо. Проверим, что оно полуразрешимо. По (14.2) имеем некоторую частично рекурсивную функцию f с условием

A f x x N .

(14.4)

Функция f рекурсивна, т.е. вычисляется некоторым алгоритмом A. Пусть x N. Приспособим этот же алгоритм A для определения факта x A. Возьмем элемент x A. Применим алгоритм A для вычислений чисел

f 0 , f 1 , f 2 . . .

.

(14.5)

Сравниваем по порядку данные элементы с элементом x. Если элемент x A, то x f i для некоторого i. Тогда после конечного числа испытаний обнаружится факт x f i , т.е. факт x A. Поэтому получили следующее.

1)Если на входе алгоритма предъявлен элемент x A, то на выходе получен ответ «да» (который закодируем числом 1).

2)Пусть на входе алгоритма предъявлен элемент x A, т.е. x N A. Тогда мы после конечного числа испытаний никогда не обнаружим факт x A. Пусть мы выполнили m шагов алгоритма. Не обнаружив после m шагов числа i с условием x f i , мы не знаем: или 1) x A, или 2) x A, но мы еще не дошли до обнаружения этого факта. Тем самым

139

после любого конечного числа шагов мы ничего не вносим в прояснение вопроса x A. Наши попытки продолжаются бесконечно и результата на выходе алгоритма нет. Поэтому множество A полуразрешимо.

Обратно, дано, что A — полуразрешимо. Тогда по предложению 14.2 полухарактеристическая функция χ x множества A частично рекурсивна. У нас есть алгоритм A для вычисления функции χ x . Для x A этот алгоритм вырабатывает «да», для x A алгоритм ничего не вырабатывает. Подправим работу алгоритма A. Если x A и алгоритм выработал «да», то заменим ответ «да» на значение аргумента x. Получим алгоритм A1, который вычисляет некоторую функцию f , и множество значений функции f равно множеству A. Получили A — перечислимо, что и нужно.

Теорема доказана.

ТЕОРЕМА 14.2. Существует перечислимое, неразрешимое множество.

Доказательство. По теореме (9.3) существует вычислимая функция f x , которую нельзя продолжить до всюду определенной вычислимой функции. Пусть A — область определения функции f x . Покажем, что A — искомое множество. Так как A — область определения вычислимой функции f x , то A — перечислимое множество (упражнение 3).

Проверим, что A — неразрешимое множество. Предположим противное. Тогда существует алгоритм A, по которому для x N определяем x A или нет. Для получения противоречия достаточно построить всюду определенную функцию g x , которая является продолжение функции f x . Это означает, что для x A имеем g x f x . Для остальных x, т.е. для x N A, функция f x не определена, а функция g x должна иметь некоторое значение. Построим следующий алгоритм A1 для вычисления значений функции g x для всех x N.

Пусть x N. Вначале применяем имеющийся алгоритм A. Его инструкциями определяем, какой случай выполнен: 1) x A или 2) x A.

В случае 1) считаем g a	f a . В случае 2) считаем g a	0. Тогда
g x f x для x A и g x	0 для x N A.

Так как алгоритм A1 вычисляет функцию g x , то функция g x вычислима. Кроме того, функция g x — продолжение функции f x . Противоречие с условием, что функция f x не имеет всюду определенного вычислимого продолжения.

140