Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ

Определение:

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

По сути, [math]k[/math]-счётчиковая машина является [math]k[/math]-стековой машиной с односимвольным алфавитом.

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

Лемма:

Язык [math]L[/math] допускается машиной Тьюринга тогда и только тогда, когда он допускается трехсчётчиковой машиной.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма:

Для любого [math]k[/math] и для любой [math]k[/math]-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.

Доказательство:

[math]\triangleright[/math]

Пусть [math]C_1, C_2, ..., C_k[/math] — значения счётчиков [math]k[/math]-счётчиковой машины. Тогда состояние [math]k[/math]-счётчиковой машины можно охарактеризовать одним числом [math]2^{C_1}*3^{C_2}*...*p_k^{C_k}[/math], где [math]p_k[/math] — [math]k[/math]-е простое число. Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, а операции увеличения значения счетчика, уменьшения значения счетчика и проверки является ли счетчик нулём осуществляются на двухсчётчиковой машине при помощи операций умножения, деления и нахождения остатка от деления на соответствующее номеру счётчика простое число. Для этих вычислений и будет использоваться второй счётчик. Таким образом, для любого [math]k[/math] и для любой [math]k[/math]-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.

[math]\triangleleft[/math]

Теорема:

Для любого перечислимого языка [math]L[/math] существует двухсчётчиковая машина, которая распознает этот язык.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Источники

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.