A08DPPMAT_UPS2006D00

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

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

ТЕОРЕМА 14.3 (Э.Пост). Множество A разрешимо тогда и только тогда, когда как множество A, так и его дополнение N A перечислимы.

Доказательство. Пусть A N и множество A разрешимо. По определению 11.1 существует алгоритм A, с помощью которого для любого элемента x N можно определить, является или нет данный элемент x элементом множества A.

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

Обратно, предположим, что A и его дополнение N A перечислимы. Тогда существуют алгоритмы A1 и A2, где A1 обладает способностью обнаруживать факт x A, а A2 может обнаруживать факт x A. Соединим вместе инструкции A1 и инструкции алгоритма A2. Получим алгоритм A, с помощью которого для любого элемента x N можно определить, является или нет данный элемент x N элементом множества A. Поэтому множество A разрешимо.

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

Пусть f x1, . . . , xn функция от n аргументов. Множество строк

Γf x1, . . . , xn, y y f x1, . . . , xn

(14.6)

называется графиком функции f . Поскольку Γf Nn 1, то график функции f является n 1-арным предикатом на множестве N.

ТЕОРЕМА 14.4 (о графике). Функция f x1, . . . , xn вычислима тогда и только тогда, когда ее график Γf перечислим в Nn 1.

Доказательство. Обозначим A Γf . Предположим, что функция f x1, . . . , xn вычислима. Установим перечислимость множества A. Для этого укажем порождающий множество A процесс. Так как функция

141

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

x1, . . . , xn, y , где y f x1, . . . , xn . Новый алгоритм A1 порождает A. Поэтому множество A перечислимо.

Обратно, пусть A перечислимо. Тогда A или множество A является областью значений некоторой всюду определенной, вычислимой функции g x (упражнение 4).

Если A , то функция f x1, . . . , xn не определена ни для одного значения и поэтому вычислима.

Если A является областью значений некоторой всюду определенной вычислимой функции g x , то

Ag 0 , g 1 , g 2 , . . . .

Вданной последовательности содержатся все строки x1, . . . , xn, y , где y f x1, . . . , xn , возможно с повторениями.

Укажем алгоритм A для вычисления функции f . Пусть x1, . . . , xn — произвольная строка, поступающая на вход алгоритма A. Вычисляем по очереди элементы g 0 , g 1 , g 2 , . . . с целью обнаружить в этих элемен-

тах на первых n местах строку x1, . . . , xn . Если f x1, . . . , xn существует, то такая строка обнаружится после конечного числа шагов. На ее n 1

месте находится y f x1, . . . , xn . Это выходной объект алгоритма A. Если f x1, . . . , xn не существует, то алгоритм A работает бесконеч-

но и объекта на выходе нет. Поэтому алгоритм A вычисляет функцию

f x1, . . . , xn . Следовательно, функция f вычислима. Теорема доказана.

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

Диофантовы множества. С понятием перечислимого множества тес-

но связано понятие диофантова множества.

ОПРЕДЕЛЕНИЕ 14.3 . Пусть A — подмножество множества N. Множество A называется диофантовым, если существует многочлен f x, y1, . . . , yn с целыми коэффициентами, такой, что для всех x N имеем

x A )y1 N, . . . , )yn N f x, y1, . . . , yn 0.

(14.7)

142

ПРЕДЛОЖЕНИЕ 14.3. Всякое диофантово множество является перечислимым множеством.

Доказательство. Рассмотрим полухарактеристическую функцию χ множества A. Тогда

χ x	1,	если x A,			(14.8)
	не определено,	если x N A.
Проверим ее вычислимость с помощью следующего алгоритма A. Пусть x
элемент из N . Перебираем все строки вида y			, . . . , y Nn и проверяем
		1		n
условие f x, y1, . . . , yn	0.
Строки y1, . . . , yn	можно записать	в виде		последовательности
a0, a1, a2, . . . . Проверку f x, y1, . . . , yn		0 производим по порядку для

строк a0, a1, a2, . . . . Если x A, то за конечное число шагов мы обнаружим этот факт и создадим на выходе A число 1. Если x A, то процесс подбора такой строки бесконечен и нет объекта на выходе A. Поэтому алгоритм A вычисляет полухарактеристическую функцию χ . Тогда функция χ вычислима. Следовательно, множество A является полуразрешимым и поэтому перечислимым множеством.

Предложение доказано. Справедливо обратное утверждение.

ТЕОРЕМА 14.5 (Ю.В.Матиясевич). Пусть A N и A — перечислимое множество. Тогда множество A является диофантовым множеством.

Доказательство этой теоремы содержится в [18] . Рассмотрим следствие из этой теоремы.

ПРЕДЛОЖЕНИЕ 14.4. Пусть A — подмножество множества N. Множество A является перечислимым множеством тогда и только тогда, когда A является множеством неотрицательных значений некоторого многочлена p x1, . . . , xn с целыми коэффициентами, при условии, что переменные x1, . . . , xn пробегают все значения из N.

Доказательство. Пусть A — множество неотрицательных значений целочисленного многочлена p x1, . . . , xn при условии, что переменные пробегают все значения из N.

143

Тогда

x A )y1 N, . . . , )yn N p y1, . . . , yn x.

Как и в предложении 14.3, получаем, что множество A является перечислимым множеством. Обратно, пусть множество A перечислимо. По теореме Ю.В.Матиясевича, множество A является диофантовым. Поэтому существует целочисленный многочлен f x, y1, . . . , yn , для которого

x A )y1 N, . . . , )yn N f x, y1, . . . , yn 0.

Рассмотрим многочлен p x, y1, . . . , yn , задаваемый равенством

p x, y1, . . . , yn x x 1 f x, y1, . . . , yn 2.

(14.9)

