Счётчиковые машины
| Определение: |
[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]\Rightarrow[/math]
Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть [math]\Pi[/math] - стековый алфавит, [math]|\Pi|=P[/math]. Пронумеруем символы алфавита от [math]0[/math] до [math]P-1[/math]. Тогда стек можно рассматривать как целое число в системе счисления с основанием [math]P[/math].
Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине.
- Снять символ со стека. Для того, чтобы снять символ, необходимо разделить число, которым представлен стек, на [math]P[/math], отбросив остаток.
- Добавить символ в стек. Для того, чтобы добавить символ, необходимо умножить число, которым представлен стек, на [math]P[/math] и прибавить к нему номер символа, который добавляется на стек.
- Проверка верхнего символа стека. Для этого необходимо найти остаток от деления на [math]P[/math].
Опишем реализацию арифметических операций с счётчиком, использованных при описании имитации работы двухстековой машины, при помощи двух счётчиков и управляющего автомата.
- Разделить значение первого счётчика на число [math]C[/math], отбросив остаток. Пока первый счётчик не равен нулю, будем уменьшать его на один. При этом после каждых [math]C[/math] успешных уменьшений значения первого счётчика будем увеличивать на один значение второго счётчика. Далее скопируем значение второго счётчика на первый: пока второй счётчик не равен нулю, уменьшаем его значение и увеличиваем значение первого счётчика. Очевидно, что при фиксированном [math]C[/math] для данной операции может быть построен управляющий автомат.
- Умножить значение первого счётчика на число [math]C[/math]. Будем уменьшать первый счётчик на один и увеличивать второй на [math]C[/math]. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение со второго счётчика на первый. Очевидно, что при фиксированном [math]C[/math] для данной операции может быть построен управляющий автомат.
- Увеличить значение счётчика на [math]C[/math]. Последовательно [math]C[/math] раз увеличиваем значение счётчика на один.
- Найти остаток от деления значения первого счётчика на число [math]C[/math]. Рассмотрим автомат их [math]C[/math] состояний. Пронумеруем состояние от [math]0[/math] до [math]C-1[/math]. Пусть [math]0[/math] - стартовое состояние автомата. Скопируем значение с первого счётчика на второй. В случае если второй счётчик не нуль, автомат осуществляет переход из состояния [math]i[/math] в состояние [math]i+1[/math] (из состояния с номером [math]C-1[/math] осуществляется переход в состояние с номером [math]0[/math]), при этом значение второго счётчика уменьшается на один, а первого — увеличивается на один. Ясно, что в момент, когда третий счётчик станет равен нулю, управляющий автомат окажется в состоянии с номером, равным остатку от деления значения первого счётчика на [math]C[/math].
Таким образом, мы можем имитировать работу двухстековой машины на трёхсчётчиковой.
[math]\Leftarrow[/math]
Трёхсчётчиковая машина является частным случаем трёхстековой машины, а любая [math]k[/math]-стековая машина эквивалента по вычислительной мощности двухстековой, следовательно, любой язык, допускаемый трёхсчётчиковой машиной, допускается двухстековой. |
| [math]\triangleleft[/math] |
Эквивалентность [math]k[/math]-счётчиковой машины двухсчётчиковой
| Лемма: |
Для любого [math]k[/math] и для любой [math]k[/math]-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Для доказательства покажем, как имитировать [math]k[/math]-счётчиковую машины на двухсчётчиковой. Пусть [math]C_1, C_2, ..., C_k[/math] — значения счётчиков [math]k[/math]-счётчиковой машины. Тогда состояние [math]k[/math]-счётчиковой машины можно охарактеризовать одним числом [math]2^{C_1}\cdot3^{C_2}\cdot...\cdot p_k^{C_k}[/math], где [math]p_k[/math] — [math]k[/math]-е простое число.
Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, и использовать второй счётчик для временных вычислений.
Тогда элементарные операции на [math]k[/math]-счётчиковой машине реализуются следующим образом.
- Увеличить [math]i[/math]-й счётчик. Для этого необходимо умножить значение счётчика на [math]p_i[/math].
- Уменьшить [math]i[/math]-й счётчик. Для этого необходимо поделить значение счётчика на [math]p_i[/math].
- Сравнить с нулём значение [math]i[/math]-го счётчика. Для этого необходимо найти остаток от деления значения счётчика на [math]p_i[/math] и сравнить его с нулём.
Операции умножения на константу, деления на константу и нахождения остатка от деления на константу значения счётчика при помощи одного вспомогательного счётчика описаны в предыдущей лемме.
Таким образом, для любого [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 (рус.)
