Машина Тьюринга — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение: начал выписывать формализацию процесса работы МТ)
(Определение: выписал правила для отношения перехода)
Строка 12: Строка 12:
  
 
== Определение ==
 
== Определение ==
 
+
=== Определение машины ===
 
Формально машина Тьюринга определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где
 
Формально машина Тьюринга определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где
 
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
 
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
Строка 25: Строка 25:
 
Существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга. В дальнейшем мы будем для простоты предполагать, что головка в процессе работы не записывает на ленту символ <tex>B</tex>. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую <tex>B</tex> на ленту.
 
Существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга. В дальнейшем мы будем для простоты предполагать, что головка в процессе работы не записывает на ленту символ <tex>B</tex>. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую <tex>B</tex> на ленту.
  
Кроме формального определения самой машины требуется также формально описать процесс её работы. Назовём '''конфигурацией''' машины Тьюринга тройку <tex>\langle w, q, v \rangle</tex>, где <tex>q \in Q</tex> — текущее состояние автомата, а <tex>w, v \in (\Pi \setminus \{B\})^*</tex> — строки слева и справа от головки соответственно. В данной записи головка находится над ячейкой, на которой написана первая буква <tex>v</tex> (или <tex>B</tex>, если <tex>w = \varepsilon</tex>).
+
=== Определение процесса работы ===
 +
Кроме формального определения самой машины требуется также формально описать процесс её работы. Назовём '''конфигурацией''' машины Тьюринга тройку <tex>\langle w, q, v \rangle</tex>, где <tex>q \in Q</tex> — текущее состояние автомата, а <tex>w, v \in (\Pi \setminus \{B\})^*</tex> — строки слева и справа от головки до первого пробельного символа соответственно. В данной записи головка находится над ячейкой, на которой написана первая буква <tex>v</tex> (или <tex>B</tex>, если <tex>w = \varepsilon</tex>).
  
В дальнейшем используются следующие обозначения: <tex>x, y, z \in \Pi</tex>, <tex>w, v \in \Pi*</tex>
+
В дальнейшем используются следующие обозначения: <tex>x, y, z \in \Pi</tex>, <tex>w, v \in \Pi^*</tex>
  
 
Определим на конфигурациях отношение перехода <tex>\langle w_1, q_1, v_1 \rangle \vdash \langle w_2, q_2, v_2 \rangle</tex>:
 
Определим на конфигурациях отношение перехода <tex>\langle w_1, q_1, v_1 \rangle \vdash \langle w_2, q_2, v_2 \rangle</tex>:
 
* если <tex>\delta(q, x) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, xv \rangle \vdash \langle w, p, zyv \rangle</tex>
 
* если <tex>\delta(q, x) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, xv \rangle \vdash \langle w, p, zyv \rangle</tex>
 +
* если <tex>\delta(q, x) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, xv \rangle \vdash \langle wy, p, v \rangle</tex>
 +
* если <tex>\delta(q, x) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, xv \rangle \vdash \langle w, p, yv \rangle</tex>
 +
 +
Особо следует рассмотреть случай переходов по пробельному символу:
 +
* если <tex>\delta(q, B) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, \varepsilon \rangle \vdash \langle w, p, zy \rangle</tex>
 +
* если <tex>\delta(q, B) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle wy, p, \varepsilon \rangle</tex>
 +
* если <tex>\delta(q, B) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle w, p, y \rangle</tex>

Версия 21:40, 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] — всюду определённая функция перехода автомата

Существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга. В дальнейшем мы будем для простоты предполагать, что головка в процессе работы не записывает на ленту символ [math]B[/math]. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую [math]B[/math] на ленту.

Определение процесса работы

Кроме формального определения самой машины требуется также формально описать процесс её работы. Назовём конфигурацией машины Тьюринга тройку [math]\langle w, q, v \rangle[/math], где [math]q \in Q[/math] — текущее состояние автомата, а [math]w, v \in (\Pi \setminus \{B\})^*[/math] — строки слева и справа от головки до первого пробельного символа соответственно. В данной записи головка находится над ячейкой, на которой написана первая буква [math]v[/math] (или [math]B[/math], если [math]w = \varepsilon[/math]).

В дальнейшем используются следующие обозначения: [math]x, y, z \in \Pi[/math], [math]w, v \in \Pi^*[/math]

Определим на конфигурациях отношение перехода [math]\langle w_1, q_1, v_1 \rangle \vdash \langle w_2, q_2, v_2 \rangle[/math]:

  • если [math]\delta(q, x) = \langle p, y, \leftarrow \rangle[/math], то [math]\langle wz, q, xv \rangle \vdash \langle w, p, zyv \rangle[/math]
  • если [math]\delta(q, x) = \langle p, y, \rightarrow \rangle[/math], то [math]\langle w, q, xv \rangle \vdash \langle wy, p, v \rangle[/math]
  • если [math]\delta(q, x) = \langle p, y, \downarrow \rangle[/math], то [math]\langle w, q, xv \rangle \vdash \langle w, p, yv \rangle[/math]

Особо следует рассмотреть случай переходов по пробельному символу:

  • если [math]\delta(q, B) = \langle p, y, \leftarrow \rangle[/math], то [math]\langle wz, q, \varepsilon \rangle \vdash \langle w, p, zy \rangle[/math]
  • если [math]\delta(q, B) = \langle p, y, \rightarrow \rangle[/math], то [math]\langle w, q, \varepsilon \rangle \vdash \langle wy, p, \varepsilon \rangle[/math]
  • если [math]\delta(q, B) = \langle p, y, \downarrow \rangle[/math], то [math]\langle w, q, \varepsilon \rangle \vdash \langle w, p, y \rangle[/math]