Презентация на тему "МАШИНА ТЬЮРИНГА"

Содержание

• 
  Слайд 1

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

  Выполнил студент группы ПК2-12 Баютова Надя.

• 
  Слайд 2

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

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

• 
  Слайд 3

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

  1. Внешний алфавит: А = {a0, a1, …, an} Элемент 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) Каретка перемещается в соответствии с управляемым символом Х Є{П, Л, С}