matlogta

18.Пусть T теория плотных линейных порядков. Показать, что T имеет ровно четыре полных расширения сигнатуры f·g.

19.Пусть T теория константной сигнатуры fcn j n 2 !g. Показать, что T допускает элиминацию кванторов.

20.Описать теории сигнатуры fEg одного отношения эквивалентности. Найти все возможные функции спектра для этих теорий.

21.Определить интерпретации сигнатурных символов теории арифметики Пеано так, чтобы моделью теории TP стала система с носителем:

(à) N [ fag, ãäå a 62N; (á) N [ fa; bg, ãäå a; b 62N;

(â) N [ fan j n 2 !g, ãäå an 62N äëÿ âñåõ n 2 !.

После изучения главы 2 выполняются задачи 2 6 контрольной работы. Задача 2 решается аналогично примеру 2.1.7, задача 3 аналогично примеру 2.2.2, п.2, задача 4 аналогично примеру 2.2.2, пп.4, 5, задача 5 аналогично примерам 2.4.1 и 2.7.3, а задача 6 аналогично примерам 2.8.12 2.8.14.

à ë à â à 3

ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ

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

Отметим несколько основных общих черт алгоритмов.

1. Алгоритм это процесс последовательного построения (вычисления) величин, протекающий в дискретном времени так, что в на- чальный момент времени задается исходная конечная система вели- чин, а в каждый последующий момент система величин получается по определенному закону (программе) из системы величин, имевшихся в предыдущий момент времени (дискретность алгоритма).

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

3. Закон получения последующей системы величин из предшествующей должен быть простым (элементарность шагов алгоритма).

4. Если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указано, чтo надо считать результатом алгоритма (направленность алгоритма).

5. Алгоритм должен быть пригоден для решения всех задач из заданного класса (массовость алгоритма).

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

82

В 20-х 30-х годах двадцатого века предпринимались попытки формализовать понятие алгоритма. В результате было предложено несколько моделей алгоритмов (машины Поста и Тьюринга, рекурсивные функции, нормальные алгорифмы Маркова (1954 г.) и др.). Впоследствии было установлено, что классы решаемых ими задач совпадают, и на основании этого появился тезис о моделях алгоритмов, опубликованный впервые Черчем в 1936 г. для класса рекурсивных функций и носящий его имя в следующем современном виде.

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

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

Любое вычисление по алгоритму A можно представить в виде функ- öèè fA : X ! N, ãäå X µ Nn, такой, что для любых числовых данных (x1; : : : ; xn) 2 X значение fA(x1; : : : ; xn) совпадает с результатом

A(x1; : : : :xn) работы алгоритма A на данных x1; : : : ; xn. Таким обра- зом, в классе всех функций f : X ! N, ãäå X µ Nn, выделяется под-

класс вычислимых функций, т.е функций вида fA. Тем самым тезис Черча утверждает, что совпадают классы вычислимых и рекурсивных функций.

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

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

Ÿ 3.1. Машины Тьюринга

1. Определение и примеры. Машина Тьюринга T представляет собой систему, работающую в дискретные моменты времени t = 0; 1; 2; : : : и состоящую из следующих частей (рис. 3.1).

1.Конечная лента, разбитая на конечное число ячеек. При этом

âкаждый момент времени t в ячейках записаны буквы из некоторого

алфавита A = fa0; a1; : : : ; amg (ãäå a0 = 0, a1 = 1, m ¸ 1), называемого внешним алфавитом машины. Ячейка, в которой записан символ 0, называется пустой. В процессе работы машины каждая ячейка

может менять свое состояние путем замены приписанного к ней сим-

83

@qj¡ @¡

ai

Ðèñ. 3.1

âîëà ai на другой символ al 2 A. К существующим ячейкам можно пристраивать неограниченное число дополнительных ячеек, которые изначально считаются пустыми. Лента считается направленной, и ее ячейки будут просматриваться слева направо. Таким образом, если в какой-то момент времени лента имеет r ячеек, то состояние ленты

полностью описывается словом ai1ai2 : : : air , ãäå ai1 состояние первой (слева) ячейки, ai2 состояние второй ячейки и т.д.

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

состояний Q = fq0; q1; : : : ; qng, Q \ A = ?. Состояние q0 называется заключительным и означает завершение работы машины, а состояние q1 начальным и означает начало работы машины.

3. Программа Π, т.е. совокупность выражений T (i; j) (ãäå i = 0; : : : ; m, j = 1; : : : ; n), каждое из которых имеет один из следующих видов:

aiqj ! L qk (сдвиг головки, находящейся в состоянии qj напротив ячейки с буквой ai, на одну ячейку влево с заменой состояния qj íà qk);

aiqj ! R qk (сдвиг головки, находящейся в состоянии qj напротив ячейки с буквой ai, на одну ячейку вправо с заменой состояния qj íà qk);

aiqj ! alqk (замена буквы ai в текущей ячейке на букву al, à также замена состояния qj головки на состояние qk).

Выражения T (i; j) называются командами. При этом команды не

могут начинаться со слов aiq0. Символы L è R не принадлежат множеству A [ Q.

Таким образом, машина Тьюринга T есть пятерка hA; Q; Π, q0; q1i, а работа машины T состоит в изменении ее конфигурации K, состоящей

из состояния ленты, состояния головки и положения текущей ячейки. Дискретным моментам времени t = 0; 1; 2; : : : соответствуют кон-

фигурации K0; K1; K2; : : : Конфигурация K0 называется начальной, а конфигурация Kt, содержащая q0, заключительной. Конфигурации

84

M = ®qjai¯, ãäå ®ai¯

будут задаваться в виде машинных слов со-

стояние ленты, qj состояние головки, находящейся напротив ячейки с состоянием ai, занимающей то же положение среди других ячеек,

что и буква ai в слове ®qjai¯.

Опишем преобразование M !T M0 машинного слова M в машинное слово M0 за один шаг работы машины T .

Пусть команда T (i; j) равна aiqj ! L qk. Åñëè ® пустое слово Λ,

òî M2 = qka0ai¯. Åñëè æå ® = ®0al, òî M2 = ®0qkalai¯.

Åñëè T (i; j) = aiqj ! R qk, òî M2 = ®aiqka0 ïðè ¯ = Λ è M2 = ®aiqkal¯0 ïðè ¯ = al¯0.

Åñëè T (i; j) = aiqj ! alqk, полагаем M2 - ®qkal¯.

Будем говорить, что машинное слово M0 получается из машинного слова M c помощью машины T , и писать M )T M0, если существует

последовательность преобразований Mi !T Mi+1, i = 0; : : : ; k ¡ 1, для которой M0 = M, Mk = M0.

Преобразование M )T M0, при котором на каждом переходе Mi !T

Mi+1 не достраиваются ячейки слева, обозначается через M VT M0. Преобразование M )T M0, при котором на каждом переходе Mi !T

Mi+1 не достраиваются ячейки ни слева, ни справа, обозначается че- рез M jVT M0.

В дальнейшем в записях !T , )T , VT è jVT индекс T будет опус-

