Изменения

'''<tex>k</tex>-счетчиковой счётчиковой машиной ''' называется набор A=<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>\delta</tex> — функция переходов, зависящая от символа на ленте, текущего состояния управляющего автомата и состояния счетчиков счётчиков и осуществляющая переход в автомата в новое состояние и изменение состояния счетчиковсчётчиков.Для каждого счетчика счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить , является ли значение счетчика нулемнулём.Будем считать, что значение нулевых счетчиков счётчиков уменьшать нельзя.

По сути, <tex>k</tex>-счетчиковая счётчиковая машина является [[Стековые машины, эквивалентность двухстековой машины МТ|<tex>k</tex>-стековой машиной]] с односимвольным алфавитом.

== Эквивалентность двухсчетчиковой двухстековой машины трёхсчётчикой машине Тьюринга ==

|statement=Язык <tex>L</tex> допускается двухстековой машиной Тьюринга тогда и только тогда, когда он допускается трехсчетчиковой трёхсчётчиковой машиной.

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

|statement=Для любого <tex>\forall k</tex> и для любой <tex>k</tex>-счетчиковой счётчиковой машины <tex>\exists</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>\forall k</tex> и для любой <tex>k</tex>-счетчиковой счётчиковой машины <tex>\exists</tex> существует эквивалентная ей двухсчетчиковая двухсчётчиковая машина.

|statement=<tex>\forall</tex> Для любого перечислимого языка <tex>L</tex> <tex>\exists</tex> двухсчетчиковая существует двухсчётчиковая машина, которая распознает этот язык.

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

==См. также ==* [[Машина Тьюринга]]* [[Стековые машины, эквивалентность двухстековой машины МТ]] ==Источникиинформации ==Джон * ''ХопкрофтД., Раджив МотваниР., Джеффри УльманД. '' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ.— Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.) [[Категория: Теория вычислимости]][[Категория: Вычислительные формализмы]]