Изменения

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

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