Изменения
→Многоленточная машина Тьюринга
=== Многоленточная машина Тьюринга ===
В отличие от многодорожечной машины Тьюринга, ленты не зависят друг от друга и головки во время одного шага могу могут перемещаться по-разному. То есть, функция перехода теперь имеет тип <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> позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).
