Изменения
→Эквивалентность двухсчетчиковой машины машине Тьюринга
увеличить первый счётчик;
}
По данной программе легко восстановить управляющий автомат счётчиковой машины, поскольку выполнение подпрограммы в псевдокоде зависит только от констант и значений счетчиков.
Аналогично реализуются остальные стековые операции. Таким образом получили, что для любой операции с двухстековой машиной существует эквивалентная операция с трехсчётчиковой машиной. Так как стековый алфавит конечен, то и управляющий автомат эквивалентной трехсчётчиковой машины будет иметь конечное число состояний. То есть для любой двухстековой машины существует эквивалентная ей трехсчётчиковая.
}}
