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

UptoLike

Составители: 

15) q
3
1q
3
1L ε001*11ε 31) q
0
0 q
0
1L ε011*111ε
16) q
3
*q
3
*L ε001*11ε 32) q
0
ε q
z
1R ε111*111ε
Из примера видно, что машина Тьюринга из стандартной начальной конфигурации,
имея на ленте аргумент 111 и выполнив совокупность команд 1-32, перешла в стандартное
заключительное состояние, имея на ленте результат ε
111*111ε.
3.8. Машина Тьюринга с полулентой
В рассмотренных выше определениях машины Тьюринга использовалась бесконечная в
обе стороны лента. Ограничим ленту с одной стороны и покажем, что машина Тьюринга с
правой или левой полулентой эквивалентна машине Тьюринга с бесконечной лентой.
Говорят, что функция, правильно вычислимая на машине Тьюринга с обычной лентой,
правильно вычислима и на машине Тьюринга с правой полулентой, т.е. для любой машины
Тьюринга Т существует эквивалентная ей машина с правой полулентой T
R
.
Идея доказательства этого утверждения основана на следующих предпосылках:
а) рабочая область ленты ограничена двумя маркерами: неподвижным - слева и
подвижным - справа;
б) на внутренней части ограниченной области машина Тьюринга с полулентой должна
работать как обычная машина Тьюринга, а при выходе на маркеры она должна освобождать
рабочее пространство, для этого правый маркер может сдвигаться вправо, а при выходе на
левый маркер необходимо сдвинуть всю цепочку вправо;
в) полученный результат, находящийся между маркерами, в конце работы машины
Тьюринга нужно сдвинуть вплотную к левому маркеру.
Машина Тьюринга может вычислять функцию с восстановлением, то есть с сохранением
исходных данных. Это позволяет получить на ленте сначала результат, а затем - исходные
данные или наоборот.
Рассмотрим пример построения машины Тьюринга с правой полулентой, вычисляющей
функцию f(x) = 2x. Алгоритм вычисления данной функции состоит в приписывании нуля к
входной цепочке справа.
Таблица соответствия данной машины Тьюринга будет иметь следующий вид:
< 0 1 >
ε
q
0
q
0
0R q
0
1R q
1
0R
q
1
q
2
>L
q
2
q
z
< R
q
2
0L q
2
1L
Здесь символ “<“ обозначает левый маркер, а символ “>“ - правый маркер. Машина
Тьюринга, начав работу из стандартной начальной конфигурации, после выполнения
совокупности команд переходит в стандартную заключительную конфигурацию.
Полученный результат располагается между маркерами и сдвинут вплотную к левому
маркеру.
3.9. Универсальная машина Тьюринга
До сих пор мы имели дело со специализированными машинами Тьюринга,
предназначенными для решения конкретных задач и отличающимися набором команд,
внутренним и внешним алфавитами. Однако можно построить универсальную машину