Изменения

Для доказательства покажем, как имитировать <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> — <tex>k</tex>-е простое число. Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, а и использовать второй счётчик для временных вычислений. Тогда элементарные операции увеличения на <tex>k</tex>-счётчиковой машине реализуются следующим образом.*Увеличить <tex>i</tex>-й счётчик. Для этого необходимо умножить значение счётчика на <tex>p_i</tex>. *Уменьшить <tex>i</tex>-й счётчик. Для этого необходимо поделить значение счётчика на <tex>p_i</tex>.*Сравнить с нулём значение <tex>i</tex>-го счётчика. Для этого необходимо найти остаток от деления значения счетчика, уменьшения значения счетчика счётчика на <tex>p_i</tex> и проверки является ли счетчик сравнить его с нулём осуществляются на двухсчётчиковой машине при помощи операций .Операции умножения, деления и нахождения остатка от деления на соответствующее номеру счётчика простое число. Для этих вычислений и будет использоваться второй счётчикпри помощи двух счётчиков описаны в предыдущей лемме. Таким образом, для любого <tex>k</tex> и для любой <tex>k</tex>-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.

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