каться, если из контекста будет ясно, о какой машине T èäåò ðå÷ü.

Зафиксируем алфавит A = fa0; a1; a2; : : : ; amg. Через axi будем обо- значать слово aiai : : : ai алфавита A, состоящее из x áóêâ ai. Приведем список машин, которые будут использоваться в дальнейшем в качестве составляющих для других машин.

1.A (перенос нуля): q1001x0 jV q001x00.

2.Á+ (сдвиг вправо): q1ai1x0 jV ai1xq00.

3.Á¡ (сдвиг влево): 01xq1ai jV q001xai.

4. (транспозиция): q101x01y0 jV q001y01x0.

5.Ê (копирование): q101x00x0 jV q001x01x0.

6.Ë (стирающая машина): q101x0 jV q000x0.

7.R (удаление 1): q101x+10 jV q001x00.

8.S (добавление 1): q101x0 jV q001x+1.

9.Сложение: q101x+101y+10 jV q001x+y+1000.

10.Умножение: q101x+101y+10 V q001x¢y+10.

85

грамма. Обозначим через

Приведем примеры программ для машин Á+ è Сложение, оставив

написание остальных программ читателю в качестве упражнения. Программа для машины Á+, например, выглядит так:

0q1 ! Rq2; 0q2 ! 0q0;

