Изменения
→Эквивалентность двухстековой машины трёхсчётчикой машине
|statement=Язык <tex>L</tex> допускается двухстековой машиной тогда и только тогда, когда он допускается трёхсчётчиковой машиной.
|proof=
<tex>Leftarrow</tex>Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть <tex>\Pi</tex> - стековый алфавит <tex>, |\Pi|=P</tex>. Пронумеруем символы алфавита от <tex>0</tex> до <tex>P</tex>. Тогда стек можно рассматривать как целое число в системе счисления с основанием <tex>P</tex>.Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа операций: положить символ в стек, снять символ со стека, проверить верхний символ стека.Рассмотрим реализацию этих операция на трёхсчётчиковой машине.***
}}
