Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов, страница 5

В клетках таблицы на пересечении строки и столбца будет находиться действие(или правая часть команды).Таблица соответствия для задания машины Тьюринга из рассмотренного примера будетвыглядеть следующим образом:q0q10q0 1Rq1 0L1Q0 0RQ1 1Lεq1 ε Lq z εLИнвертирование входной цепочки можно выполнить программой машины Тьюринга,приведенной в таблице соответствия. Эта программа включает шесть команд.3.5.

Вычислимые функцииГоворят, что машина Тьюринга вычисляет функцию f(x1, x2, ..., xn), если выполняютсяследующие условия:1) для любых x1, x2, ..., xn, принадлежащих области определения функции, машинаТьюринга из начальной конфигурации, имея на ленте представление аргументов, переходитв заключительную конфигурацию, имея на ленте результат (представление функции);2) для любых x1, x2, ..., xn, не принадлежащих области определения функции, машинаТьюринга из начальной конфигурации работает бесконечно.Если начальная и заключительная конфигурации машины Тьюринга являютсястандартными, то говорят, что машина Тьюринга правильно вычисляет функцию f.Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга,вычисляющая ее.Для того чтобы доказать вычислимость функции, а в дальнейшем и существованиеалгоритма, необходимо построить машину Тьюринга, реализация которой на практикезачастую представляет собой трудоемкую задачу.

В связи с этим возникает необходимостьразбиения алгоритма на отдельные задачи, каждая из которых будет решаться отдельноймашиной Тьюринга. Если объединить программы этих машин, то получится новаяпрограмма, позволяющая решить исходную задачу.Машины Тьюринга могут вычислять искомую функцию с восстановлением и безвосстановления. Вычисление функции с восстановлением означает работу машиныТьюринга с сохранением исходных данных:p0 1X1* . . * 1Xn*⇒p z 1f(X1, X2, . . . , Xn) *1X1* .

. * 1Xn.Приведенное определение позволяет получать на ленте сначала результат, а затемисходные данные. В отдельных случаях удобно сделать наоборот:p0 1X1* . . * 1Xn*⇒1X1* . . * 1Xn * p z 1f(X1, X2, . . . , Xn) .Вычисление функции без восстановления означает работу машины Тьюринга безсохранения исходных данных:p0 1X1* . . * 1Xn ⇒* p z 1f(X1, X2, .

. . , Xn) .Справедливо утверждение, что всякая правильно вычислимая функция правильновычислима с восстановлением.3.6. Операции над машинами Тьюринга1. Композиция машин Тьюринга. Пусть машины Т1 и Т2 имеют программы Р1 и Р2.Предположим, что внутренние алфавиты этих машин не пересекаются; пусть qz1 заключительное состояние машины Т1, а q02 - начальное состояние машины Т2. Заменимвсюду в программе Р1 заключительное состояние qz1 на начальное состояние q02 машины Т2и полученную программу объединим с программой Р2.

Новая программа Р определяетмашину Т, называемую композицией машин Т1и Т2 по паре состояний (qz1, q02).Композиция машин может быть обозначена Т1 ⋅Т2 или Т1Т2. Более подробно композициямашин записывается следующим образом:Т = Т(Т1, Т2, (qz1, q02)), гдеT1 = (Q1, A1, δ1, p01, pz1, a01, a11),Т2= (Q2, A2, δ2, p02, pz2, a02, a12).Пусть a01 = a02 = a0 и a11 = a12 = a1.Внешний алфавит композиции Т1Т2 являетсяобъединением внешних алфавитов машин Т1 и Т2:p02Т= (Q1 ∪ Q2 \ {pz1}, A1 ∪A2, | (δ1,∪ δ2), p01, pz2, a0, a1).pz1Операция композиции, выполняемая над алгоритмами, позволяет получать новые, болеесложные алгоритмы из ранее известных простых алгоритмов.2. Итерация машины Тьюринга. Эта операция применима только к одной машине.Пусть qz - заключительное состояние машины Т, а qn - какое-либо состояние машины Т,не являющееся заключительным.

Заменим всюду в программе Р машины Т состояние qz наqn . Полученная программа определяет новую машину Т′(qz, qn), которая называетсяитерацией машины Т по паре состояний (qz, qn). Если машина Тьюринга имеет однозаключительное состояние, то после выполнения итерации получается машина, не имеющаязаключительного состояния.3. Разветвление машин Тьюринга. Пусть машины Тьюринга Т1, Т2 и Т3 задаютсяпрограммами Р1, Р2 и Р3 соответственно.

Считаем, что внутренние алфавиты этих машинпопарно не пересекаются. Пусть qz11 и qz12 - какие-либо различные заключительныесостояния машины Т1. Заменим всюду в программе Р1 состояние qz11 начальным состояниемq02 машины Т2, а состояние qz12 начальным состоянием q03 машины Т3. Затем новуюпрограмму объединим с программами Р2 и Р3. Получим программу Р, задающую машинуТьюринга и обозначаемую:Т = Т(Т1, (qz11, q02), Т2, (qz12, q03), Т3).Машина Т называется разветвлением машин Т2 и Т3, управляемым машиной Т1.3.7.

