Изменения

'''<tex>k</tex>-счётчиковой машиной ''' называется набор <tex>A=\langle\Sigma, Q, s\in Q, T \subset Q, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \{0,1\}^k \rightarrow Q \times \{ -1, 0, 1\}^k \rangle</tex>, где*<tex>\Sigma</tex> — {{---}} входной алфавит на ленте;*<tex>Q</tex> — {{---}} множество состояний автомата;*<tex>s</tex> — {{---}} стартовое состояние автомата;*<tex>T</tex> — {{---}} множество допускающих состояний автомата;

Для каждого счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить , является ли значение счетчика нулём.

Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть <tex>\Pi</tex> {{- --}} стековый алфавит, <tex>|\Pi|=P</tex>. Пронумеруем символы алфавита от <tex>0</tex> до <tex>P-1</tex>. Тогда стек можно рассматривать как целое число в системе счисления с основанием <tex>P</tex>.

*'''Снять символ со стека'''. Для того, чтобы снять символ , необходимо разделить число, которым представлен стек, на <tex>P</tex>, отбросив остаток. Пусть снимается *'''Добавить символ в стек'''. Для того, чтобы добавить символ с первого , необходимо умножить число, которым представлен стек, на <tex>P</tex> и прибавить к нему номер символа, который добавляется на стек.*'''Проверка верхнего символа стека'''. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик Для этого необходимо найти остаток от деления на <tex>P</tex>. Опишем реализацию арифметических операций с счётчиком, использованных при описании имитации работы двухстековой машины, при помощи двух счётчиков иуправляющего автомата.*'''Разделить значение первого счётчика на число <tex>C</tex>, если это удалось сделать, третий увеличивать на одинотбросив остаток. Эти действия будем повторять, пока ''' Пока первый счётчик не равен нулю, будем уменьшать его на один. Затем При этом после каждых <tex>C</tex> успешных уменьшений значения первого счётчика будем увеличивать на один значение второго счётчика. Далее скопируем значение с третьего второго счётчика на первый: пока третий второй счётчик не равен нулю, уменьшаем третий счётчик его значение и увеличиваем первыйзначение первого счётчика. Очевидно, что при фиксированном <tex>C</tex> для данной операции может быть построен управляющий автомат. *'''Добавить символ в стек'''. Для того, чтобы снять символ необходимо умножить Умножить значение первого счётчика на число, которым представлен стек, на <tex>PC</tex> и прибавить к нему номер символа, который добавляется на стек. Пусть снимается символ с первого стека. Тогда обнулим третий счётчик. ''' Будем уменьшать первый счётчик на один и увеличивать третий второй на <tex>PC</tex>. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего со второго счётчика на первый. Очевидно, что при фиксированном <tex>C</tex> для данной операции может быть построен управляющий автомат. * '''Проверка верхнего символа стекаУвеличить значение счётчика на <tex>C</tex>.'''Последовательно <tex>C</tex> раз увеличиваем значение счётчика на один. Для этого необходимо найти *'''Найти остаток от деления значения первого счётчика на число <tex>PC</tex>. Скопируем значение первого счётчика на третий. Реализуем при помощи введения дополнительных автоматов, входящих в управляющий ''' Рассмотрим автомат трехсчётчиковой машины. Этот автомат должен состоять из <tex>PC</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>. Будем уменьшать третий счетчик Таким образом, каждый раз переходя в следующее состояние автоматамы можем имитировать работу двухстековой машины на трёхсчётчиковой.

==Эквивалентность <tex>k</tex>-счётчиковой машины двухсчётчиковой машины трёхсчётчиковой ==

Для доказательства покажем, как имитировать <tex>k</tex>-счётчиковую машины на двухсчётчиковой. Пусть <tex>C_1, C_2, ...\ldots, C_k</tex> — {{---}} значения счётчиков <tex>k</tex>-счётчиковой машины. Тогда состояние <tex>k</tex>-счётчиковой машины можно охарактеризовать одним числом <tex>2^{C_1}*3\cdot3^{C_2}*...*\cdot \ldots \cdot p_k^{C_k}</tex>, где <tex>p_k</tex> — {{---}} <tex>k</tex>-е простое число.

*'''Увеличить <tex>i</tex>-й счётчик. ''' Для этого необходимо умножить значение счётчика на <tex>p_i</tex>. *'''Уменьшить <tex>i</tex>-й счётчик. ''' Для этого необходимо поделить значение счётчика на <tex>p_i</tex>.*'''Сравнить с нулём значение <tex>i</tex>-го счётчика. ''' Для этого необходимо найти остаток от деления значения счётчика на <tex>p_i</tex> и сравнить его с нулём.Операции умножения на константу, деления на константу и нахождения остатка от деления на константу значения счётчика при помощи двух счётчиков одного вспомогательного счётчика описаны в предыдущей лемме.

Утверждение теоремы очевидно следует из двух описанных выше лемм, и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]] и тезиса Тьюринга-Черча.

==См. также ==* [[Машина Тьюринга]]* [[Стековые машины, эквивалентность двухстековой машины МТ]] ==Источникиинформации ==