A08DPPMAT_UPS2006D00

A 0, , Æ, a, b . Как и в случае сложения, натуральное число x изображается x палочками с предшествующим символом 0. Буква Æ служит как знак умножения. Буквы a и b — дополнительные символы.

Рассмотрим нормальный алгорифм A, имеющий следующую схему:

a	ba		(1)
a			(2)
b	b		(3)
Æ 0	Æ 0 a		(4)
00		0	(5)
Æ 0		0 Æ	(6)
Æ		Æ	(7)
Æ b Æ			(8)
Æ			(9)

Пусть нужно вычислить произведение чисел x и y. Подаем на вход алгорифма слово P , равное 0 . . . Æ0 . . . . Нужно проверить, что на вы-

x y

ходе алгорифма получится слово 0 . . . — изображение числа xy. Разо-

xy

бьем решение на три случая.
ЗАДАЧА 8. Случай 1. Пусть x 0, т.е.
P 0 Æ 0 . . .	(10.11)
y

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

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

101

Номер	Вход	Активная формула	Выход
шага
1	P 0 Æ 0 . . .	Æ 0 0 Æ	P1 00 Æ . . .

		y				y
2	P1	00 Æ . . .		00 0	P2	0 Æ . . .
		y				y
3	P2	0 Æ . . .		Æ Æ	P3	0 Æ . . .
		y				y 1
. . . . . .				. . .	. . .
	0Æ			Æ	0

ЗАДАЧА 9. Случай 2, x 0 и y 0. Тогда
P 0 . . . Æ0 .	(10.12)
x

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

Номер	Вход			Активная формула	Выход
шага
1	P	0 . . . Æ0		Æ 0 Æ 0 a	P1	0 . . . Æ 0 a
		x				x 1
2	P1	0 . . . Æ 0 a		a	P2	0 . . . Æ 0
		x 1				x 1
. . .	. . .			. . .	. . .
. . .	0 Æ 0			Æ 0 0 Æ	0 0 Æ
. . .	0 0 Æ			0 0 0	0 Æ
. . .	0 Æ			Æ	0
ЗАДАЧА 10. Случай 3, x 0 и y 0. Тогда
		P	0 . . . Æ0 . . . .			(10.13)
				x y

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

102

Номер	Вход			Активная форму-	Выход
шага				ла
1	P 0 . . . Æ0 . . .			Æ 0 Æ0a	P1 0 . . . Æ 0 a . . .
	x y				x 1		y
2	P1 0 . . . Æ 0 a . . .			a b a	0 . . . Æ 0 b a . . .
		x 1	y		x 1		y 1
. . .	. . .			. . .	. . .
. . .	0 . . . Æ 0 b . . . b a			a	0 . . . Æ 0 b . . . b
	x 1	y			x 1	y
. . .	0 . . . Æ 0 b . . . b			b b	0 . . . Æ 0 b b b . . . b
	x 1	y			x 1		y 2
. . .	. . .			. . .	. . .
1	0 . . . Æ 0 . . . b . . . b			Æ 0 Æ0a	0 . . . Æ 0a . . . b . . . b
	x 1	y y			x 2	y y
					В 1 новый проход
					буквы a такой же, как
					в строке 1. Он породит
					из y символов y
					символов и y симво-
					лов b. Такие проходы
					закончатся,		когда
					исчерпаются		палочки
					первого сомножителя.
. . .	. . .			. . .	. . .
. . .	0 Æ 0 . . . b . . . b			Æ0 0Æ	00 Æ . . . b . . . b
	y xy				y xy
. . .	00 Æ . . . b . . . b			00 0	0 Æ . . . b . . . b
	y xy				y xy
. . .	0 Æ . . . b . . . b			Æ Æ	0 Æ . . . b . . . b
	y xy				y 1 xy
. . .	. . .			. . .	. . .
. . .	0 Æ b . . . b			Æb Æ	0 Æ b . . . b
	xy				xy 1
. . .	. . .			. . .	. . .
. . .	0 . . . Æ			Æ	0 . . .
	xy				xy

103

Лекция 11. Неразрешимые алгоритмические проблемы

Различные виды проблемы разрешения. Проблема построения алгоритма, обладающего теми или иными свойствами, называется алгоритмической проблемой. Мы получим решение алгоритмической проблемы, если будет сделано следующее: 1) найден искомый алгоритм (т.е. представлено его описание) или 2) доказано, что такого алгоритма не существует. Следующий рисунок изображает постановку проблемы и два возможных варианта ответа.

Алгоритмической проблема. Нужно найти алгоритм A, такой что . . .

Алгоритм A найден.		Теорема. Искомого алгоритма A не
Он имеет вид . . .		существует.

Взависимости о того, с какими конкретно объектами мы оперируем

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

