Машина Тьюринга с полулентой

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

Идея доказательства этого утверждения основана на следующих предпосылках:

а) рабочая область ленты ограничена двумя маркерами: неподвижным - слева и подвижным - справа;

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

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

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

Рассмотрим пример построения машины Тьюринга с правой полулентой, вычисляющей функцию f(x) = 2x. Алгоритм вычисления данной функции состоит в приписывании нуля к входной цепочке справа.

Таблица соответствия данной машины Тьюринга будет иметь следующий вид:

Здесь символ “<“ обозначает левый маркер, а символ “>“ - правый маркер. Машина Тьюринга, начав работу из стандартной начальной конфигурации, после выполнения совокупности команд переходит в стандартную заключительную конфигурацию.

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

Дата добавления: 2015-07-26; просмотров: 293; Нарушение авторских прав

Мы поможем в написании ваших работ!