Презентация по дискретной математике "Машина Тьюринга"

• 1 слайд

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

• 2 слайд

  Понятие Машины Тьюринга
  Алан Тьюринг
  В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель, представляющий собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель.
  Предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
  

• 3 слайд

  Устройство машины Тьюринга
  В состав машины Тьюринга входит бесконечная в обе стороны лента, разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний.
  Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
  

• 4 слайд

  Устройство машины Тьюринга
  Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита внутренний алфавит. Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке, и внутреннее состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
  

• 5 слайд

  Пример машины Тьюринга
  Проверка на четность числа символов (единичек), записанных на ленте
  
  𝑞 1 → 𝑞 2 𝑅 ∗
  
  𝑞 2 → 𝑞 1 𝑅 ∗
  
  𝑞 1 ∗ → 𝑞 0 𝐸 четное
  
  
  
  𝑞 2 ∗ → 𝑞 0 𝐸 нечетное
  

• 6 слайд

  Для задания конкретной машины Тьюринга, требуется описать для нее следующие составляющие:
  Внешний алфавит
  Конечное множество, элементы которого называются буквами. Одна из букв этого алфавита должна представлять собой пустой символ.
  Внутренний алфавит
  Конечное множество состояний головки. Одно из состояний должно быть начальным (запускающим программу), одно - конечным (завершающим программу).
  Таблица переходов
  Описание поведения автомата (головки) в зависимости от состояния и считанного символа.
  

• 7 слайд

  Варианты Машин Тьюринга
  Многодорожечная Машина Тьюринга
  Машина Тьюринга с полубесконечной лентой
  Многоленточная машина Тьюринга
  Универсальная машина Тьюринга
  не отличаются от обычных машин Тьюринга по вычислительной мощности
  

• 8 слайд

  Многодорожечная Машина Тьюринга
  Машиной Тьюринга с nn дорожками называется вычислитель, аналогичный машине Тьюринга, лишь с тем отличием, что лента состоит из nn дорожек, на каждой из которых записаны символы ленточного алфавита. У многодорожечной машины одна головка, которая за один шаг переходит в одном направлении на всех дорожках одновременно. Многодорожечная машина Тьюринга тривиально эквивалентна обычной с ленточным алфавитом
  Универсальная машина Тьюринга
  Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, универсальный язык перечислим с помощью машины Тьюринга.
  

• 9 слайд

  Машина Тьюринга с полубесконечной лентой
  Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой.
  Теорема
  Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.
  

• 10 слайд

  Многоленточная машина Тьюринга
  В отличие от многодорожечной машины Тьюринга, ленты не зависят друг от друга и головки во время одного шага могут перемещаться по-разному. 
  Утверждение (Тезис Чёрча-Тьюринга):
  Класс перечислимых языков совпадает с классом языков, перечислимых с помощью машин Тьюринга
  Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.
  

• 11 слайд

  Спасибо за внимание