aiq1 ! Rq2; aiq2 ! Rq2; i = 1; : : : ; m:

Для написания программы машины Сложение приведем сначала упрощенные преобразования, позволяющие перерабатывать машинное слово q101x+101y+10 в слово q001x+y+1000:

q101x+101y+10 jV 01x+101y+1q®0 jV

½01x+1q¯01y¡1000 jV q001x+y+1000; åñëè y =6 0; q001x+1000; åñëè y = 0:

Программу, соответствующую указанной схеме, представим в виде следующей таблицы команд, в которой на пересечении строки с символом ai 2 A и столбца с символом qj 2 Q, j > 0, имеется запись

¤qk (¤ 2 A [ fL; Rg), содержащаяся в команде aiqj ! ¤qk, а пустая ячейка соответствует произвольной записи ¤qk и для определенности будет означать 0q0:

q1

q2

q3

q4

q5

q6

q7

q8

q9

0

Rq2

Rq3

Lq4

Lq5

Lq6 (ãäå y = 0)

0q0

Lq8

1q9

0q0

1

Rq2

Rq3

0q4

0q7 (ãäå y 6= 0)

Lq6

Lq8

Lq9

Определим основные операции над машинами Тьюринга.

2. Композиция машин Тьюринга. Пусть Π некоторая про-

[Π]qqij результат замены во всех командах из Π вхождений символов qi на символы qj.

Пусть Ti = hAi; Qi; Πi; q0Ti; q1Tii, i = 1; 2, машины Тьюринга с условиями A1 = A2 = A, Q1 \ Q2 = ?. Машина

D ³

1 n f 0

g´

[

2 1 q1

2

[

2 0

1

E

T = A; Q

q

T1

q0T1

Π ; q

T2

; q

T1

Q ; [Π ] T

называется композицией машин T1 è T2 и обозначается через T1 ± T2 или через T1T2.

Очевидно, для любого машинного слова M машины T1 преобразо- вание M )T M0 означает, что найдется слово M00 = ®q0T1¯ с условиями

M )T1 M00 è ®q1T2¯ )T2 M0.

86

Условимся считать, что для машин T1; T2; T3 запись T1T2T3 означает композицию машин T1T2 è T3, а запись (T1)n совпадает с записью n

машин T1T1 : : : T1.

Следующие машины представляются в виде композиции машин из списка 1 10.

11. Ön, n ¸ 2 (циклическая перестановка n аргументов):

q101x101x201x3 : : : 01xn0 jV q001xn01x101x2 : : : 01xn¡10:

12. Ên, n ¸ 2 (удвоение n аргументов):

q101x101x2 : : : 01xn0 V q001x101x2 : : : 01xn01x101x2 : : : 01xn0:

Машина Ö2 совпадает с машиной Â. Машина Ö3 соответствует следующей цепочке преобразований:

q101x101x201x30 jVÁ+ 01x1q®01x201x30 jVÖ2

01x1q¯01x301x20 jVÁ¡ q°01x101x301x20 jVÖ2 q001x301x101x20:

Таким образом, Ö3 = Á+Ö2Á¡Ö2. В общем случае по индукции выводится равенство Ön+1 = Á+ÖnÁ¡Â.

Машина Ê2 представляется в виде следующей композиции:

Ê2 = Á+ÊÁ¡(Ö3)2(Á+)2Ê(Á¡)2Ö4(Á+)2Ö2(Á¡)2;

а машина Ên+1 выражается через Ên по следующей формуле:

Ên+1 = Á+ÊnÁ¡(Ö2n+1)2n(Á+)2nÊ(Á¡)2n¢ Ö2n+2(Á+)n+1Ön+1(Á¡)n+1:

3. Условные операторы. Пусть T1, T2 машины Тьюринга, удо- влетворяющие условиям предыдущего пункта. Определим машину T ,

