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

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

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

[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]P[/math]. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый. Проверка верхнего символа стека. Для этого необходимо найти остаток от деления на [math]P[/math]. Скопируем значение первого счётчика на третий. При помощи конечного автомата можно хранить целое число, принадлежащее конечному интервалу (каждое состояние автомата соответствует некоторому значению числа). Будем хранить остаток от деления третьего счётчика на [math]P[/math]. Изначально инициализируем хранимое значение нулём. Пока третий счетчик не нуль, будем увеличивать по модулю [math]P[/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}*3^{C_2}*...*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 (рус.)