Изменения
→Эквивалентность двухсчетчиковой машины машине Тьюринга
}
Аналогично реализуются остальные стековые операции. Такм образом получили, что для люьой опреации с двухстековой машиной сществует эквивалентная операция с трехсчтечиковой машиной. Так как стековый алфавит конечен, то и управляющий автомат эквивалентной трехсчетчиковой машины будет иметь конечное число состояний. То есть для любой двухстековой машины существует эквивалентная ей трехсчетчиковая.
}}
{{Лемма
|statement=<tex>\forall k</tex> и для любой <tex>k</tex>-счетчиковй машины <tex>\exists</tex> эквивалентная ей двухсчетчиковая машина.
|proof=
}}
==Источники==
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
