ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ_учит

0 1 1 1 0 1ый шаг

	q2					2ой шаг
0 1		1 1 0
			q2			3ий шаг
0 1		1 1 0
				q2		4ый шаг
0	1		1	1	0
						q2
0	1		1	1	0	5ый шаг

q3

Составим машинную таблицу:

	q1	q2	q3
0	0пq2	0лq3	0нq0
1	–	1пq2	0лq3

0 1 1 0 0

q3

0 1 0 0 0

q3

0 0 0 0 0

q3

0 0 0 0 0

q0

6ой шаг

7ой шаг

8ой шаг

9ый шаг

2). Построить машину Тьюринга, вычисляющую функ-

цию: f(х)=x+1.
1)							5)
	0		1	1	0			0	1	1	1
	q1			x						q3
														q1	q2	q3
													0	0пq2	1лq3	0нq0
4)	0	1		1	0		8)
													1	–	1пq2	1лq3
								0	1	1	1
					q2			q0
		3). Построить машину Тьюринга, вычисляющую функ-
цию:							0, x 1;
			f x x 1
							x 1, x 1.
													99

1)								начало			7)
	0	1	1	1	0								0			1		1		0
2)	q1		x								8)								q5
	0	1	1	1	0								0			1		1		0
3)		q2									9)						q5
	0	1	1	1	0								0			1		1		0
			q3	…	q3									q5
6)											10)
															0		1		1		0
	0	1	1	1	0
				q4												q0
Составим машинную таблицу:
								q1	q2		q3					q4					q5
						0		0пq2	0лq5	0лq4						–				0нq0
						1		–	1пq3	1пq3				0лq5						1лq5

Операции с машинами

При построении (МТ) можно их комбинировать:

I.Произведение (МТ) (композиция (МТ)). Пусть даны 2 машины Тьюринга М1 и М2. Для построения композиции М= М1 М2 требуется:

1)отождествить стоп-состояние М1 с начальным состоянием М2;

2)состояния М2 переобозначить: qi+1 машины М2 обозначить через qm+i+1 (1 i+1 k, q0, q1, …, qm – состояния машины М1, q0, q1, …, qk – состояния М2);

3)соединить полученные программы М1 и М2.

Если М=М1 М1 … М1, то будем писать М=М1n.

nраз

II.Разветвления. Иногда заключительную ленты машины М1 предъявляют как начальную ленту некоторой машины М2 только в случае выполнения некоторого условия. Если дан-

100

ное условие не выполняется, то стоп-состояние машины М1 предъявляют как начальную ленту некоторой машины М3. Будем считать при этом, что у М1 имеется 2 стоп-

состояния q0 и q0 . Если М1 в какой-то момент приходит в состояние q0 , то начинает работать машина М2, если в q0 , то машина М3. Имея программы машин М1, М2, М3, легко построить программу машины М, которую будем называть разветв-

M2

лением М1 на М2 и М3 и обозначать: M M1

M3.

III.Разветвление с циклом. Пусть мы имеем некоторое разветвление М1 на М2 и М3 и дополнительное условие, что если машина М2 закончит работу, то ее результат надо подать как начальную ленту снова машине М1. Таким образом устроенную машину М будем называть разветвлением М1

		M 2
на М2 и М3 с циклом и обозначать M M1
		M3.
	M3		M 4
Пример: работа машины M M1 M 2						(•, -
			M		M 7
	M	5		6
			M8

обозначение цикла) описывается следующим образом: начинает М1; продолжает М2; если М2 придет в стоп-состояние q0 , то начинает работать М3, затем М4, ее результат снова подается на М2 и т.д.; если М2 придет в состояние q0 , то начинает работать М5; если М5 придет в стоп-состояние q0 , то начинает работать М6, затем М7, ее результат снова подается на М5 и т.д.; если М5 придет в стоп-состояние q0 , то начинает работать М8,ее результат является заключительным для М.

Эти операции над машинами Тьюринга позволяют из очень простых машин строить сложные.

Тезис Тьюринга–Черча. Определение алгоритма

