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

Счётчиковые машины

Определение:

$k$-счётчиковой машиной называется набор $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$, где $\Sigma$ — входной алфавит на ленте; $Q$ — множество состояний автомата; $s$ — стартовое состояние автомата; $T$ — множество допускающих состояний автомата; $\delta$ — функция переходов, зависящая от символа на ленте, текущего состояния управляющего автомата и состояния счётчиков и осуществляющая переход в автомата в новое состояние и изменение состояния счётчиков. Для каждого счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить, является ли значение счетчика нулём. Будем считать, что значение нулевых счётчиков уменьшать нельзя.

По сути, $k$-счётчиковая машина является $k$-стековой машиной с односимвольным алфавитом.

Эквивалентность двухстековой машины трёхсчётчикой машине

Лемма:

Язык $L$ допускается двухстековой машиной тогда и только тогда, когда он допускается трёхсчётчиковой машиной.

Доказательство:

$\triangleright$

$\Rightarrow$ Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть $\Pi$ - стековый алфавит, $|\Pi|=P$. Пронумеруем символы алфавита от $0$ до $P-1$. Тогда стек можно рассматривать как целое число в системе счисления с основанием $P$. Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине. Снять символ со стека. Для того, чтобы снять символ, необходимо разделить число, которым представлен стек, на $P$, отбросив остаток. Добавить символ в стек. Для того, чтобы добавить символ, необходимо умножить число, которым представлен стек, на $P$ и прибавить к нему номер символа, который добавляется на стек. Проверка верхнего символа стека. Для этого необходимо найти остаток от деления на $P$. Опишем реализацию арифметических операций с счётчиком, использованных при описании имитации работы двухстековой машины, при помощи двух счётчиков и управляющего автомата. Разделить значение первого счётчика на число $C$, отбросив остаток. Пока первый счётчик не равен нулю, будем уменьшать его на один. При этом после каждых $C$ успешных уменьшений значения первого счётчика будем увеличивать на один значение второго счётчика. Далее скопируем значение второго счётчика на первый: пока второй счётчик не равен нулю, уменьшаем его значение и увеличиваем значение первого счётчика. Очевидно, что при фиксированном $C$ для данной операции может быть построен управляющий автомат. Умножить значение первого счётчика на число $C$. Будем уменьшать первый счётчик на один и увеличивать второй на $C$. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение со второго счётчика на первый. Очевидно, что при фиксированном $C$ для данной операции может быть построен управляющий автомат. Увеличить значение счётчика на $C$. Последовательно $C$ раз увеличиваем значение счётчика на один. Найти остаток от деления значения первого счётчика на число $C$. Рассмотрим автомат из $C$ состояний. Пронумеруем состояние от $0$ до $C-1$. Пусть $0$ - стартовое состояние автомата. Скопируем значение с первого счётчика на второй. В случае если второй счётчик не нуль, автомат осуществляет переход из состояния $i$ в состояние $i+1$ (из состояния с номером $C-1$ осуществляется переход в состояние с номером $0$), при этом значение второго счётчика уменьшается на один, а первого — увеличивается на один. Ясно, что в момент, когда третий счётчик станет равен нулю, управляющий автомат окажется в состоянии с номером, равным остатку от деления значения первого счётчика на $C$. Таким образом, мы можем имитировать работу двухстековой машины на трёхсчётчиковой. $\Leftarrow$ Трёхсчётчиковая машина является частным случаем трёхстековой машины, а любая $k$-стековая машина эквивалента по вычислительной мощности двухстековой, следовательно, любой язык, допускаемый трёхсчётчиковой машиной, допускается двухстековой.

$\triangleleft$

Эквивалентность $k$-счётчиковой машины двухсчётчиковой

Лемма:

Для любого $k$ и для любой $k$-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.

Доказательство:

$\triangleright$

Для доказательства покажем, как имитировать $k$-счётчиковую машины на двухсчётчиковой. Пусть $C_1, C_2, ..., C_k$ — значения счётчиков $k$-счётчиковой машины. Тогда состояние $k$-счётчиковой машины можно охарактеризовать одним числом $2^{C_1}\cdot3^{C_2}\cdot...\cdot p_k^{C_k}$, где $p_k$ — $k$-е простое число. Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, и использовать второй счётчик для временных вычислений. Тогда элементарные операции на $k$-счётчиковой машине реализуются следующим образом. Увеличить $i$-й счётчик. Для этого необходимо умножить значение счётчика на $p_i$. Уменьшить $i$-й счётчик. Для этого необходимо поделить значение счётчика на $p_i$. Сравнить с нулём значение $i$-го счётчика. Для этого необходимо найти остаток от деления значения счётчика на $p_i$ и сравнить его с нулём. Операции умножения на константу, деления на константу и нахождения остатка от деления на константу значения счётчика при помощи одного вспомогательного счётчика описаны в предыдущей лемме. Таким образом, для любого $k$ и для любой $k$-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.

$\triangleleft$

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

Теорема:

Для любого перечислимого языка $L$ существует двухсчётчиковая машина, которая распознает этот язык.

Доказательство:

$\triangleright$

Утверждение теоремы очевидно следует из двух описанных выше лемм и эквивалентности двухстековой машины машине Тьюринга.

$\triangleleft$

Источники информации

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