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


Подписи к слайдам:
Презентация PowerPoint

Машина Тьюринга

Выполнил студент группы ПК2-12

Баютова Надя.

Определение:

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

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

Устройство машины Тьюринга.

1. Внешний алфавит:

А = {a0, a1, …, a n}

Элемент a0 называется пустой символ.

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

Устройство машины Тьюринга.

2. Внутренний алфавит

Q = {q0, q1, …, qm}, {П, Л, С}

В любой момент времени машина М находится в одном из состояний q0, q1, …, qm

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

q0 - заключительное состояние

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

Устройство машины Тьюринга.

3) Внешняя память (лента)

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

Внешняя память (лента)

Пустая клетка содержит a0.

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

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

Это соответствует принципу абстракции потенциальной осуществимости.

Устройство машины Тьюринга.

4) Каретка (управляющая головка)

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

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

Устройство машины Тьюринга.

5. Функциональная схема (программа).

Программа машины состоит из команд:

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

Описание работы машины Тьюринга

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

Будем говорить, что непустое слово а в алфавите А{а0} воспринимается машиной в стандартном положении, если:

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

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

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

Описание работы машины Тьюринга

Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q1 (стоп-состоянии q0)

Описание работы машины Тьюринга

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

Описание работы машины Тьюринга

В соответствии с командой qi - qkal Х выполняются следующие действия:

  • Содержимое обозреваемой ячейки aj стирается и в нее записывается символ al (который может совпадать с aj )
  • Машина переходит в новое состояние qk (оно может совпадать с состоянием qi )
  • Каретка перемещается в соответствии с управляемым символом Х Є {П, Л, С}