40
правок
Изменения
Нет описания правки
|proof=
Для упрощения доказательства без умаления общности предположим, что вход для двухстековой машины заканчивается специальным символом <tex>\$</tex>, которого нет в исходном алфавите. <br>
[[Изображение:SM.png|400px|thumb|left|Рис. 2. Представление ленты МТ двумя стекамии наоборот]]
<tex>\Rightarrow)</tex>
Докажем, что если язык <tex>L</tex> допускается машиной Тьюринга, то он допускается двухстековой машиной. <br>
Таким образом, мы с помощью двухстековой машины сымитировали МТ.
<tex>\Leftarrow)</tex> ОчевидноЭтот пункт доказательства аналогичен предыдущему. Содержимое двух стеков отображается лентой МТ также, как и в предыдущем пункте (рис. 2). Снятие, например, с первого стека символа соответствует сдвигу куска ленты, соответствующего второму стеку, влево на одну позицию, что прекрасно умеет делать МТ. Положить символ на этот стек соответствует сдвигу куска ленты, соответствующего второму стеку, вправо на одну позицию, записи этого символа на место начального положения головки и сдвигу головки вправо на одну позицию (действие "положить цепочку на стек" аналогично последовательности действий "положить на стек один символ"). Операции со вторым стеком имитируются аналогично.
}}
