Презентация на тему Машина Тьюринга

осуществляющий алгоритмический процесс
Это математический объект, а не физическая машина

Предложена Аланом Тьюрингом в 1936 году

А = {a0 ,

a1 , …, an }
Элемент a0 называется пустой символ
В этом алфавите в виде слова кодируется исходный набор данных и результат работы алгоритма

Q = {q0 , q1 , …, qm}, {П, Л, С}
В любой момент времени машина М находится в одном из состояний q0 , q1 , …, qm
При этом:
q1 - начальное состояние
q0 - заключительное состояние
Символы {П, Л, С} – символы сдвига (вправо, влево, на месте)

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

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

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

в ячейке.




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

состоит из команд:







Для каждой пары (qi , aj )

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

появиться несколько параллельных вычислительных процессов




2) Разные машины Тьюринга

отличаются своими программами
Для каждого алгоритма создается своя машина Тьюринга, точнее ее программа

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

Будем говорить, что непустое слово a

- оно задано в последовательных ячейках ленты,

- все другие ячейки пусты,

- машина обозревает крайнюю правую ячейку из тех, в которых записано слово a

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

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

состояние q0
ее работа прекращается
На ленте записан результат

работы алгоритма – слово в алфавите

машина Тьюринга
-Что происходит при переходе в заключительное состояние q0
-Как

называется элемент a0