Изменения

Пусть стековая машина имеет стековый алфавит <tex>\Pi</tex>. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием <tex>|\Pi|</tex>. Пусть первому стеку соотвествует соответствует число на первом счетчике трехсчетчиковой машины, второму стеку - второе, а третий счетчик используется для временных вычислений.

*Добавление символа в стек: умножить значение счетчика на <tex>|\Pi|</tex> и прибавить число соответсвующее , соответствующее символу алфавита (цифре).

'''while''' (перый первый счетчик не ноль)

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

Пусть <tex>C_1, C_2, ..., C_k</tex> - значения счетчиков <tex>k</tex>-счетчиковой машины. Тогда состояние <tex>k</tex>-счетчиковой машины можно охарктеризовать охарактеризовать одним числом <tex>2^{C_1}*3^{C_2}*...*p_k^{C_k}</tex>, где <tex>p_k</tex> - k-е простое число. Тогда любое состояние k-счетчиковой машины можно хранить на одном счетчике, а операции увеличения значения счетчика, уменьшения значения счетчика и проверки является ли счетчик нулем осуществляются на двухсчетчиковой машине при помощи операций умножения, деления и нахождения остатка от деления на соответствующее номеру счетчика простое число. Для этих вычислений и будет использоваться второй счетчик. Таким образом, <tex>\forall k</tex> и для любой <tex>k</tex>-счетчиковой машины <tex>\exists</tex> эквивалентная ей двухсчетчиковая машина.

Утвердение Утверждение теоремы очевидно следует из двух описанных выше лемм, тезиса Тьюринга-Черча и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]].