Таким образом, мы с помощью двухстековой машины сымитировали МТ.
[[Изображение:SMM.png|400px|thumb|left|Рис. 3. Представление двух стеков лентой МТ]]<tex>\Leftarrow)</tex> Докажем, что если язык <tex>L</tex> допускается двухстековой машиной, то он допускается машиной ТьюрингаОчевидно. <br> Двухстековую машину можно сымитировать трехленточной МТ (Рис. 3). На первой ленте будет записан вход, вторая лента будет имитировать первый стек, третья — второй. <br>Стеки имитируются Конечный автомат для МТ получим из двухстековой машины следующей заменой действия на переходе:
}}
