Редактирование: Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 18: | Строка 18: | ||
<tex>\Rightarrow</tex> | <tex>\Rightarrow</tex> | ||
− | Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть <tex>\Pi</tex> | + | Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть <tex>\Pi</tex> - стековый алфавит, <tex>|\Pi|=P</tex>. Пронумеруем символы алфавита от <tex>0</tex> до <tex>P-1</tex>. Тогда стек можно рассматривать как целое число в системе счисления с основанием <tex>P</tex>. |
Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине. | Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине. | ||
Строка 29: | Строка 29: | ||
*'''Умножить значение первого счётчика на число <tex>C</tex>.''' Будем уменьшать первый счётчик на один и увеличивать второй на <tex>C</tex>. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение со второго счётчика на первый. Очевидно, что при фиксированном <tex>C</tex> для данной операции может быть построен управляющий автомат. | *'''Умножить значение первого счётчика на число <tex>C</tex>.''' Будем уменьшать первый счётчик на один и увеличивать второй на <tex>C</tex>. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение со второго счётчика на первый. Очевидно, что при фиксированном <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>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>. |
Таким образом, мы можем имитировать работу двухстековой машины на трёхсчётчиковой. | Таким образом, мы можем имитировать работу двухстековой машины на трёхсчётчиковой. |