3622
правки
Изменения
м
→Эквивалентность двухстековой машины трёхсчётчикой машине
*'''Умножить значение первого счётчика на число <tex>C</tex>.''' Будем уменьшать первый счётчик на один и увеличивать второй на <tex>C</tex>. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение со второго счётчика на первый. Очевидно, что при фиксированном <tex>C</tex> для данной операции может быть построен управляющий автомат.
*'''Увеличить значение счётчика на <tex>C</tex>.''' Последовательно <tex>C</tex> раз увеличиваем значение счётчика на один.
*'''Найти остаток от деления значения первого счётчика на число <tex>C</tex>.''' Рассмотрим автомат их из <tex>C</tex> состояний. Пронумеруем состояние от <tex>0</tex> до <tex>C-1</tex>. Пусть <tex>0</tex> - стартовое состояние автомата. Скопируем значение с первого счётчика на второй. В случае если второй счётчик не нуль, автомат осуществляет переход из состояния <tex>i</tex> в состояние <tex>i+1</tex> (из состояния с номером <tex>C-1</tex> осуществляется переход в состояние с номером <tex>0</tex>), при этом значение второго счётчика уменьшается на один, а первого — увеличивается на один. Ясно, что в момент, когда третий счётчик станет равен нулю, управляющий автомат окажется в состоянии с номером, равным остатку от деления значения первого счётчика на <tex>C</tex>.
Таким образом, мы можем имитировать работу двухстековой машины на трёхсчётчиковой.
