Л.С. Корухова, М.Р. Шура-Бура. Введение в алгоритмы (793777), страница 6
Текст из файла (страница 6)
А. А. Марковпредложил рассматривать более широкий класс алгоритмов, допустив для задания пар,определяющих подстановки, использование алфавитов, являющихся расширениемалфавита А, употребляемого для задания исходных слов. Такие алгоритмы А. А. Марковназвал нормальными алгоритмами над алфавитом А. Слова, получаемые на отдельныхшагах таких алгоритмов, могут и не принадлежать A*.
А. А. Марковым быласформулирована гипотеза, названная им принципом нормализации, заменяющая гипотезуТьюринга:ПРИМЕРПостроим нормальный алгоритм, который "инвертирует" любое слово, заданное валфавите А = { a, b }, т.е. заменяет в заданном слове все символы a на символы b и все bна a.+a b++b a++ +Работа алгоритма начинается с приписывания к исходному слову слевадополнительного символа +.
Такое приписывание обеспечивается правилом подстановки,которое применимо к любому слову. Но поскольку оно стоит последним, то применяетсятолько один раз, когда другие правила еще не применимы. Далее символ + "перегоняется"в конец слова с заменой стоящей за ним буквы на "противоположную". Когда +19оказывается в конце слова, применимо третье правило подстановки, которое "стирает"символ + и прекращает выполнение алгоритма.Любой алгоритм, отображающий слова из A*, где А - конечный алфавит, эквивалентеннормальному алгоритму над алфавитом А.
Как и гипотеза Тьюринга, принципнормализации А.А.Маркова недоказуем. Как гипотеза Тьюринга, так и принципнормализации, являются формальными определениями алгоритма, и важнымобстоятельством для их обоснования является эквивалентность этих определений. Дляустановления их эквивалентности достаточно доказать:I) Алгоритм, выполняемый каждой машиной Тьюринга, эквивалентен некоторомунормальному алгоритму над внешним алфавитом машины.II) Каждый нормальный алгоритм над алфавитом А эквивалентен алгоритму,выполняемому некоторой машиной ТьюрингаДоказательство утверждения I) оказывается совсем простым.
Нормальный алгоритм,эквивалентный заданной машине Тьюринга с внешним алфавитом А ={ a 1 , a 2 , ... , a p } ивнутренним алфавитом Q = {q 0,...q n,q s}, задается подстановками, определяемымиследующим образом. Для каждой клетки (qi, a j) таблицы переходов, в которой записанатройка (a j', R, q i'), т.е. предписывается переход управляющей головки к рассмотрениюследующей (правой) ячейки ленты, вводим подстановку q i a j aj'q i' , если q i'≠ qs, илизаключительную подстановку qia j aj', если q i' = q s. Если же в клетке (q i,a j) записанатройка (a j',L,q i'), то управляющая головка должна перейти к рассмотрению предыдущей(левой) ячейки ленты. В этом случае для всех a k ∈ A при q i'≠ q s вводим группуподстановок a k qi a j q i'a k aj', либо при q i' = q s - группу заключительных подстановокa k qi a j a k aj'.
К выписанным подстановкам добавим подстановку q 0, поместив ее вконце всех остальных, упорядочение которых произвольно.Легко видеть, что нормальный алгоритм, определенный введенными подстановками,начинается с приписывания перед исходным словом символа q 0.Такое приписываниеобеспечивается формулой подстановки q 0. Далее выполняется нормальный алгоритм,который полностью соответствует работе заданной машины Тьюринга и завершается темже результатом.Доказательство положения II требует преодоления некоторых технических трудностей.Это связано с тем, что операции подстановки, выполняемые в нормальном алгоритме,существенно сложнее элементарных шагов машины Тьюринга и каждый шаг нормальногоалгоритма требует порой сложной серии различных тактов машины Тьюринга.
Длякаждого нормального алгоритма, заданного конечной последовательностью подстановокv i v i' , i = 1,...,n,мы построим машину Тьюринга, выполняющую алгоритм, эквивалентный заданному.Через a(i,j) будем обозначать символы, входящие в слова v i - левые части подстановокv i v i' , определяющих нормальный алгоритм. Пусть v i= a(i,1) a(i,2) ... a(i,m i),где i= 1,2,...,n-1 и m i = | v i|. Заметим, что для i < n можно считать, что v i ≠ λ, так какподстановки, следующие за подстановкой с пустым словом в ее левой части, не имеютникакого значения в выполнении нормального алгоритма и могут быть отброшены.
Еслиv i ≠ λ, то считаем, что v n= a(n,1)...a(n,m n). Через b(i,j) будем обозначать символы,входящие в слова v i' - правые части подстановок, определяющих нормальный алгоритм.При этом v i' = b(i,1) b(i,2) ... b(i,n i), i= 1,2,...,n. Если n i=0, то в правой части i-той формулыподстановки - пустая цепочка (v i'= λ).Соотношение длин цепочек v i и v i' в соответствующей подстановке задается формулойn i = m i + d i, где d i может принимать положительные, отрицательные, и нулевыезначения. Рассмотрим далее вариант реализации подстановок, для которых d i >= 0.
При20реализации подстановок, правая часть которых "короче" левой ( d i< 0), не возникаетновых принципиальных трудностей. Предлагаем рассмотреть этот вариантсамостоятельно.Для определения вхождения левых частей подстановок, определяющих заданныйнормальный алгоритм, в управляющей головке соответствующей машины Тьюрингапредусмотрим следующие состояния:1). q(i,j) для j =1,..,m i и i = 1,2,...,n-1, и i = n, если m n= 0Эти состояния будут соответствовать проверке наличия символа a(i,j) вобозреваемой головкой ячейке ленты машины Тьюринга.
Состояние q(1,1) отождествим сначальным состоянием q 0.2). q(i,j)' и q(i)' - состояния, обеспечивающие возврат управляющей головкидля продолжения поиска вхождения или его завершения3). q(i,m i+1) = p(i,d i), i= 1,2,...,n - состояния, соответствующие установлениювхождения v i и переходу к реализации i-ой подстановки4). q(n+1,1) = q s - заключительное состояние машины ТьюрингаЧерез IZ обозначим множество номеров подстановок, которые нумеруютзаключительные подстановки нормального алгоритма, а q Z - соответствующие такимподстановкам состояния. Если машина оказывается в состоянии qZ, то нужно перевестиуправляющую головку в начало слова и закончить работу, т.е.
перейти в состояниеостанова q s.Для описания таблицы переходов конструируемой машины Тьюринга Т N мы будемописывать клетки таблицы соотношениями вида :[ q, a] : [ a', X, q'],где слева в квадратных скобках обозначена клетка таблицы переходов символами еестроки q и столбца а, справа же -.содержимое этой клетки. Здесь а' - записываемый вобозреваемую ячейку символ, X - один из символов указателей R и L, перехода головки крассмотрению следующей ячейки ленты, а q' - состояние, в которое переходитуправляющая головка.
Клетки таблицы переходов, обеспечивающие обнаружениесоответствующих вхождений, зададим следующими формулами1. [ q(i,j), a(i,j) ] : [ a(i,j), R, q(i,j+1) ]Осуществляется поиск вхождения левой цепочки i-ой подстановки, j-ая и всепредыдущие буквы цепочки v i найдены - отождествляем j+1 - ю букву2. [ q(i,1), a ] : [ a, R, q(i,1) ], где a- буква, а ≠ Λ и а ≠ a(i,1)Поиск вхождения первой буквы цепочки v i, идем вправо, пока не встретимпервую букву3. [ q(i,j), a ] : [ a, L, q(i,j-1)' ], где j>1 и а ≠ Λ и а ≠ a(i,1)При поиске встретили букву, отличную от нужной а(i,j), - возвращаемся влево4.
[ q(i,j), Λ] : [Λ, L, q(i)' ]Если дошли до конца слова и не нашли вхождение левой цепочки i-ойподстановки, то идем влево по слову5. [ q(i,1)', a ] : [ a, R, q(i,1) ]Ищем начало вхождения v i, начиная со следующей буквы слова6. [ q(i,j)', a ] : [ a, L, q(i,j-1)' ]Возврат влево при неудачном поиске7. [ q(i)', a ] : [ a, L, q(i)' ]Дойдя до конца слова, не нашли v i - идем влево к первой букве слова8. [ q(i)', Λ ] : [Λ, R, q(i+1,1) ]Ищем вхождение следующей ( i+1 )- ой подстановки.21После того, как найдено вхождение в заданное слово левой цепочки (.v i.)подстановки ( v i v i' ) из формул подстановок, задающих нормальный алгоритм, нужнореализовать соответствующую подстановку, т.е.
заменить в исходном слове цепочку v i нацепочку v i'. Реализация такой замены происходит после того, как машина оказывается всостоянии q(i,m i+1) = p(i, d i), и ее последующая работа осуществляется в соответствии соследующими действиями, записанными в соответствующие клетки таблицы переходовмашины :9. [ p(i,j), a ] : [ Λ, R, p(i,j,a) ] для всех i10.
[ p(i,j,a), b ] : [ a, R, p(i,j,b) ] для символов b ≠ Λ11. [ p(i,j,a), Λ ] : [ a, L, p(i,j-1)' ]12. [ p(i,j)', a ] : [ a, L, p(i,j)' ]13. [ p(i,j)', Λ ] : [ Λ, R, p(i,j)' ]14. [ p(i,0), a ] :[ a, L, r(i,n i) ]15. [ r(i,j), a ] : [ b(i,j), L, r(i,j-1) ] для j > 0При этом r(i,0) = q Z, если i ∈ I Z иr(i,0) = q , если i ∉ I Z16. [ r(q Z), a ] : [ a, L, r(q Z) ]17. [ r(q Z), Λ ] : [ Λ, R, q s ]18. [ q, a ] : [ a, L, q ]19. [ q, Λ ] : [ Λ, R, q 0 ] , где q 0 = q(1,1)6.
САМОПРИМЕНИМОСТЬ И ПРОБЛЕМА ПРИМЕНИМОСТИТаблицы переходов машин Тьюринга кроме символов внешнего алфавита содержаттакже символы протяжки ленты и символы состояний управляющей головки. Однако, несоставляет большого труда представить таблицу переходов каждой машины некоторымсловом внешнего алфавита этой машины, если алфавит содержит по крайней мере двасимвола. Тот или иной способ такого представления не имеет принципиального значения.Но, учитывая дальнейшее изложение, касающееся универсальной машины Тьюринга, мырассмотрим конкретный способ изображения таблиц переходов. При этом двухмернуютаблицу переходов представим в виде линейного слова, которое можно записать на лентумашины Тьюринга.Расширим внешний алфавит двумя символами, при помощи которых будем разделятьцепочки символов, задающие строки и клетки таблиц переходов, и изображать заданные вклетках состояния управляющей головки.
Обозначим эти два символа через & и @.Занумеруем символы состояний управляющей головки данной машины Тьюринга так,чтобы номером 1 оказался символ начального состояния, а последним - символзаключительного. Последовательностью @@...@ будем изображать символ состояния сномером, равным длине такой последовательности. Включив в изображение клеткитаблицы переходов указание на столбец, которому принадлежит клетка, и признак,позволяющий легко обнаружить, является или нет состояние, к которому предписываетперейти клетка, заключительным, представим каждую клетку цепочкой@@...@ & S Z a ja i&,где @@...@ - изображение состояния, в которое переходит управляющая головка в такте,соответствующем изображаемой клетке;S - & или @ - символы, кодирующие сигналы R и L протяжки ленты;Z - & или @ - символы, кодирующие признак заключительного состояния;a j - символ, записываемый на ленту в соответствующем такте работы машины;a i - символ столбца таблицы переходов, которому принадлежит изображаемая клетка.22Изображение клетки завершается символом &, отмечающим конец "содержимого"клетки.Каждую строку таблицы переходов представим конкатенацией символа & ипоследовательности цепочек, изображающих составляющие строку клетки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
