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

Материал из Викиконспекты
Версия от 02:05, 4 января 2012; 192.168.0.2 (обсуждение) (→‎Эквивалентность двухсчетчиковой машины машине Тьюринга)
Перейти к: навигация, поиск
Определение:
[math]k[/math]-счетчиковой машиной называется набор A=[math]\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]\forall k[/math] и для любой [math]k[/math]-счетчиковой машины [math]\exists[/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] - k-е простое число. Тогда любое состояние k-счетчиковой машины можно хранить на одном счетчике, а операции увеличения значения счетчика, уменьшения значения счетчика и проверки является ли счетчик нулем осуществляются на двухсчетчиковой машине при помощи операций умножения, деления и нахождения остатка от деления на соответствующее номеру счетчика простое число. Для этих вычислений и будет использоваться второй счетчик. Таким образом, [math]\forall k[/math] и для любой [math]k[/math]-счетчиковой машины [math]\exists[/math] эквивалентная ей двухсчетчиковая машина.
[math]\triangleleft[/math]
Теорема:
[math]\forall[/math] перечислимого языка [math]L[/math] [math]\exists[/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] - k-е простое число. Тогда любое состояние k-счетчиковой машины можно хранить на одном счетчике, а операции увеличения значения счетчика, уменьшения значения счетчика и проверки является ли счетчик нулем осуществляются на двухсчетчиковой машине при помощи операций умножения, деления и нахождения остатка от деления на соответствующее номеру счетчика простое число. Для этих вычислений и будет использоваться второй счетчик. Таким образом, [math]\forall k[/math] и для любой [math]k[/math]-счетчиковой машины [math]\exists[/math] эквивалентная ей двухсчетчиковая машина.
[math]\triangleleft[/math]

Источники

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Счетчиковые_машины,_эквивалентность_двухсчетчиковой_машины_МТ&oldid=15561»