Изменения
→Эквивалентность двухсчетчиковой машины машине Тьюринга
|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=
Пусть <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> эквивалентная ей двухсчетчиковая машина.
}}
==Источники==
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
