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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эквивалентность двухсчетчиковой машины машине Тьюринга)
(Эквивалентность двухсчетчиковой машины машине Тьюринга)
Строка 17: Строка 17:
 
|proof=
 
|proof=
 
Так как [[Стековые машины, эквивалентность двухстековой машины МТ|двухстековая машина эквивалентна машине Тьюринга]], то достаточно показать, что трехсчетчиковая машина эквивалентна по вычислительной мощности трехсчетчиковой машине.
 
Так как [[Стековые машины, эквивалентность двухстековой машины МТ|двухстековая машина эквивалентна машине Тьюринга]], то достаточно показать, что трехсчетчиковая машина эквивалентна по вычислительной мощности трехсчетчиковой машине.
Пусть стековая машина имеет стековый алфавит <tex>\Pi</tex>. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием <tex>|\Pi|</tex>. Пусть первому стеку соотвествует число на первом счетчике трехсчетчиковой машины, второму стеку - второе, а третий счетчик используется для временных вычислений.  
+
Пусть стековая машина имеет стековый алфавит <tex>\Pi</tex>. Тогда любое из состояний стеков можно считать числом в системе счисления с основанием <tex>|\Pi|</tex>. Пусть первому стеку соотвествует число на первом счетчике трехсчетчиковой машины, второму стеку - второе, а третий счетчик используется для временных вычислений.
 +
Тогда операции со стеком можно реализовать на трехсчетчиковой машине:
 +
*Добавление символа в стек: умножить значение счетчика на <tex>|\Pi|</tex> и прибавить число соответсвующее символу алфавита (цифре).
 +
*Удаление символа из стека: целочисленно разделить значение счетчика на <tex>|\Pi|</tex>.
 +
*Проверить верхний символ стека: найти остаток от деления значения счетчика на <tex>|\Pi|</tex>.
 
}}
 
}}
  
 
==Источники==
 
==Источники==
 
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
 
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.

Версия 21:06, 3 января 2012

Определение:
[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].
[math]\triangleleft[/math]

Источники

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