Презентация на тему МАШИНА ТЬЮРИНГА

осуществляющий алгоритмический процесс.

Была предложена Аланом Тьюрингом в 1936 году.

…, a n}
Элемент a0 называется пустой символ.
В

этом алфавите в виде слова кодируется исходный набор данных и результат работы алгоритма Устройство машины Тьюринга.

…, qm}, {П, Л, С}
В любой момент времени

машина М находится в одном из состояний q0, q1, …, qm

При этом: q1 - начальное состояние
q0 - заключительное состояние

Символы {П, Л, С} – символы сдвига (вправо, влево, на месте)

разбитую на ячейки, в каждую из которых может быть

записана только одна буква.

момент времени на ленте записано конечное число непустых букв.

Лента

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

над некоторой ячейкой ленты – воспринимает символ, записанный в

ячейке

В одном такте работы каретка сдвигается на одну ячейку (вправо, влево) или остается на месте

из команд:



Для каждой пары (qi, aj) программа машины должна

содержать одну команду (детерминированная машина Тьюринга).

ленту подается исходный набор данных в виде слова 
Будем

говорить, что непустое слово а в алфавите А{а0} воспринимается машиной в стандартном положении, если:
-оно задано в последовательных ячейках ленты,
- все другие ячейки пусты,
- машина обозревает крайнюю правую ячейку из тех, в которых записано слово а.

если машина, воспринимающая слово в стандартном положении, находится в

начальном состоянии q1 (стоп-состоянии q0)

машина совершает шаг, который определяется текущим состоянием qi обозреваемым

символом aj