Изменения
→Эквивалентность двухсчетчиковой машины машине Тьюринга
{{Лемма
|statement=<tex>\forall k</tex> и для любой <tex>k</tex>-счетчиковой машины <tex>\exists</tex> существует эквивалентная ей двухсчетчиковая машина.
|proof=
Пусть <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> эквивалентная ей двухсчетчиковая машина.
{{Теорема
|statement=<tex>\forall</tex> Для любого перечислимого языка <tex>L</tex> <tex>\exists</tex> существует двухсчетчиковая машина, которая распознает этот язык.
|proof=
Утверждение теоремы очевидно следует из двух описанных выше лемм, тезиса Тьюринга-Черча и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]].
