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

Материал из Викиконспекты
Версия от 01:32, 24 января 2012; 192.168.0.2 (обсуждение) (Эквивалентность двухсчетчиковой машины машине Тьюринга)
Перейти к: навигация, поиск
Определение:
[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]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]

Источники

  • Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)