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

Материал из Викиконспекты
Версия от 16:22, 5 декабря 2012; Андрей Шулаев (обсуждение | вклад) (первая версия, неформальное описание и неполное определение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Введение

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

Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:

  • бесконечной одномерной ленты, разделённой на ячейки,
  • головкой, которая представляет из себя детерминированный конечный автомат. За один шаг головка может перезаписать символ под лентой и сместиться на одну ячейку

Определение

Формально машина Тьюринга определяется как кортеж из восьми элементов [math]\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle[/math], где

  • [math]\Sigma[/math] — алфавит, из букв которого могут состоять входные слова
  • [math]\Pi \supseteq \Sigma[/math] — символы, которые могут быть записаны на ленту в процессе работы машины
  • [math]B \in \Pi \setminus \Sigma[/math] ­— пробельный символ (от слова blank)
  • [math]Q[/math] — множество состояний управляющего автомата
  • [math]Y \in Q[/math] — допускающее состояние автомата
  • [math]N \in Q[/math] — отвергающее состояние автомата
  • [math]S \in Q[/math] — стартовое состояние автомата
  • [math]\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}[/math] — функция перехода автомата