304
правки
Изменения
м
→Определение процесса работы: ещё шаблоны
=== Определение процесса работы ===
Кроме формального определения самой машины требуется также формально описать процесс её работы. В определении для простоты будем предполагать, что головка в процессе работы не записывает на ленту символ <tex>B</tex>. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую <tex>B</tex> на ленту.
{{Определение|definition=Назовём '''конфигурацией''' машины Тьюринга тройку <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>
{{Определение|definition=
Определим на конфигурациях отношение перехода <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, 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>
}}
Очевидно, что определённое отношение является функциональным: для каждой конфигурации <tex>C</tex> существует не более одной конфигурации <tex>C'</tex>, для которой <tex>C \vdash C'</tex>.