Примеры построения машин ТьюрингаПример 1. Построить машину Тьюринга, которая правильно вычисляет функцию f(x) =x+1 по правилам двоичного сложения.Решение. Исходя из формулировки задачи, требующей вычислить функцию по правиламсложения в двоичной системе сложения, выберем входной алфавит:А ={0, 1, ε}.Представим машины Тьюринга таблицей соответствия и графом.Таблица соответствия:01εq0q0 0Rq0 1RQ1 ε Lq1q2 1Lq1 0Lq2 1Lq2q2 0LQ2 1Lqz ε RПредставление машины Тьюринга в виде графа:1→ 1Rq00 → 0L1 → 0Lε → ε L0 → 1Lε → ε Rq2q1qzε → 1L0 → 0R1 → 1LЗапишем программу построенной машины Тьюринга для случая, когда входная цепочкана ленте равна двоичному числу 111.

Слева от каждой команды приведем представлениевходной цепочки на ленте до выполнения данной команды. Символ, который находится подголовкой, будем помечать подчеркиванием.1) q01 → q01R ε111ε6) q11 → q10L ε110ε2) q01 → q01R3) q01 → q01R4) q0ε → q1εL5) q11 → q10Lε111εε111εε111εε111ε7) q11 → q10L8) q1ε → q21L9) q2 ε → qz εRε100εε000εε1000εИз примера видно, что машина Тьюринга из стандартной начальной конфигурации, имеяна ленте аргумент 111, выполнив совокупность команд 1-9, перешла в стандартноезаключительное состояние, имея на ленте результат 1000.

Действительно:1112 + 12 = 10002.Пример 2. Построить машину Тьюринга, выполняющую операцию (x div 2) и имеющуювходной алфавит А = {0, 1, ε}.Таблица соответствия данной машины Тьюринга будет иметь следующий вид:q00q0 0R1q0 1Rq1q3 ε Lq2 ε Lεq1 ε Lq20q3 1L1q2 0Lεq3 1Lq3q2 0Lq2 1Lqz ε RОперация (x div 2) реализована сдвигом цепочки вправо на 1 разряд.Пример 3.

Построить машину Тьюринга, которая выполняет копирование заданногоаргумента. Выберем входной алфавит А={0,1,ε}. Представим данную машину таблицейсоответствия:q0q1q2q30q11Lq00R1q10Rq11Rq21Rq31L*q0*Lq2*RεqzεRq2*Rq31Lq3*LЗапишем программу построенной машины для заданной входной цепочки на ленте,равной двоичному числу 111.

Слева от каждой команды приведем представление входнойцепочки на ленте до выполнения данной команды. Символ, который находится подголовкой, будем помечать подчеркиванием.1) q01 → q10R2) q11 → q11R3) q11 → q11R4) q1ε → q2*R5) q2ε → q31L6) q3* → q3*L7) q31 → q31L8) q31 → q31L9) q30 → q00R10) q01 → q10R11) q11 → q11R12) q1* → q2*R13) q21 → q21R14) q2ε → q31Lε111εε011εε011εε011εε011*εε011*1εε011*1εε011*1εε011*1εε011*1εε001*1εε001*1εε001*1εε001*1ε17) q31 → q31L18) q30 → q00R19) q01 → q10R20) q1* → q2*R21) q21 → q21R22) q21 → q21R23) q2ε → q31L24) q31 → q31L25) q31 → q31L26) q3* → q3*L27) q30 → q00R28) q0* → q0*L29) q00 → q01L30) q00 → q01Lε001*11εε001*11εε000*11εε000*11εε000*11εε000*11εε000*11εε000*111εε000*111εε000*111εε000*111εε000*111εε000*111εε001*111ε15) q31 → q31L ε001*11ε16) q3* → q3*L ε001*11ε31) q00 → q01L32) q0ε → qz1Rε011*111εε111*111εИз примера видно, что машина Тьюринга из стандартной начальной конфигурации,имея на ленте аргумент 111 и выполнив совокупность команд 1-32, перешла в стандартноезаключительное состояние, имея на ленте результат ε111*111ε.3.8.

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

для любой машиныТьюринга Т существует эквивалентная ей машина с правой полулентой TR.Идея доказательства этого утверждения основана на следующих предпосылках:а) рабочая область ленты ограничена двумя маркерами: неподвижным - слева иподвижным - справа;б) на внутренней части ограниченной области машина Тьюринга с полулентой должнаработать как обычная машина Тьюринга, а при выходе на маркеры она должна освобождатьрабочее пространство, для этого правый маркер может сдвигаться вправо, а при выходе налевый маркер необходимо сдвинуть всю цепочку вправо;в) полученный результат, находящийся между маркерами, в конце работы машиныТьюринга нужно сдвинуть вплотную к левому маркеру.Машина Тьюринга может вычислять функцию с восстановлением, то есть с сохранениемисходных данных.