Изменения

'''<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> — {{---}} множество допускающих состояний автомата;

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

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

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

Так как [[Стековые машины, эквивалентность двухстековой машины МТ|двухстековая машина эквивалентна машине Тьюринга]], то достаточно показать, что трехсчётчиковая машина эквивалентна по вычислительной мощности двухстековой машине.Пусть стековая машина имеет стековый алфавит <tex>\PiRightarrow</tex>. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием <tex>|\Pi|</tex>. Пусть первому стеку соответствует число на первом счётчике трехсчётчиковой машины, второму стеку — второе, а третий счётчик используется для временных вычислений.Тогда операции со стеком можно реализовать на трехсчётчиковой машине:*добавление символа в стек: умножить значение счётчика на <tex>|\Pi|</tex> и прибавить число, соответствующее символу алфавита (цифре);*удаление символа из стека: целочисленно разделить значение счётчика на <tex>|\Pi|</tex>;*проверить верхний символ стека: найти остаток от деления значения счётчика на <tex>|\Pi|</tex>.Все эти элементарные операции очевидно реализуются при помощи третьего счётчика. Например, рассмотрим операцию добавления символа в стек. Напишем программу для трехсчётчиковой машины, реализующую эту операцию. '''while''' (первый счётчик не ноль) { '''for''' (i = 0; i < <tex>|\Pi|</tex>; ++i) увеличить третий счётчик; уменьшить первый счётчик; } '''for''' (i = 0; i < номер добавляемого символа в алфавите; ++i) увеличить третий счётчик; '''while''' (третий счётчик не ноль) { уменьшить третий счётчик; увеличить первый счётчик; }

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

Для доказательства покажем, как имитировать <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>-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.

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

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