содержащую начальное состояние q1T , заключительное состояние q0T è обладающую следующими свойствами для любых символов a; b; c 2 A,

ñëîâ ®; ¯		2	W	(	A	, машинных слов M , содержащих заключительные
					)				Tii		Mi заменой
состояния qTi, и машинных слов [Mi]q0T
			0						q0 , получающихся из
q0Ti	íà q0T , i = 1; 2:
											q0T1
						T1	abc¯ )	T1	T	T
	à) åñëè abc = 010 è ®q1								M1, òî ®q1 abc¯ )		[M1]q0T ;

87

á) åñëè abc = 010 è ®q

T2

abc¯

)

T2

M

, òî ®q

T

abc¯

)

T

[M

q0T2

1

1

] T

6

2

2

q0 .

Положим

A; Q;

; qT ; qT

®,T2ãäå

T -

- T1

Π

0

1

T

T

T

T

T

T

Q = (Q1 n fq0

g) [ (Q2 n fq0

g) [ fq0

; q1

; q2

; q3

; q4

; q5 g;

Π = [Π1

qT1

qT2

[ Π0;

]q0T

[ [Π2]q0T

0

0

Π0 программа, осуществляющая проверку условия abc = 010 и задание альтернатив по следующей таблице команд:

	q1T		q2T		q3T		q4T		q5T
0	Rq2T		Lq1T2		Lq4T				Lq1T2
1	1q1T2		Rq3T		Lq5T		Lq1T1		Lq1T2
a2	T2		T2		T				T2
	a2q1		Lq1		Lq5				Lq1
: : :	: : :		: : :		: : :		: : :		: : :
am	T2		T2		T				T2
	amq1		Lq1		Lq5				Lq1

Отображение E(¢; ¢), ставящее в соответствие машинам T1 è T2 ìà- øèíó T , называется условным оператором и обозначается через E(T1; T2)

èëè E ½ T1

T2 .

Пусть Ti = hAi; Qi; Πi; q0Ti; q1Tii, i = 0; 1; 2, машины Тьюринга с

условиями A0 = A1 = A2 = A, Q0					Q1 = ?, Q0	\		Q2 = ?, Q1	\	Q1 = ?,
			T	T
T = E(T1; T2),				\
	T = hA; Q; Π; q0 ; q1 i. Условным оператором с циклом
называется оператор, ставящий в соответствие машинам T0; T1; T2 ìà-
øèíó T ¤ = A; Q¤; Π¤; q0T ; q1T0				c множеством внутренних состояний
DT0			E		q0T0			q0T1		q0T2
Q¤ = (Q0 n fq0	g) [ Q и программой Π¤ = [Π0]q1T						[ [Π1]q0T [ [Π2			]q1T0 [ Π0:
Значение T ¤ условного оператора с циклом от машин T0, T1, T2
			T1
обозначается через T˙0E ½ T˙2 .
Работа машины T ¤			с машинным словом M0, содержащим началь-
ное состояние q1T0		машины T ¤, состоит в следующем. Сначала машина
T0 перерабатывает слово M0 в слово ®q1T abc¯, соответствующее сло-
âó ®q0T0abc¯, на котором завершается работа машины T0. Затем с по-
мощью программы Π0			проводится проверка равенства abc = 010. Â

случае равенства машина T1 перерабатывает слово ®q1T abc¯ в некоторое слово M1, содержащее q0T , и завершает свою работу или работает неограниченное время.

88

Åñëè æå abc =6 010, машина T2 некоторое слово M2, содержащее q1T0

перерабатывает слово ®q1T abc¯ â

, соответствующее слову, на котором завершается работа машины T2, или работает неограниченное вре-

мя. При получении слова M2 снова применяется машина T0 и процесс продолжается неограниченное время или после прохождения некоторого числа циклов останавливается после работы машины T1.

4. Функции, вычислимые на машинах Тьþринга. Для любого натурального числа n 2 N обозначим через n слово, состоящее из

n + 1 числа единиц: 11 : : : 1.

Функция f : X ! N, ãäå X µ Nk, называется вычислимой на ма-
условия:		Tf = DA; Q; Π; q0		; q1 E, если выполняются следующие
шине Тьюринга			Tf	Tf
à) èç (n1	; : : : ; nk) 2 X следует
	q1Tf 0n10n2 : : : 0nk0 )Tf ®q0Tf 0					f(n1; n2; : : : ; nk)0¯;
á) èç (n1	; : : : ; nk) 2 Nk n X следует
		qTf	n n : : : n		k0 )		1;
		1	0 10 2	0

т.е. начиная со слова q1Tf 0n10n2 : : : 0nk0 машина Tf работает неограниченно долго, не приходя в заключительное состояние q0Tf .

Таким образом, вычислимость функции f на машине Тьюринга Tf означает, что по любому набору (n1; : : : ; nk) из области определения

±f (закодированному в виде наборов единиц длин ni + 1, разделенных нулями) машина Tf выдает значение f(n1; : : : ; nk) (закодированное в виде набора единиц длины f(n1; : : : ; nk) + 1), а для любого набора

(n1; : : : ; nk)		2 Nk n X		машина Tf не завершает работу за конечное
время.
Функция f называется правильно вычислимой на машине Тьюрин-
à) èç	D(n1	; : : : ; nk)		X Eследует,
ãà Tf =	A; Q; Π; q0Tf ; q1Tf				если выполняются следующие условия:
			2

q1Tf 0n10n2 : : : 0nk0 VTf q0Tf 0f(n1; n2; : : : ; nk)0¯

и ячейка, напротив которой находится головка в начальный момент времени, совпадает с ячейкой, напротив которой находится головка в заключительный момент времени;

á) èç (n1; : : : ; nk) 2 Nk n X следует

q1Tf 0n10n2 : : : 0nk0 V1;

89

т.е. начиная со слова q1Tf 0n10n2 : : : 0nk0 машина Tf работает неограни- ченно долго, не приходя в заключительное состояние q0Tf , è ïðè ýòîì не достраиваются ячейки слева.

Функция f называется правильно вычислимой (сокращенно ПВФ), если f правильно вычислима на некоторой машине Тьюринга.

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

Ï ð è ì å ð 3.1.1. 1. 0-Функция o : N ! N, для которой o(x) = 0, x 2 N, правильно вычислима на машине ËS.

2. Функция следования s : N ! N, для которой s(x) = x + 1, x 2 N,

правильно вычислима на машине S.

íà

n

n

! N,

3. n-

Местная функция проекции

n

(x

; : : : ; x

m-ю координату Im : N

для которой I

) = xm, x1; : : : ; xn

, 1

·

m

·

n правильно

m

1

n

Á+ n 1

(

ËÁ

n

21. N

вычислима на машине Öm(

) ¡

¡)

¡

! N, ¢(x; y) =

4. Функции + : N2

! N, +(x; y) = x + y, è ¢ : N2

x ¢ y, правильно вычислимы на машинах Сложение è Умножение

соответственно. При этом машина

Умножение представима в виде

следующей машины:

+E

½ RÁ¡ÂÁ+ÊÁ¡ÂÁ+E˙

Á

Á¡ÂÁ+ËÁ¡

½

Á¡Ö3(Á+)2(ËÁ¡)2

Сложение Б

:

RÁ

Á

¡)2

Ö2

Á+

)2Ê(

Á

Ö

Á+

)2

+A(

3(

¡)2

3(

˙¡

5. Функция усеченной разности

˙

2

! N

, ãäå

¡ : N

x¡˙ y = ½ x ¡ y; åñëè x ·> y;

0; åñëè x

y;

правильно вычислима на машине

RÁ

¡ : ¤

+E˙ 8 RÁ¡E

<

ËÁ¡

½

+À˙

Á

Á+ËÁ

Теорема 3.1.1. Åñëè

функции

f1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn)

:

è g(y1; : : : ; ym) правильно вычислимы, то функция

h(x1; : : : ; xn) = g(f1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn))

правильно вычислима.

90