1632
правки
Изменения
м
rollbackEdits.php mass rollback
* если <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>.
}}
Очевидно, что определённое отношение является функциональным: для каждой конфигурации <tex>C</tex> существует не более одной конфигурации <tex>C'</tex>, для которой <tex>C \vdash C'</tex>.
=== Многоленточная машина Тьюринга ===
В отличие от многодорожечной машины Тьюринга, ленты не зависят друг от друга и головки во время одного шага могу могут перемещаться по-разному. То есть, функция перехода теперь имеет тип <tex>\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}^n</tex>.
Многоленточная машина с <tex>n</tex> дорожками эмулируется многодорожечной машиной с <tex>2n</tex> дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом <tex>*</tex> позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).
