Изменения

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

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

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