304
правки
Изменения
→Варианты машины Тьюринга: добавлена многоленточная МТ
=== Машина Тьюринга с полубесконечной лентой ===
Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой следующим образом: в первой ячейке записывается символ <tex>\mathbb T</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> позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).
Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов <tex>*</tex> символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.
