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

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


Здесь Вы можете скачать готовую презентацию на тему Машина Тьюринга. Предмет презентации: Информатика. Красочные слайды и илюстрации помогут вам заинтересовать своих одноклассников или аудиторию. Для просмотра содержимого презентации воспользуйтесь плеером, или если вы хотите скачать презентацию - нажмите на соответствующий текст под плеером. Презентация содержит 12 слайдов.

Слайды презентации

Слайд 1
Выполнил студент группы ПК2-12 Баютова Надя. Машина Тьюринга
Слайд 2
Определение: Машина Тьюринга(МТ)  — абстрактный исполнитель (абстрактная вычислительная машина) , осуществляющий алгоритмический процесс. Была предложена Аланом Тьюрингом в 1936 году.
Слайд 3
Устройство машины Тьюринга. 1. Внешний алфавит: А = { a 0, a 1, …, a n } Элемент a0 называется пустой символ. В этом алфавите в виде слова кодируется исходный набор данных и результат работы алгоритма Устройство машины Тьюринга.
Слайд 4
Устройство машины Тьюринга. 2. Внутренний алфавит Q = { q 0 , q 1 , …, q m }, {П, Л, С} В любой момент времени машина М находится в одном из состояний q 0 , q 1 , …, q m При этом: q 1 - начальное состояние q 0 - заключительное состояние Символы {П, Л, С} – символы сдвига (вправо, влево, на месте)
Слайд 5
Устройство машины Тьюринга. 3) Внешняя память (лента) Машина имеет ленту, разбитую на ячейки, в каждую из которых может быть записана только одна буква.
Слайд 6
Внешняя память (лента) Пустая клетка содержит a 0 . В каждый момент времени на ленте записано конечное число непустых букв. Лента является конечной, но дополняется в любой момент ячейками слева и справа для записи новых непустых символов. Это соответствует принципу абстракции потенциальной осуществимости.
Слайд 7
Устройство машины Тьюринга . 4) Каретка (управляющая головка) Каретка машины располагается над некоторой ячейкой ленты – воспринимает символ, записанный в ячейке В одном такте работы каретка сдвигается на одну ячейку (вправо, влево) или остается на месте
Слайд 8
Устройство машины Тьюринга. 5. Функциональная схема (программа). Программа машины состоит из команд: Для каждой пары ( q i , a j ) программа машины должна содержать одну команду (детерминированная машина Тьюринга).
Слайд 9
Описание работы машины Тьюринга К началу работы машины на ленту подается исходный набор данных в виде слова  Будем говорить, что непустое слово а в алфавите А { а 0 } воспринимается машиной в стандартном положении , если: -оно задано в последовательных ячейках ленты, - все другие ячейки пусты, - машина обозревает крайнюю правую ячейку из тех, в которых записано слово а.
Слайд 10
Описание работы машины Тьюринга Стандартное положение называется начальным ( заключительным ), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q 1 (стоп-состоянии q 0 )
Слайд 11
Описание работы машины Тьюринга Находясь в не заключительном состоянии, машина совершает шаг, который определяется текущим состоянием q i обозреваемым символом a j
Слайд 12
Описание работы машины Тьюринга В соответствии с командой q i - q k a l Х выполняются следующие действия: 1. Содержимое обозреваемой ячейки a j стирается и в нее записывается символ a l (который может совпадать с a j ) 2. Машина переходит в новое состояние q k (оно может совпадать с состоянием q i ) 3. Каретка перемещается в соответствии с управляемым символом Х Є {П, Л, С}

Другие презентации по информатике



  • Яндекс.Метрика
  • Рейтинг@Mail.ru