Изменения

|statement=Для любого <tex>\forall k</tex> и для любой <tex>k</tex>-счетчиковой машины существует эквивалентная ей двухсчетчиковая машина.

Пусть <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>-счетчиковой машины существует эквивалентная ей двухсчетчиковая машина.