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