Изменения

По сути, <tex>k</tex>-счетчиковая машина является [[Стековые машины, эквивалентность двухстековой машины МТ|<tex>k</tex>-стековой машиной ]] с односимвольным алфавитом.

== Эквивалентность двухстековой двухсчетчиковой машины машине Тьюринга =={{ТеоремаЛемма|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается двухстековой трехсчетчиковой машиной.

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