Принцип работы машины Тьюринга

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

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

Q\S			…		…
…
				D
…

Рис. 2

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

Для записи команды используется выражения вида D , где  - символ который головка должна записать в обозреваемую ячейку, D (D {L,R,N}) – один из трех вариантов сдвига головки: L (Left) – на одну ячейку влево, R (Right) – на одну ячейку вправо, N (None) – остаться на месте (не совершать перехода),  – перейти в новое состояние (или остаться в текущем).

Машина Тьюринга, выполняя каждую отдельную команду, осуществляет элементарное действие, называемое шагом (тактом). На каждом отдельном шаге (такте) команда предписывает лишь замену единственного символа , хранящегося в обозреваемой ячейке каким либо другим символом . При i=j содержимое обозреваемой ячейки не изменяется. При переходе от одного шага (такта) к другому адрес обозреваемой ячейки может изменяться не более чем на одну единицу, т.е. обозревается соседняя слева или соседняя справа ячейка, или же обозревается та же ячейка, что и в предыдущем шаге (такте). Таким образом, за один шаг (такт) работы машина Тьюринга может:

1. Изменить содержимое  обозреваемой ячейки ленты, т.е. заменить содержащийся в ней символ другим, или оставить прежний символ.

2. Совершить сдвиг влево или вправо, или остаться на месте;

3. Перейти в новое состояние, или остаться в текущем состоянии.

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

1. Задать внешний алфавит и записать в соответствии с ним символы на ленту;

2. Задать начальное положение головки на ленте;

3. Задать начальное состояние головки;

4. Задать некоторую программу (алгоритм), на основании которой головка будет совершать действия.

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

1. Дискретность алгоритма: решение задачи, записанное в виде алгоритма, должно быть разбито на отдельные простейшие команды, расположенные в порядке их выполнения;

2. Определённость алгоритма: каждая команда алгоритма должна быть понятна исполнителю, не оставлять места для её неоднозначного толкования и неопределенного исполнения;

3. Результативность алгоритма: алгоритм всегда должен приводить к определенному решению через конечное, минимальное число шагов (или сообщать, что такого решения нет);

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

II. НЕКОТОРЫЕ ПРАКТИЧЕСКИЕ ПРИМЕРЫ ПРОГРАММ (АЛГОРИТМОВ) ДЛЯ МАШИНЫ ТЬЮРИНГА