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