36
правок
Изменения
→Эквивалентность k-счётчиковой машины двухсчётчиковой
|statement=Для любого <tex>k</tex> и для любой <tex>k</tex>-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
|proof=
Для доказательства покажем, как имитировать <tex>k</tex>-счётчиковую машины на двухсчётчиковой. Пусть <tex>C_1, C_2, \ldots, C_k</tex> — {{---}} значения счётчиков <tex>k</tex>-счётчиковой машины. Тогда состояние <tex>k</tex>-счётчиковой машины можно охарактеризовать одним числом <tex>2^{C_1}\cdot3^{C_2}\cdot \ldots \cdot p_k^{C_k}</tex>, где <tex>p_k</tex> {{---}} <tex>k</tex>-е простое число.
Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, и использовать второй счётчик для временных вычислений.
