Изменения

На рис. 1 изображена '''k-стековая машина'''. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> — текущий считываемый символ). Для каждого стека с вершины снимается символ <tex>x_i</tex>. Вместо , вместо него помещается строка <tex>\alpha_i</tex> таким образом, чтобы первый символ строки находился на вершине стекаи делается переход в автомате в зависимости от считанного с ленты символа <tex>c_i</tex> и снятых со стеков верхних значений <tex>x_i</tex>.

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