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