1632
правки
Изменения
м
Так как [[Стековые машины, эквивалентность двухстековой машины МТ|двухстековая машина эквивалентна машине Тьюринга]], то достаточно <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>-стековая машина эквивалента по вычислительной мощности двухстековой, следовательно, любой язык, допускаемый трёхсчётчиковой машиной, допускается двухстековой машины существует эквивалентная ей трехсчетчиковая.
Утвердение Утверждение теоремы очевидно следует из двух описанных выше лемм, тезиса Тьюринга-Черча и [[Стековые машины, эквивалентность двухстековой машины МТ|эквивалентности двухстековой машины машине Тьюринга]].
rollbackEdits.php mass rollback
{{Определение
|definition=
'''<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> допускается двухстековой машиной Тьюринга тогда и только тогда, когда он допускается трехсчетчиковой трёхсчётчиковой машиной.
|proof=
}}
==Эквивалентность <tex>k</tex>-счётчиковой машины двухсчётчиковой ==
{{Лемма
|statement=Для любого <tex>\forall k</tex> и для любой <tex>k</tex>-счетчиковой счётчиковой машины <tex>\exists</tex> существует эквивалентная ей двухсчетчиковая двухсчётчиковая машина.
|proof=
Для доказательства покажем, как имитировать <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> двухсчетчиковая существует двухсчётчиковая машина, которая распознает этот язык.
|proof=
}}
==См. также ==* [[Машина Тьюринга]]* [[Стековые машины, эквивалентность двухстековой машины МТ]] ==Источникиинформации ==Джон * ''ХопкрофтД., Раджив МотваниР., Джеффри УльманД. '' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ.— Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.) [[Категория: Теория вычислимости]][[Категория: Вычислительные формализмы]]