По сути, <tex>k</tex>-счётчиковая машина является [[Стековые машины, эквивалентность двухстековой машины МТ|<tex>k</tex>-стековой машиной]] с односимвольным алфавитом.
== Эквивалентность двухсчетчиковой двухстековой машины трёхсчётчикой машине Тьюринга ==
{{Лемма
|statement=Язык <tex>L</tex> допускается двухстековой машиной Тьюринга тогда и только тогда, когда он допускается трехсчётчиковой трёхсчётчиковой машиной.
|proof=
Так как [[Стековые машины, эквивалентность двухстековой машины МТ|двухстековая машина эквивалентна машине Тьюринга]], то достаточно показать, что трехсчётчиковая машина эквивалентна по вычислительной мощности двухстековой машине.
Пусть стековая машина имеет стековый алфавит <tex>\Pi</tex>. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием <tex>|\Pi|</tex>. Пусть первому стеку соответствует число на первом счётчике трехсчётчиковой машины, второму стеку — второе, а третий счётчик используется для временных вычислений.
Тогда операции со стеком можно реализовать на трехсчётчиковой машине:
*добавление символа в стек: умножить значение счётчика на <tex>|\Pi|</tex> и прибавить число, соответствующее символу алфавита (цифре);
*удаление символа из стека: целочисленно разделить значение счётчика на <tex>|\Pi|</tex>;
*проверить верхний символ стека: найти остаток от деления значения счётчика на <tex>|\Pi|</tex>.
Все эти элементарные операции очевидно реализуются при помощи третьего счётчика. Например, рассмотрим операцию добавления символа в стек. Напишем программу для трехсчётчиковой машины, реализующую эту операцию.
'''while''' (первый счётчик не ноль)
{
'''for''' (i = 0; i < <tex>|\Pi|</tex>; ++i)
увеличить третий счётчик;
уменьшить первый счётчик;
}
'''for''' (i = 0; i < номер добавляемого символа в алфавите; ++i)
увеличить третий счётчик;
'''while''' (третий счётчик не ноль)
{
уменьшить третий счётчик;
увеличить первый счётчик;
}
По данной программе легко восстановить управляющий автомат счётчиковой машины, поскольку выполнение подпрограммы, описанной выше, зависит только от констант и значений счётчиков.
Аналогично реализуются остальные стековые операции. Таким образом получили, что для любой операции с двухстековой машиной существует эквивалентная операция с трехсчётчиковой машиной. Так как стековый алфавит конечен, то и управляющий автомат эквивалентной трехсчётчиковой машины будет иметь конечное число состояний. То есть для любой двухстековой машины существует эквивалентная ей трехсчётчиковая.
}}
==Эквивалентность двухсчётчиковой машины трёхсчётчиковой ==
{{Лемма
|statement=Для любого <tex>k</tex> и для любой <tex>k</tex>-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