Тезис. Всякий алгоритм реализуется на подходящей М.Т.

101

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

вфизике.

Впользу тезиса можно привести следующие доводы:

1)Все известные алгоритмы реализуются на подходящих МТ (это проверено). Это создает надежду. Что и алгоритмы будущего тоже могут быть реализованы на МТ.

2)Попытки построить алгоритм, который не реализовался бы на МТ, оказались неудачными.

3)Различные определения алгоритма, сформулированные

в30х г.г., оказались равносильными.

Тезис Т-Ч содержит в себе определение алгоритма. Понятие алгоритма отождествляется с машиной Тьюринга.

Гёделевская нумерация машин Тьюринга

Гёдель составил алгоритм, который любой МТ сопоставляет ее номер (МТ NMT) следующим образом. Занумеруем все машины Тьюринга так, чтобы по номеру машины можно было воссоздать саму машину. В основу такой нумерации можно положить основную теорему арифметики:

внешний алфавит: N(0)=1 номер первого символа; N(1)=2 номер второго символа;

сдвиги: N(л)=3; N(н)=4; N(п)=5;

внутренний алфавит: N(q0)=6; N(q1)=8; N(q2)=10;

…

N(qm)=2m+6;

102

команды: saqb sczqd – общий вид команды.

Поставим ей в соответствие число:

2N sa 3N qb 5N sc 7N z 11N qd .

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

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

Пример: Пусть МТ задана системой команд:

команды	номера команд
0q1 0пq2	21 38 51 75 1110 N1
0q2 1пq2	21 310 52 75 1110 N2
1q2 1пq2	22 310 52 75 1110 N3.

Пусть командам уже присвоены номера N1, N2, …, Nk. Тогда самой МТ поставим в соответствие номер, вычисляемый

по формуле: p1N1 p2N2 p3N3 ... pkNk , где р1, р2, …, рk – последовательные простые числа.

В примере: NMT 2N1 3N2 5N3 .

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

Неразрешимость проблемы самоприменимости машины Тьюринга.

Опр. МТ называется самоприменимой, если она, начиная работу со стандартного восприятия своего собственного номера на ленте, через конечное число шагов останавливается. Если МТ не останавливается, то она называется неса-

моприменимой.

103

0 1 1 … 1 0

q1 NMT

Любая МТ либо самоприменима, либо несамоприменима. Проблема самоприменимости МТ состоит в построении алгоритма, позволяющего по номеру МТ определить самопри-

менима она или нет.

ТТьюринга. Проблема самоприменимости МТ алгоритмически неразрешима.

Т.е. искомого алгоритма не существует.

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

1)Допустим, что он бреет сам себя. Тогда по условию он не должен себя брить.

2)Пусть он не бреет сам себя, тогда по условию он должен себя брить.

Вывод: такого парикмахера не существует. Почему не существует? Точного ответа нет. Доказательство теоремы: (от противного).

Пусть искомый алгоритм существует. Тогда по тезису Тьюринга-Черча существует МТ (обозн. М), реализующая этот алгоритм. Эта машина М должна обладать свойствами:

1)Если на ленте машины М номер самоприменимой машины, то М через конечное число шагов останавливается, печатая символ самоприменимости, например «1».

2)Если на ленте М – номер несамоприменимой машины, то М через конечное число шагов останавливается, печатая на ленте «0» – признак несамоприменимости.

По машине М построим вспомогательную машину Тью-

~
ринга M следующим образом. Среди команд МТ М имеется
команда вида:	1нq0 (	– что угодно), которая означа-

104

ет, что машина М самоприменима. Заменим эту команду на

1нq , где q – новое внутреннее состояние, не встречавшееся в М. Далее приписываем еще две команды:

0q 0пq ;

1q 1пq .

~

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

~

1*) Если на ленте M – номер самоприменимой машины,

~

то M не останавливается;

~

2*) – свойство такое же, как у М: если на ленте M номер

~

несамоприменимой машины, то M останавливается.

~

Поставим вопрос: самоприменима ли машина M ?

~

Пусть на ленте M ее собственный номер.

~

