Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Машина Тьюринга
Содержание
- 1. Машина Тьюринга
- 2. Определение:Машина Тьюринга(МТ) — абстрактный исполнитель (абстрактная вычислительная машина) , осуществляющий алгоритмический процесс. Была предложена Аланом Тьюрингом в 1936 году.
- 3. Устройство машины Тьюринга.1. Внешний алфавит: А = {a0,
- 4. Устройство машины Тьюринга.2. Внутренний алфавит Q = {q0,
- 5. Устройство машины Тьюринга.3) Внешняя память (лента)Машина имеет
- 6. Внешняя память (лента) Пустая клетка содержит a0.
- 7. Устройство машины Тьюринга.4) Каретка (управляющая головка)Каретка машины
- 8. Устройство машины Тьюринга.5. Функциональная схема (программа).Программа машины
- 9. Описание работы машины Тьюринга К началу работы
- 10. Описание работы машины Тьюринга Стандартное положение называется
- 11. Описание работы машины Тьюринга Находясь в не
- 12. Описание работы машины Тьюринга В соответствии с
- 13. Скачать презентанцию
Определение:Машина Тьюринга(МТ) — абстрактный исполнитель (абстрактная вычислительная машина) , осуществляющий алгоритмический процесс. Была предложена Аланом Тьюрингом в 1936 году.
Слайды и текст этой презентации
Слайд 2Определение:
Машина Тьюринга(МТ) — абстрактный исполнитель (абстрактная вычислительная машина) , осуществляющий алгоритмический
процесс.
Слайд 3Устройство машины Тьюринга.
1. Внешний алфавит:
А = {a0, a1, …, a
n}
Элемент a0 называется пустой символ.
В этом алфавите в
виде слова кодируется исходный набор данных и результат работы алгоритма Устройство машины Тьюринга.
Слайд 4Устройство машины Тьюринга.
2. Внутренний алфавит
Q = {q0, q1, …, qm},
{П, Л, С}
В любой момент времени машина М находится
в одном из состояний q0, q1, …, qmПри этом: q1 - начальное состояние
q0 - заключительное состояние
Символы {П, Л, С} – символы сдвига (вправо, влево, на месте)
Слайд 5Устройство машины Тьюринга.
3) Внешняя память (лента)
Машина имеет ленту, разбитую на
ячейки, в каждую из которых может быть записана только одна
буква.
Слайд 6Внешняя память (лента)
Пустая клетка содержит a0.
В каждый момент времени
на ленте записано конечное число непустых букв.
Лента является конечной, но
дополняется в любой момент ячейками слева и справа для записи новых непустых символов.Это соответствует принципу абстракции потенциальной осуществимости.
Слайд 7Устройство машины Тьюринга.
4) Каретка (управляющая головка)
Каретка машины располагается над некоторой
ячейкой ленты – воспринимает символ, записанный в ячейке
В одном такте
работы каретка сдвигается на одну ячейку (вправо, влево) или остается на месте
Слайд 8Устройство машины Тьюринга.
5. Функциональная схема (программа).
Программа машины состоит из команд:
Для
каждой пары (qi, aj) программа машины должна содержать одну команду
(детерминированная машина Тьюринга).
Слайд 9Описание работы машины Тьюринга
К началу работы машины на ленту подается
исходный набор данных в виде слова
Будем говорить, что непустое
слово а в алфавите А{а0} воспринимается машиной в стандартном положении, если:-оно задано в последовательных ячейках ленты,
- все другие ячейки пусты,
- машина обозревает крайнюю правую ячейку из тех, в которых записано слово а.
Слайд 10Описание работы машины Тьюринга
Стандартное положение называется начальным (заключительным), если машина,
воспринимающая слово в стандартном положении, находится в начальном состоянии q1
(стоп-состоянии q0)
Слайд 11Описание работы машины Тьюринга
Находясь в не заключительном состоянии, машина совершает
шаг, который определяется текущим состоянием qi обозреваемым символом aj
Слайд 12Описание работы машины Тьюринга
В соответствии с командой qi - qkal
Х выполняются следующие действия:
Содержимое обозреваемой ячейки aj стирается и в
нее записывается символ al (который может совпадать с aj )Машина переходит в новое состояние qk (оно может совпадать с состоянием qi )
Каретка перемещается в соответствии с управляемым символом Х Є {П, Л, С}
