Изменения
добавлен пример
* <tex>\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}</tex> — всюду определённая функция перехода автомата
Отметим, что существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга. В дальнейшем мы будем для простоты предполагать, что головка в процессе работы не записывает на ленту символ <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>x, y, z \in \Pi</tex>, <tex>w, v \in \Pi^*</tex>
Очевидно, что определённое отоношение является функциональным: для каждой конфигурации <tex>C</tex> существует не более одной конфигурации <tex>C'</tex>, для которой <tex>C \vdash C'</tex>.
Для машины Тьюринга, которая пишет символ <tex>B</tex> на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода. Это предоставляется читателю в качестве упражнения.
=== Результат работы ===
Машину Тьюринга можно рассматривать как распознаватель слов языка. Пусть <tex>M</tex> — машина Тьюринга, распознаваемый ей язык определяется как <tex>\mathcal L(M) = \{ x \in \Sigma^* \mid \exists y, z \in \Pi^*: \langle \varepsilon, S, x \rangle \vdash^* \langle y, Y, z \rangle \}</tex>.
Также можно рассматривать машины Тьюринга как преобразователь входных данных в выходные. Машина <tex>M</tex> задаёт вычислимую функцию <tex>f</tex>, причём <tex>f(x) = y \Leftrightarrow \exists z \in \Pi^* : \langle \varepsilon, S, x \rangle \vdash^* \langle z, Y, y \rangle</tex>. Переход автомата в состояние <tex>N</tex> можно интерпретировать как аварийное завершение программы (например, при некорретном входе). Примеры машин-распознавателей и машин-преобразователей будут даны ниже. == Примеры машин Тьюринга ==Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:* в стартовом состоянии головка идёт вправо от младшего бита к старшему, заменяя все единицы на нули,* встретив нуль или пробельный символ головка записывает единицу, после чего переходит в состояние <tex>R</tex>,* в состоянии <tex>R</tex> головка идёт влево от старшего бита к младшему, не изменяя символы 0 и 1 на ленте,* встретив в состоянии <tex>R</tex> пробельный символ, головка перемещается на один символ вправо и переходит в состояние <tex>Y</tex>, завершая работу. Следующее определение формализует данный алгоритм:* <tex>\Sigma = \{0, 1 \}</tex>, <tex>\Pi = \{0, 1, B\}</tex>* <tex>Q = \{S, R, Y, N \}</tex>** <tex>\delta(S, 1) = \langle S, 0, \rightarrow \rangle</tex>** <tex>\delta(S, 0) = \langle R, 1, \downarrow \rangle</tex>** <tex>\delta(S, B) = \langle R, 1, \downarrow \rangle</tex>** <tex>\delta(R, 0) = \langle R, 0, \leftarrow \rangle</tex>** <tex>\delta(R, 1) = \langle R, 1, \leftarrow \rangle</tex>** <tex>\delta(R, B) = \langle Y, B, \rightarrow \rangle</tex>