1) Предположим, что M самоприенима. Тогда, начиная работу со своего собственного номера, она по свойству 1*) не останавливается, это означает, по определению, что она несамоприменима.

~

2) Пусть M – несамоприменима, тогда, начиная работу со своего собственного номера по свойству 2*) она останавливается, что значит, по определению, что она самоприменима.

~

В обоих случаях получаем противоречие: значит M – не существует, а следовательно не существует М и не существует искомого алгоритма.

Пример перечислимого, но неразрешимого множества

Пусть А – подмножество N0={0, 1, 2,…}.

Опр. Подмножество А множества N0 называется разрешимым, если существует алгоритм, позволяющий по любому числу определить, принадлежит ли это число подмножеству или нет.

Например: {2n |n N0} – разрешимо.

Опр. Подмножество А множества N0 называется перечислимым, если существует алгоритм, перечисляющий эле-

105

менты этого подмножества (множество может быть с повторениями).

ТПОСТА. Если множество А разрешимо, то оно само и его дополнение перечислимо (т.е. из существования разрешающего алгоритма следует существование перечисляющего алгоритма).

Доказательство: Пусть А – разрешимо, докажем, что А – перечислимо. Берем любое число n (начиная с 0), применим к нему разрешающий алгоритм. Если число принадлежит А, то включаем его в перечисляющий список, если нет, то переходим к следующему числу n+1 и т.д. В результате, если n A, то мы это узнаем на некотором конечном шаге работы алгоритма. (Обратное неверно), т.е. справедлива теорема:

Т(Клини, Пост, Гёдель, Тьюринг, Черч, Марков и др.). Существует перечислимое

множество, не являющееся разрешимым. Доказательство: Примером такого множества служит множе-

ство В – номеров самоприменимых машин Тьюринга. В={NMT N NMT – номер самоприменимой машины}.

В не является разрешимым, иначе была бы разрешима проблема самоприменимости.

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

Если какая-либо машина остановилась, то номер этой машины включаем в список перечислений элементов В. Ясно, что каждый элемент множества В может быть получен на некотором конечном шаге.

такты работы M	1	2	3	4	5	6	7	8	9
NМТ
N1	1	2	6	7	15	16
N2	3	5	8	14	17
N3	4	9	13	18
N4	10	12	19
N5	11	20
N6	21

106

N1 – наименьший номер МТ; N2 – следующий за ним.

Эта таблица и есть перечисляющий алгоритм.

Порядок запуска МТ таков: сначала выполняется первый такт с N1, потом второй такт (по стрелкам).

Если на каком-то такте машина Тьюринга прекращает работу, то будем считать этот такт пустым.

107

Нормальные алгоритмы Маркова

В конце 40-х г.г. А.А. Марков предложил алгоритмическую схему, в которой, как и в машине Тьюринга, преобразуются слова в каком-то алфавите, но на основе других принципов. Алфавитом называется любое непустое множество «букв», а любые последовательности букв – словами в данном алфавите. В алгоритмической схеме Маркова нет понятия ленты и подразумевается непосредственный доступ к различным частям преобразуемого слова. А.А. Марков назвал эту алгоритмическую схему «нормальным алгорифмом».

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

P1 Q1

P2 Q2

……….

Pn Qn

Вместо символа должна быть записана одна из стрелокили : P Q – формула подстановки; P Q – формула завершающей или заключительной подстановки.

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

Каждая пара представляет собой формулу подстановки для замены подслов в преобразуемом слове.

Выполнение нормального алгоритма распадается на такты. Каждый такт включает в себя поиск первой по порядку применимой формулы подстановки и применение этой формулы. Первый такт начинается с проверки, является ли слово P1 частью входного слова. Иначе говоря, ищется вхождение слова P1 в исходное слово. Например, в слове ТОВАР есть вхождение слова ТО (но нет вхождения слова ТК, так как буквы вхождения должны располагаться подряд). Если вхождение имеется, то оно заменяется на правую часть пары, т. е. на слово Q1. Таким образом, производится изменение входного слова путем подстановки вместо одного подслова другого полслова. На

108