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