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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эквивалентность двухсчетчиковой машины машине Тьюринга)
(Эквивалентность двухсчетчиковой машины машине Тьюринга)
Строка 13: Строка 13:
  
 
== Эквивалентность двухсчетчиковой машины машине Тьюринга ==
 
== Эквивалентность двухсчетчиковой машины машине Тьюринга ==
{{Лемма
+
{{Лемма 1
 
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается трехсчетчиковой машиной.
 
|statement=Язык <tex>L</tex> допускается машиной Тьюринга тогда и только тогда, когда он допускается трехсчетчиковой машиной.
 
|proof=
 
|proof=

Версия 21:24, 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]n[/math] в перестановке не является подвижным элементом тогда и толко тогда когда первая компонента перестановки есть (n, ←) или последняя

Источники

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