Ш.И._Галиев_МЛ_и_ТА_2004

Если алгоритм В ив применим к слову Н=А(1’), то и алгоритм С будет не применим к р вследствие того, чтп 8) будет бесконечно

иерораБ.тгыватьслово а6я Ь„г ...Ь„ .

Если алгоритм В применим к слову R=A(Pu то в резулыаю его применения ии получили бы слово В(Л(Р)), например:

КА(ГУ)^сЯ]стг..£т1(с„,ёА, \S ii l)

Теперь s-кротное.применение 4) приводит к слову

Далее, применяя 5), аздгем (М) раз 6), имеем

аВ с,||Ся,..£ж =а|5В(ЖЛ).

Применяя заключительную подстановку 7), получим результат:

B(A(Ff,

Таким образом, С(Р) = В1А(Р>), и, так хак олово Р было произ­ вольным, теорема доказана.

Соединенна алгоритмов.

Теорема 6.2. Пусть АъАъ...,А,- нормальные алгоритмы в ал-

алфавигов. Тогда существует нормальный ялгоркга В над Л, назы­ ваемый соединением пгоритмов^],^;,...,/*, такой, что

VP вА :Д(Р)ё/),“(P'lA,1(?)..^„9 (Р\

где/1/- ость естественное распространением, наА.

Теорему примем без доказательств*. Доказательство можно уви­ деть , например, в работе [21).

Рлыепиаение алгоритмов. Пусть заданы алгоритмы А и Н

в алфашпв А и некоторое	условие V.	Тогда можно задать
предписание следующего	типа: для данного слова Р в алфави­

те А проверить, удовлетворяет ли оно условию U. Если удовлетворяет, 231

то к Р применить алгоритм А . в противном случае применить к Р алгоритмВ (рнс 6.2).

Ясип, что условно Uможно задавать самым различным образом, напришр, можно задать так' условие U выполнимо для заданною слова Р, если P*NP (ом. главу о сложности вычислений). Решить, выполнимо это условие V или нет, и настоящее время нельзя, ибо указанная проблема еще не решена, несмотря на настойчивые попитки. Поэтому такого рода (типа) условия не будем рассмат­ ривать. Будем считать, что условие U всегда задано с помощью кйкого-ю алгоритма € в алфавитеА в следующем виде:

условие С/для слова? выполнено, если С(Р)-Л.

условие U для слова Р не выполнено, если СТР)*А

При таком задании условия U описанное предписание будем считать разветплением алгоритмов в алфавите А. Точнее, пусть А, В

и С - алгоритмы в алфавите А. Разветвлением алгоритмов А а В

называется алгоритм УъА.ке применимый к Р, если на применим к Р

алгоритм Ситакой, что

Будем говорить, что это разветвление втгоритмов упрммежя алгоритмом С.

232

I	Теорема 6.3. Разгетвление нормальных алгоритмов, управляемое
нормальнымалгоритмом,являеюянормальный адорншом.
	Примем без доказательства, Доказательство можно найти,
	например, в рабох-е [21J.
	Повторение аягвримпм. Во многих случаях требуется

поьторигьоля)' и ту же процедуру многократно, каждый раз применяя ее к результату, полученному на предыдущем шаге. Процедур; ПоВсирясм до выполнения некоторого усиовия U. Буден считать, что уединив U задается с помощью алгоритма, как и ранее. Такаа процедура будет задавать повторение алгирюма. Боасе точно: пусть/! и С - алгоритмы г алфавите А а Рс - произвольное слово в А Применим к Рц алгоритм А. Полупим некоторое слово Л-Д^о)> если С'Р{)=Л, то процесс заканчивается. Если С(Л}/Л так /1 применяем

А, получаем Pi=A(Pl)=A(AfP:)). Если С\_Р{)=Л, то процесс заканчи­ ваем. Нели ОР-.)Ф/1, то к Яг применяемА и т.д. Определенный тихим образом алгоритм называется повторением алгоритма Л, упраиляя-

Повторение алгоритма можно представить блок-схемой,

Также без доказательства причем следующуютеорему.

Теорема 6.4. Повторение нормального алгоритма, управля­ емое нормыьным алгоригмом, есть термальный алгоритм.

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

§ 7. Машин» Тьюуннга

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

Пусть имеется лента, потенциально бесконечная в обб стороны и разделенная на ячейки (квадраты) (рис. 6.4). Потенциальная бесконечность ленты понимается в том смысле, что в каждый данный

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

г ш	ж	п	п	Г	.7	1 ,™
			.а д ,....4,,,	которое	называется
			алфавитом машины. В га.идой
			ячейке может быть			млисан

только один из символов-буква алфавита машины.

Машина обладает некоторый конечным множеством внутрен­ них состояний {§<>?).•••-?»}• В каждый данный иоменг времени машина находится только в одном из этих состояний. Считаем, что

щутрвнним состоянием q<\ обладает каждая машина и ?о называется

ючпяьнмм состоянием

Машина имеет читающую гпдсеку, которая в каждый данный юмент времени находится на одном и квадратов ленты и вослришмает символ, записанный на этом квадрате. Будем предполагать, !то среди символов iSo,Si...,S, имеется сичвоп, означающий пустой свадрат, например, .¾ Положим, что символ .% принадлежит алфавшу саждой мшпины Тьюринга и .¾ не может быть записан ни в каком дидрате ленты. Когда пишем, что читающая головка обозревает гвадрат с символам ,¾ или записывает в квадрат символ 5-j, то имеем

!виду, чте читающая головка соответственно обозревает пустой ладрат (воспринимая его как 50) или оставляет квадриг без символов воспринимая его как Sn). Машина действует не непрерывно, а лишь ! дискретные моменты времени.

Если в какой-то момент времени l читающая головка воспри-

«мает	квадрат (т.е. стоит на квадрате), содержащий символ 5,.
1 машина находится во вн>греннем состоянии qh то действие машины
определено, и она совершает одно из следующих четырехдействий:
1)	головка стирает символ Л1, н записывает на том же квадрате

:иивол St]

3)головка перемешается в соседний справа квадрат;

4)машина останавливается.

Вслучаях 1)-35 машина переходит во внутреннее состояние ц, н готова к действию вследующий момент времени f+1.

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

1	)q,S,Lq,:,
2
J \q iS,Rqr.

235

вол St, асрсдикомандмашины неткоманды, ишичаюпийс*с ¢.¾. Если на ленте имеется какое-нибудь слово Р (в частносто,

пустее слаос), читающаяголовкапомещена на квадратс первой левой буквой слова Р и машина приведена во внутреннее состояние qc. то машина начинает оперировать на ленте: ее головки стирает и пишет символы и перемешается из оляпго квадрата в Другой (соседний). Если при этом машинакогда-нибудь останавливается, то находящееся в uDuem остановкисловоналапе смотается результатом применения мшины Т ! данному слову Р. Если процесс переработан машиной 'Г cuotjP бесконечен,тоговорят, то машинаГнс цюмснима*словуР.

это не «делано, то предполагается, что читающая головка находится ни первой (самой левой) букве сгтпьа Р

Рассмотрим««сколько примеров.

1. Пусть задана машина Гкомандами: qaiRq,

qAlqn,

1 на ленте записано слово /М (рис.6.5). Легко убецэтъся, что машина

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

2. Мапшна, заданная командами:

CuSiSjo

?цЧ?ь

где нн одно из S, (1S Ы *) не совпадает г. символом 1, движете» гм ленте вправо, пока не ширетит ихоидаиие {если 14К0е вообще име­ ете») символа!, после чет останавливается.

3. Машина Т, заданная командами

ЧъаНцп qt,bSqп fuSgdfi,

кап легко убедиться, приписывает к любому слову Р алфавита {а,Ь\ справабукву в и останавливается.

237

§9. Алгоритм Тьюрппга. Вычислимость по Тьюрингу

Скаждой машиной Тыоринга можно связать некоторый алгоритм ЛГл в алфавите А машины Т. Бозьмсм произвольное слово Р алфавита А и запишем его слева направо в кшшрыш чистой ленты, причем так, чтобы nepoas (смая левая) буква Р находилась под читающей головкой. Приведем машину Г во внутреннее состояние ¢¢.

Машина начинает рабогать. Если она когда-нибудь остановится, к появившееся на ленте слово Q алфавита А является результатом применения машина Т к слову Р. Алгоритм преобразования слова Р в слово Q с помощью машины Т называется алгоритмом Тоюринга и обозначается через А ц

Будеч говорить, что мат пни Гьюрикта Т с алфавитом А, включающим 1 н*. частично вычисляет частичнуюарифметическую функцию если для любых натуральных к , k, и некоторых гит имеем:

тогда и только горда, когда определена хотя бы одна нз частей sioro равенства. Это означает, что применение алгпрюма Тьюринга Аг,л

к слову (41,ft’2,...,An) даст слово, означающее с точностью до слов

S„r и 5™ зшчеиие функции (So - интерпретируете* как изображение пустот квадрата ленты).

Частично определенная арифметическая функция ДгьХг,, называется частично вычислимой по Тьюрингу, если сушествует машина Тьюринга, которая частично вычисляет

Арифмстическа* функция называется вычислимой по 2'ыорингу, если существует машина Тьюринга Т с алфавитом А, включающим ! и *, такая, что для любых натуральных М ь -Л найдутся некоторые г пт:

Это означает, что применение алгоритма ТьюрингаАг_л к слову

>*и) &1ст слово, означающее с точностью ло слое SJ я S” значение функции j%fe,...,fa), т.е. существует машина Тьюринга, вычисляющаяэту функциюдля любыхзначений ее аргументов.

Пример. Рассмотрим всюду определенную функцию сложении АХ,У)-Х*У- Покажем, что эта функции вычислима по Тьюрингу Для этого построим МишинуТьюринга;

¢0 Sa R¢1 ¢1 1 Я-?,

¢1 * Мг q-i 1 R ®

qi SiLqj

9з I ■?«<?}

Нетрудно убедиться, >тто эта машин» пгрееоднг слово (ю,л) =М^,..1 * П...1 Е слово! L..1, а последнее слово азначаот

число т+п, следовательно, я т машинаТьюринга вычисляет функцию x-ty.

Итак, функциих~*~увычислима поТьюрингу.

§111. Связь межлу машинами Тыпрш

ннормальным» алгоритмами

Теорема 6.S, Пусть Т - машина Тьюринга с алфавитом А.]

Тогда «ушесгаует нормальный алгоритм В над'/l, вполне эквиеа-|
Iлеитный относительноЛалгоритмуТьюринга.^.,	I

23»

Доказательны». Каждая конкретная машина Тьюринга содер­ жит конечное число команд вида 1)-3) (§ 7). Выпишем сначала для веек команд вида qjSiSig, (если они есть) машины 7 формулы подста­ новки qiSr->q£>. При этой порядок этих формул подстановок друг относительно друга не существенен, ибо никакие две команды машины Г не имели совпадающими перпые дна символа. Далее для каждой команды вида 4jSJ.q, (если она есть) выпишем всевозможные формулы подстановки вида SiifrS.-'tq&'i,, гае SteA, и формулу подстановки qjS,-*q&St- Затем для каждой команды вида qtS:I>q, (если она ость) выпишем всевозможные формулы подстановки д,ЗД-*У?г5/, где St^A, и формулу подстановки q,S—>S,q,St. Наконец, выпишем всевозможные формулы постановок. q,-**Л, где у, - внутреннее состоанис, заданной машина Т, и формулу подстановки /!-*?} Полученная таким образом таблица (схема) формул подгганошж определяет некоторый нормальныйалгоритм В надЛ.

Покажем, что полученный нормальный япиритм В вполне эквивалентен относительно алфавита^ алгоритму Тьюринга. А~,, т.е. оба алгоритма одинаковым образом преобразуют любое слово Р алфавита А. Для этого возьмем произвольно: слово Р в алфамте Л, пусть, например, Р“ 5н,>?«,...¾. где Sh^A. Машина Тьюринга находогся сначала во инугреннем состоянии qa к обозревает символ 5(]. Дальнейшие ее действия определены ее командами. Из подстановок алгоритма В к слову Г будет сначала применима только последняя подстановка, в результате которой получим слово

9о St.Se....Sb, ■

(6.2)

Если среди команд машины Г имеется команда, по которой стирается буква &, и заменяется, например, буксой SffieA), т.е. имеется команда q?SifSfi„ то го подстановке 4tSu-*q^ алгоритм преобразует адово (6.2) В слово

240