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

Содержание

• 
  Слайд 1

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

• 
  Слайд 2

  Введение

  Понятие алгоритма. Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату (Марков А.А.) Свойства алгоритма: 1) Дискретность. 2) Определенность. 3) Результативность. 4) Массовость.

• 
  Слайд 3

  Математическая модель машины Тьюринга

  Машина Тьюринга (МТ) – это математическая модель идеализированной цифровой вычислительной машины. Устройство машины Тьюринга. Лента. Считывающая головка. Устройство управления. Внутренняя память.

• 
  Слайд 4

  Лента

  В клетки в дискретный момент времени может быть записан только один символ (буква) из внешнего алфавита A = {˄, a1,a2,…,an-1}, 2≥n . Пустая ячейка обозначается символом ˄, а сам символ ˄ называется пустым, при этом остальные символы называются непустыми.

• 
  Слайд 5

  Считывающая головка

  Головка может считывать содержимое ячейки и записывать в нее новый символ из алфавита А. В одном такте работы она может сдвигаться только на одну ячейку вправо (П), влево (Л) или оставаться на месте (Н).

• 
  Слайд 6

  Внутренняя память

  Внутренняя память машины представляет собой некоторое конечное множество внутренних состояний Q = {q0, q1, … , qm}, m≥ 1. Будем считать, что мощность | Q |≥2. Два состояния машины имеют особое значение: q1 – начальное внутреннее состояние (начальных внутренних состояний может быть несколько), q0 – заключительное состояние или стоп-состояние (заключительное состояние всегда одно). В каждый момент времени МТ характеризуется положением головки и внутренним состоянием.

• 
  Слайд 7

  Устройство управления

  Выполняет следующие действия: Изменяет считываемый в момент t символ ai на новый символ aj (в частности оставляет его без изменений, т. е. ai= aj ); Передвигает головку в одном из следующих направлений: Н, Л, П; Изменяет имеющееся в момент t внутреннее состояние машины qi на новое qj , в котором будет машина в момент времени t +1. Такие действия устройства управления называют командой, которую можно записать в виде: qiaiajDqj

• 
  Слайд 8

  Работа машины Тьюринга

  Работа машины полностью определяется заданием в первый (начальный) момент: Слова на ленте, т. е. последовательности символов, записанных в клетках ленты (слово получается чтением этих символов по клеткам ленты слева направо); Положения головки; Внутреннего состояния машины.

• 
  Слайд 9
  

  Если в начальный момент на ленте записано слово a1, a2,˄, a1 , a1 то начальная конфигурация будет иметь вид: Работа машины Тьюринга состоит в последовательном применении команд, причем, применение той или команды определяется текущей конфигурацией. Так в приведенном выше примере должна применятся команда с левой частью q1a1 . Результатом работы машины считается слово, которое будет записано на ленте в заключительной конфигурации, т. е. в конфигурации, в которой внутреннее состояние машины есть q0 .

• 
  Слайд 10

  Примеры машины Тьюринга

  Пример 1. Построить машину Тьюринга T1­ , которая применима ко всем словам с внешним алфавитом {a,b} и делает следующее: любое слово x1,x2…xn , где xi = a или xi = b (i = 1, 2 … n) преобразует в слово x2, …xn, x1 т. е., начиная работать при слове x1,x2…xn на ленте в начальной конфигурации, машина остановится, и в заключительной конфигурации на некотором участке ленты будет записано слово x2, …xn, x1, а все остальные клетки ленты (если такие будут) окажутся пустыми.

• 
  Слайд 11
  

  Решение: За внешний алфавит машины T1 возьмем множество A={˄, a, b} , а за внутренний – Q = {q0, q1, q2, q3}. Команды определим следующим образом: q1a ˄Пq2, q1b ˄Пq3, qiy ˄ППi, где yϵ{a, b}, i =2, 3; q2˄ aHq0, q3˄ bHq0 Рассмотрим работу машины T1 над словом ba . В работе машины над словом ba начальная конфигурация имеет следующий вид:

• 
  Слайд 12
  

  На втором шаге действует команда q3aaПП3 и на машине создается конфигурация: Наконец, третий шаг обусловлен командой q3˄ bHq0. В результате чего создается конфигурация: Эта конфигурация является заключительной, так как машина оказалась в состоянии остановки q0. Таким образом, слово ba переработано в слово ab . На первом шаге действует команда: q1b ˄Пq3 . В результате создается следующая конфигурация:

• 
  Слайд 13
  

  Пример 2.Применить машину Тьюринга T1 из примера 1 к слову bbabb, исходя изначального положения, при котором в состоянии q1 обозревается крайняя левая ячейка, в котором содержится символ этого слова. Решение:

• 
  Слайд 14
  

  Более короткая запись этой последовательности конфигураций, т. е. процесса работы машины будет : Таким образом, слово bbabb переработано машиной в слово babbb .