Проблемы разрешения для множеств. Пусть E — некоторое множество конструктивных объектов и A — подмножество множества E.

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

Тем самым алгоритм A должен получать на входе произвольный элемент x из E, а на выходе вырабатывать «да» для элементов x из A и вырабатывать «нет» для элементов x из E A. Если искомый алгоритм A существует, то множество A называется разрешимым в E. Подробно понятие разрешимого множества изучается в лекции 13.

Сформулируем аналогичные понятия для функций. Пусть f — произвольная частичная функция. Как всегда, слово функция означает произвольную n-арную частичную функцию, определенную на множестве N и со значениями во множестве N.

104

ОПРЕДЕЛЕНИЕ 11.2. Разрешающим методом для функции f называется такой метод (алгоритм), с помощью которого вычисляется функция f .

Как всегда, слова «алгоритм A вычисляет функцию f x1, x2, . . . , xn » означают следующее:

1) если на входе алгоритма имеется набор аргументов x1, x2, . . . , xn из области определения функции f , то алгоритм A останавливается и выдает

результат f x1, x2, . . . , xn ;

2) если на вход алгоритма поступает набор аргументов вне области определения функции f , то или алгоритм A работает бесконечно, или алгоритм останавливается без выдачи результата.

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

χ x 1, если x A,0, если x A.

ТЕОРЕМА 11.1. Подмножество A из E является разрешимым в E тогда и только тогда, когда его представляющая функция χ x является рекурсивной.

Доказательство. Множество A разрешимо тогда и только тогда, когда имеется алгоритм A, умеющий определять для x E, что верно из следующих двух условий: 1) x A или 2 ) x A. Это означает, что алгоритм A умеет вычислять значение представляющей функции χ x . Поэтому A разрешимо функция χ x вычислима. С учетом тезиса Черча получаем

Aразрешимо функция χ x рекурсивна. Предложение доказано.

Проблема разрешения для формальных систем. Другой вид проблемы разрешения связан с формальными системами.

105

Приведем определение формальной системы (исчисления). Наряду с понятием алгоритма, понятие формальной системы является одним из основных понятий теории алгоритмов и математической логики [22, с.44], [24, с.13].

Первая часть формальной системы F — ее язык. Чтобы определить язык формальной системы, нужно задать символы этого языка и его формулы. Символы формальной системы могут быть произвольными знаками, например, знаками &, , . Задавая символы, мы получаем алфавит A формальной системы F . Слова в этом алфавите будем называть также выражениями этого языка. Не все выражения в естественном языке являются осмысленными словами. Точно так же в формальной системе лишь часть выражений считается формулами. В каждой формальной системе свои правила образования формул.

Вторая часть формальной системы — аксиомы. Задать аксиомы — означает выделить некоторые формулы формальной системы, присвоив им название аксиомы.

Третья часть формальной системы — правила вывода. Они имеют вид

	A1, A2, . . . , An	,	(11.1)
	B

где A1, A2, . . . , An и B — формулы формальной теории. При этом формулы A1, A2, . . . , An называются посылками, а формула B называется заключением правила вывода.

Правила вывода указывают способ для получения теорем (выводимых формул). Вначале все аксиомы объявляются теоремами. Из этого начального списка теорем получаются новые теоремы с помощью правил вывода. Если уже установлено, что A1, A2, . . . , An — теоремы, и имеется правило вывода с посылками A1, A2, . . . , An, то его заключение B добавляется в список теорем. Получаем следующее определение теоремы формальной системы.

1.Любая аксиома формальной системы F является ее теоремой.

2.Если A1, A2, . . . , An — теоремы и (11.1 ) — правило вывода, то B — теорема.

3.То, что формула A является теоремой, устанавливается несколькими применениями правил 1 и 2.

106

Понятие формальной системы непосредственно связано с аксиоматическим методом в математике. Три части формальной системы отражают следующие три требования, предъявляемые к аксиоматическому построению какой-либо математической теории T , например, теории групп.

1)Нам нужно прежде всего создать язык теории T : символы, формулы

ит.п., для того чтобы выражать наши мысли про объекты теории.

2)При построении аксиоматической теории некоторые утверждения про ее объекты принимаются без доказательства. Они называются аксиомами теории. Поэтому мы должны задать аксиомы теории T , выделив их среди всех формул теории.

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

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

В противоположность этой ситуации при формализованном изложении теории список правил вывода фиксирован и четко задан. Тем самым процесс доказательства механизируется и может, например, осуществляться компьютером. Такая ситуация соответствует замыслам немецкого философа и математика Г. Лейбница (1646 – 1716) построить универсальный язык для доказательств и «замены идей вычислениями». Более конкретно эта идея отражена в программе Гильберта, где в определенной мере выражена вера в то, что процесс вывода теорем формальной теории F может быть механизирован.

