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