Изменения
→Эквивалентность двухсчетчиковой машины машине Тьюринга
|proof=
Так как [[Стековые машины, эквивалентность двухстековой машины МТ|двухстековая машина эквивалентна машине Тьюринга]], то достаточно показать, что трехсчетчиковая машина эквивалентна по вычислительной мощности трехсчетчиковой машине.
Пусть стековая машина имеет стековый алфавит <tex>\Pi</tex>. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием <tex>|\Pi|</tex>. Пусть первому стеку соотвествует число на первом счетчике трехсчетчиковой машины, второму стеку - второе, а третий счетчик используется для временных вычислений.Тогда операции со стеком можно реализовать на трехсчетчиковой машине:*Добавление символа в стек: умножить значение счетчика на <tex>|\Pi|</tex> и прибавить число соответсвующее символу алфавита (цифре).*Удаление символа из стека: целочисленно разделить значение счетчика на <tex>|\Pi|</tex>.*Проверить верхний символ стека: найти остаток от деления значения счетчика на <tex>|\Pi|</tex>.
}}
==Источники==
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
