Изменения

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

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

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