Презентация "Машина Тьюринга"
Подписи к слайдам:
Машина Тьюринга
Выполнил студент группы ПК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 )
- Каретка перемещается в соответствии с управляемым символом Х Є {П, Л, С}
Информатика - еще материалы к урокам:
- Презентация "Операции с файлами и папками" 4 класс
- Конспект урока "Операции над файлами и папками (каталогами)" 4 класс
- Презентация "Виды алгоритмов по способу последовательности действий" 4 класс
- Конспект урока "Виды алгоритмов по способу последовательности действий" 4 класс
- Рабочая программа по информатике по УМК Матвеевой Н.В. для 2 класса
- Презентация "Множество. Число элементов множества. Подмножество" 3 класс