Имея формальную систему, можно поставить следующую естественную задачу. Найти алгоритм A, с помощью которого для любой наперед заданной формулы A из F можно выяснить, является ли формула A теоремой формальной системы F .

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

107

Поставив задачу о нахождении алгоритма A, мы получаем проблему разрешения для формальной системы.

Заметим, что понятие формальной системы является достаточно широким понятием и может применяться в вопросах, не связанных с аксиоматическим методом. Действительно, в наиболее общем понимании формальной системы мы имеем A — набор исходных элементов в некотором множестве X. Правила вывода трактуем как способы построения новых элементов из исходных элементов и ранее построенных элементов. В итоге возникает множество B X, которое состоит из всех построенных таким способом элементов. Таким образом рассматривается, например, раздел математической логики «исчисление высказываний».

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

Пусть P множество всех программ для МНР. В лекции 8 мы осуществили следующую нумерацию элементов множества P:

P0, P1, P2, . . . .

(11.2)

Каждая программа P P имеет некоторый номер a, обозначена через Pa и ровно один раз входит в данную последовательность.

Затем для каждого n произведена нумерация множества вычислимых n-арных функций. Зафиксировав натуральное число n, каждой программе Pa мы сопоставили функцию φna от n аргументов, которую вычисляет машина Ma с программой Pa. В результате получили перечисление всех вычислимых n-арных функций

φ0, φ1, φ2, . . . ,

(11.3)

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

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

108

номера. Номерами функций являются натуральные числа — конструктивные объекты. Поэтому возникает идея описывать свойства функций, используя их номера. Приведем список проблем, естественным образом возникающих в связи с данной идеей.

1.Даны номера x и y функций φx и φy из (11.3). Найти алгоритм, который по номерам x и y определяет равенство функций φx и φy .

2.Найти алгоритм, который по номеру x определяет, является ли функция φx постоянной функцией.

3.Найти алгоритм, который по номеру x определяет, будет ли бесконечным множество значений функции φx.

4.Найти алгоритм, который по номерам x и y определяет, входит ли число y в область значений функции φx.

5. Найти алгоритм, который по числам x, y, z определяет равенство

φx y z.

6.Найти алгоритм, который по номеру x определяет, будет ли функция φx всюду определенной функцией.

7.Найти алгоритм для определения включения x Dx.

Рассмотрим ответы на некоторые из сформулированных проблем. Более подробные сведения в [20, с. 54].

Проблема «функция f(x) всюду определена». Пусть n 1. В последовательности всех вычислимых унарных функций (11.3) встречаются как всюду определенные функции φx, так и частичные функции φx, у которых область определения не равна N. Рассмотрим следующую алгоритмическую проблему.

Найти алгоритм A, который по номеру x распознает, что данная функция φx всюду определена.

ТЕОРЕМА 11.2. Проблема распознавания всюду определенности функции φx по ее номеру x алгоритмически неразрешима.

Доказательство. Предположим противное. Тогда существует алгоритм A, который для любого x N выясняет: верно или нет, что функция φx всюду определена. Рассмотрим новый алгоритм B. Вначале алгоритм

109

B с помощью инструкций из A для x N выясняет: верно или нет, что функция φx всюду определена. Затем с помощью следующих дополнительных инструкций алгоритм B задает правило для вычисления новой функции f x . При этом

f x φx x 1,	если φx всюду определена,		(11.4)
0,	если φx не всюду определена.
В этих, состоящих из конечного числа дополнительных инструкциях нуж-
но уметь вычислять число φx x . Однако φx x		U x, x	d x , где

d x — диагональная функция, которая вычислима по свойству 1 диагональная функции (лекция 9, с. 84).

Итак, функция f x вычислима и всюду определена. Так как f x вычислима, то функция f x имеет некоторый номер a при нумерации унарных функций. Тогда f x — функция φa и φa всюду определена. Отсюда

f a φa a . Однако по (11.4) f a φa a 1 (мы взяли x a и учли,что функция φa всюду определена). Имеем φa a φa a 1, противоречие.

Поэтому алгоритма A не существует.

Теорема доказана.
Рассмотрим нумерацию вычислимых функций из (11.3) при n			1
φ0,	φ1,	φ2, . . . .	(11.5)
Области определения этих функций обозначим соответственно через
D0,	D1,	D2, . . . .	(11.6)

Рассмотрим следующий вопрос.

Проблема x Dx. Найти алгоритм A, который отвечает на следующий вопрос. Для каких x N верно условие x Dx?

Очевидно, что выяснение следующих условий 1)-3) фактически одно и то же.

1)При каких x N верно x Dx?

2)Для каких чисел x определено число φx x ?

3)При каких числах x МНР с программой Px останавливается, имея на входе x?

110