Значение многочлена p x, y1, . . . , yn неотрицательно тогда и только тогда, когда f x, y1, . . . , yn 0. В этом случае его значение равно x.

Итак, A — множество неотрицательных значений целочисленного многочлена p x, y1, . . . , yn при условии, что переменные пробегают все значения из N.

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

Пример. Рассмотрим в качестве A множество простых чисел. Множество A разрешимо и тем более перечислимо. Предложение 14.4 обеспечивает возможность получения формулы для простых чисел в виде явного указания некоторого многочлена F . Укажем такой многочлен F a, b, . . . , z [2, с. 43]. Он имеет степень 25 и содержит 26 переменных — все буквы латинского алфавита.

ТЕОРЕМА 14.6. Множество простых чисел совпадает с множеством положительных значений следующего многочлена от 26 переменных при условии, что его переменные пробегают все значения из N:

144

F a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z

k 2

1 wz h j q 2

2n p q z e 2

a2y2 y2 1 x2 2

4

3

a 1

2

1

o

2 2

3

k 2 n 1

2

1

f

2 2

e

2e

16 k 1

a u4 u2a 2

1 n 4dy 2 1 x cu 2 2

ai k 1 l i 2

gk 2g k 1 h j h z 2

16r2y4 a2

1 1 u2 2

p m l a n 1 b 2an 2a n2

2

2n 2

2

z pm pla p2l t 2ap p2 1

q x y a p 1 s 2ap 2a p2

2p 2

2

a2l2

l2 1 m2 2

n l v y 2 .

145

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

ЗАДАЧА 1. Доказать, что множество четных натуральных чисел является перечислимым множеством.

ЗАДАЧА 2. Доказать, что множество всех квадратов натуральных чисел является перечислимым множеством.

ЗАДАЧА 3. Доказать, что множество A перечислимо тогда и только тогда, когда оно является областью определения некоторой вычислимой функции f x .

ЗАДАЧА 4. Доказать, что множество A перечислимо тогда и только тогда, когда A или A является множеством значений некоторой всюду определенной, вычислимой функции f x .

ЗАДАЧА 5. Пусть функция f x1, x2, . . . , xn вычислима и A — множество решений уравнения f x1, x2, . . . , xn 0. Доказать, что множество A перечислимо в Nn.

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

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

ЗАДАЧА 8. Доказать, что множество четных натуральных чисел является диофантовым множеством.

ЗАДАЧА 9. Доказать, что множество всех квадратов натуральных чисел является диофантовым множеством.

ЗАДАЧА 10. Рассмотрим формулу для простых чисел, приведенную в теореме 14.6. Сформулировать необходимые и достаточные условия, наложенные на переменные, для того, чтобы число k 2 являлось простым числом.

146

Список литературы

[1]Барвайз Дж. (ред.). Справочная книга по математической логике. Часть III. Теория рекурсии. - М.: Наука, 1982.

[2]Боро В., Цагир Д., Рольфс Ю., Крафт Х., Янцен Е. Живые числа. Пять экскурсий. - М.: Мир, 1985.

[3]Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.

[4]Ершов Ю.Л., Палютин Е.А. Математическая логика. - М.: Наука, 1987.

[5]Ершов Ю.Л. Теория нумераций. - М.: Наука, 1977.

[6]Верещагин Н.К., Шень А. Вычислимые функции. - М.: МЦНМО, 1999.

[7]Гуц А.К. Математическая логика и теория алгоритмов. - Омск.: Омский ун-т, 2003.

[8]Игошин В.И. Математическая логика и теория алгоритмов - М.: Академия, 2004.

[9]Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. - М.: Академия, 2005.

[10]Ильиных А.П. Математическая логика: - Екатеринбург.: Уральский гос. пед. ун-т. 2002.

[11]Ильиных А.П. Теория чисел: - Екатеринбург.: Уральский гос. пед. ун-т. 2003.

[12]Ильиных А.П. Числовые системы: - Екатеринбург.: Уральский гос. пед. ун-т. 2003.

[13]Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. - М.: Мир, 1983.

[14]Кушнер Б.А. Лекции по конструктивному математическому анализу. - М.: Наука, 1973.

[15]Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, 3-е изд. - М.: Физматлит, 1995.

147

[16]Мальцев А. И. Алгоритмы и рекурсивные функции. - М.: Наука, 1986.

[17]М а р к о в А. А., Нагорный Н.М. Теория алгорифмов. - М.: Наука, 1984.

[18]Матиясевич Ю. В. Десятая проблема Гильберта. - М.: Физматлит, 1993.

[19]Петер Р. Рекурсивные функции. - М.: ИЛ, 1954.

[20]Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972.

[21]Успенский В.А. Лекции о вычислимых функциях. - М.: Физматгиз, 1960.

[22]Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. - М.: Наука, 1987.

[23]Черч А. Введение в математическую логику. - М.: ИЛ, 1960.

[24]Шенфилд Дж. Математическая логика. - М.: Наука, 1975.

[25]Эббинхауз Г.Д., Якобс К., Ман Ф.К., Хермес Г. Машины Тьюринга и рекурсивные функции. - М.: Мир, 1972.

148

УЧЕБНОЕ ИЗДАНИЕ

Ильиных Анатолий Петрович

Теория алгоритмов

Учебное пособие

Компьютерная верстка: А.П.Ильиных Редактор Т.В.Васильева

Подписано в печать 18.06.2006. Формат 60 84 1 16. Бумага для множ. аппаратов.

Печать ротапринтная. Усл. печ. л. 0,0. Уч.- изд. л. 0,0. Тираж 200 экз. Заказ

Оригинал макет отпечатан в отделе множительной техники Уральского государственного педагогического университета 620219 Екатеринбург, ГСП-135, пр. Космонавтов, 26

149