close

Вход

Забыли?

вход по аккаунту

?

Вычислительные возможности односторонних машин Тьюринга с сублогарифмическими ограничениями на память.

код для вставкиСкачать
Известия вузов. Математика
2014, № 9, c. 80–86
http://old.kpfu.ru/journals/izv_vuz/
e-mail: izvuz.matem@kpfu.ru
Краткое сообщение, представленное Н.К. Замовым
А.Н. ЛЕЩЕВ
ВЫЧИСЛИТЕЛЬНЫЕ ВОЗМОЖНОСТИ ОДНОСТОРОННИХ МАШИН
ТЬЮРИНГА С СУБЛОГАРИФМИЧЕСКИМИ ОГРАНИЧЕНИЯМИ
НА ПАМЯТЬ
Аннотация. В статье рассматривается известная модель машины Тьюринга — недетерминированная односторонняя машина Тьюринга. Доказывается существование невырожденных
(нерегулярных) классов сложности языков, распознаваемых недетерминированными односторонними машинами Тьюринга с сублогарифмическими ограничениями на память. Показывается, что соответствующие классы сложности образуют строгую иерархию. Для доказательства иерархии определяется семейство языков специального вида и доказываются некоторые
их свойства.
Ключевые слова: односторонняя машина Тьюринга, недетерминированная машина Тьюринга, ограничение на память.
УДК: 519.7
1. Введение
В основе данной статьи лежат известные сложностные характеристики машин Тьюринга
— время работы машины T (n) и необходимая память для работы машины S(n), а также соответствующие им классы сложности SPACE(S(n)) и TIME(T (n)). Отметим, что эти
классы сложности и их модификации определены в [1].
SPACE(S(n)) — класс языков, распознаваемых машинами Тьюринга, использующими
для этого не более, чем S(n) ячеек памяти, где n — длина входного слова. Аналогично, TIME(T (n)) — класс языков, распознаваемых машинами Тьюринга, время работы которых ограничено T (n) операциями. Вопрос о взаимоотношении классов SPACE(S(n)) и
TIME(T (n)) при различных видах функций S(n) и T (n) не является полностью разрешенным. Так в настоящей статье рассматривается поведение классов сложности SPACE(sk (n)),
где sk (n) = log(k) n ≡ log . . . log n при T (n) = n. Отметим также, что машины Тьюринга с
k
ограничением на время работы T (n) = n называются односторонними машинами Тьюринга.
Поступила 01.04.2014
80
ВЫЧИСЛИТЕЛЬНЫЕ ВОЗМОЖНОСТИ ОДНОСТОРОННИХ МАШИН ТЬЮРИНГА
81
2. Предварительная информация
Детерминированный вариант односторонней машины Тьюринга впервые был представлен в [2]. Для некоторой константы k ≥ 1 односторонняя машина Тьюринга — это детерминированная (k + 1)-ленточная машина Тьюринга (с k рабочими лентами и одной входной),
причем на каждом такте работы читающая головка входной ленты всегда сдвигается на
одну позицию вправо:
M = (K, Σ, δ, s0 ),
где Σ — алфавит входной последовательности. Также, без потери общности, можно считать,
что алфавиты рабочих лент совпадают с Σ; s0 — начальное состояние машины (s0 ∈ Kp );
K — множество состояний управляющего устройства машины; δ — функция переходов
машины, определяемая следующим образом: δ : (K × Σ × Σk ) → (K) × ({R, L, N }k × Σk ).
Будем говорить, что слово w из Σ∗ принимается односторонней машиной M , если M
заканчивает его обработку в принимающем состоянии, и слово v из Σ∗ отвергается односторонней машиной M , если M заканчивает его обработку в отвергающем состоянии.
Язык L над алфавитом Σ распознается односторонней машиной M , если после обработки
любого слова w из языка L машина M останавливается в принимающем состоянии, а после
обработки слов v не из L — в отвергающем состоянии.
Определение 2.1. R — класс языков, распознаваемых односторонними машинами.
Недетерминированная модель односторонней машины и соответствующий класс сложности были впервые представлены в [3].
Будем говорить, что слово w из Σ∗ принимается недетерминированной односторонней машиной M , если существует вариант обработки слова w машиной M , когда она заканчивает
работу в принимающем состоянии, и слово v из Σ∗ отвергается односторонней машиной M ,
если такого варианта обработки нет.
Язык L над алфавитом Σ распознается недетерминированной односторонней машиной
M , если машина M принимает любое слово из языка L и отвергает все слова, не содержащиеся в L.
Определение 2.2. Q+ — класс языков, распознаваемых недетерминированными односторонними машинами.
Недетерминированная модель односторонней машины с ограничением на недетерминизм
и соответствующие классы сложности были впервые представлены в [4].
Определение 2.3. Qg(n) — класс языков, распознаваемых односторонними машинами,
совершающими не более, чем g(n) недетерминированных шагов. Другими словами, если
L ∈ Qg(n) , то существует машина M , распознающая L, определяющая принадлежность
языку L любого слова w длины n, совершая не более, чем g(n) недетерминированных шагов.
В частности, Qg(n) ≡ Q0 , в случае, если g(n) = const [4]; R ≡ Q0 ; Q+ ≡ Qn .
Одним из основных результатов [4] было установление свойства, что для семейства
{gk (n)}∞
k=0 функций, связанных отношением gi (n) = o(gj (n)) при i > j и gi (n) = o(n)
для всех i, выполняется
· · · Qgk+1(n) Qgk (n) Qgk−1 (n) · · · Qg0 (n) · · · .
(1)
В частности, для семейства функций gk = log(k) n ≡ log . . . log n, g0 (n) = n и g∞ (n) = const
k
справедливо
R ≡ Q0 · · · Qlog
(k+1)
n
Qlog
(k)
n
· · · Qlog
(1)
n
⊆ Qn ≡ Q+ .
(2)
82
А.Н. ЛЕЩЕВ
Техника доказательств соотношений классов сложности односторонних машин, разработанная в [4], активно используется в последнее время в получении новых результатов для
других вычислительных моделей. Так, например, в [5] для односторонних машин доказывается существование бесконечной иерархии по числу используемых рабочих лент. В [6]
обобщается результат [4] для моделей машин Тьюринга, работающих линейное время. В [7]
рассматривается связь между односторонними машнами Тьюринга и различными моделями для распознавания ω-языков. Так же одним из результатов [8] является утверждение о
том, что односторонние машины не могут распознавать нерегулярные языки при сублинейных ограничениях на память.
В настоящей статье рассматривается новая модификация односторонней машины Тьюринга, при которой недостаток вычислительных возможностей при ограничениях на память
компенсируется введением в модель неоднородности в виде слабой подсказки. Далее на основе результатов [4] доказывается существование бесконечной иерархии классов сложности,
соответствующих новым машинам, по числу недетерминированных операций.
3. Введение ограничений на память
Определение 3.1. SPACEg(n) (f (n)) — класс языков распознаваемых односторонними машинами, совершающими не более, чем g(n) недетерминированных шагов и использующими
не более, чем O(f (n)) памяти.
Понятно, что ограничивающая память функция f (n) выбирается не произвольно. Естественным ограничением сверху для этой функции будет kn, где k — количество рабочих
лент машины, так как время работы односторонней машины всегда равно n шагам. С другой стороны, в [9] было доказано, что в случае с односторонними машинами Тьюринга
сублогарифмическое ограничение на память f (n) = o(log n) приводит к вырождению соответсвующего класса сложности SPACEg(n) (f (n)) до класса регулярных языков Reg.
Модифицируем модель односторонней машины, чтобы скомпенсировать потерю мощности при ограниченной памяти.
Определение 3.2. Будем говорить, что недетерминированная односторонняя машина Тьюринга M использует слабую подсказку (unary advice) длины s, если к моменту начала работы
машины M на входном слове w на всех ее рабочих лентах размечена и заполнена одним
специальным символом область размера не более, чем s ячеек.
g(n)
Определение 3.3. SPACEu (f (n)) — класс языков распознаваемых односторонними машинами, совершающими не более чем g(n) недетерминированных шагов и использующими
не более, чем f (n) ячеек на каждой из своих рабочих лент, со слабой подсказкой размера
не более, чем f (n).
Определение 3.4. SPACE+
u (f (n)) — класс языков распознаваемых односторонними машинами, использующими не более, чем f (n) ячеек на каждой из своих рабочих лент, со
слабой подсказкой размера не более, чем f (n), без ограничения на количество недетерминированных шагов.
Определение 3.5. Будем называть совокупность содержимого всех рабочих лент и внутреннего состояния односторонней машины Тьюринга M во время i-го такта образом M i-го
такта.
Рассмотрим работу односторонней машины со слабой подсказкой M с g(n)-ограничением
на недетерминизм и f (n)-ограничением на память на некотором слове x длины n. Предположим, что машина M имеет k рабочих лент, s состояний и m символов рабочих лент. Во
ВЫЧИСЛИТЕЛЬНЫЕ ВОЗМОЖНОСТИ ОДНОСТОРОННИХ МАШИН ТЬЮРИНГА
83
время работы M может получить доступ к информации, хранящейся не более, чем в f (n)
ячейках на каждой из k рабочих лент, и к информации, заключенной в одном из s состояний управляющего устройства. Таким образом, общее число возможных образов машины
M не превосходит числа s · mkf (n) .
С другой стороны, машина M может совершить не более g(n) недетерминированных переходов. Обозначим максимальное число образов, в которые за один недетерминированный
шаг может перейти M , константой d. Тогда число различных образов, в которых может
одновременно находиться машина M при обработке слова длины n, ограничено сверху выражением dg(n) .
Определение 3.6. Пусть односторонняя машина с подсказкой M имеет g(n)-ограничение
на недетерминизм и f (n)-ограничение на память. Тогда через DCM (n) обозначим количество всевозможных наборов образов, в которых машина M может находиться при обработке
слов длины n.
Лемма 3.1. Пусть даны функции f (n), g(n) такие, что f (n) = o(n), g(n) ≤ f (n). Пусть
односторонняя машина M имеет g(n)-ограничение на недетерминизм и f (n)-ограничение
g(n)
на память со слабой подсказкой длины f (n). Тогда справедливо DCM (n) ≤ 2cf (n)2 , где c —
некоторая константа, зависящая только от параметров машины M .
4. Определение специальных языков
На основе функций g(n) и f (n) определим следующий язык.
g(n)
Определение 4.1. SPf (n) — это множество строк w, удовлетворяющих следующим свойствам:
◦ |w| = n для некотого n ≥ 1;
◦ w = x1 2x2 2 . . . 2xs 3u4y r , где s ≤ g(n) + 1;
◦ xk ∈ {0, 1}∗ и |xk | = f (n) для всех k;
◦ u ∈ {0, 1}∗ ;
◦ y r — обратная запись слова y;
◦ y ∈ {0, 1}∗ , |y| = f (n) и y = xi хотя бы для одного i, 1 ≤ i ≤ s.
Лемма 4.1. Пусть даны функции f (n), g(n) такие, что f (n) = o(n), g(n) = o(n), g(n) ≤
g(n)
g(n)
f (n). Тогда язык SPf (n) содержится в классе SPACEu (f (n)).
Определение 4.2. SP+
f (n) — это множество строк w, удовлетворяющих следующим свойствам:
◦ |w| = n для некотого n ≥ 1;
◦ w = x1 2x2 2 . . . 2xs 3u4y r , где s ≥ 1;
◦ xk ∈ {0, 1}∗ и |xk | = f (n) для всех k;
◦ u ∈ {0, 1}∗ ;
◦ y r — обратная запись слова y;
◦ y ∈ {0, 1}∗ , |y| = f (n) и y = xi хотя бы для одного i, 1 ≤ i ≤ s.
+
Лемма 4.2. Язык SP+
f (n) содержится в классе SPACEu (f (n)).
5. Свойства специальных языков
Зафиксируем некоторое значение n и рассмотрим все слова w длины n специального
g(n)
языка L1 = SPf (n) и представим их в виде w = Aw 3Bw , где Bw = u4y r . Рассмотрим такие
Aw , в которых подстроки xj не повторяются.
84
А.Н. ЛЕЩЕВ
Определение 5.1. Обозначим через LCL1 (n) количество различных подстрок Aw слов w
g(n)
длины n из языка L1 = SPf (n) .
Лемма 5.1. Пусть даны функции f (n), g(n) такие, что f (n) = o(n), g(n) ≤ f (n). Тогда
g(n)
для языка L1 = SPf (n) справедливо
g(n)
2f (n)
LCL1 (n) ≥
.
g(n)
Лемма 5.2. Пусть даны функции f (n), g(n) такие, что f (n) = o(n), 2f (n) ≤ g(n) ≤ n.
g(n)
Тогда для языка L1 = SPf (n) справедливо
f (n)
LCL1 (n) ≥ 22
.
6. Доказательство иерархии
Зафиксируем некоторое значение n и рассмотрим все слова w длины n специального
= SPg(n) и представим их в виде w = Aw 3Bw , где Bw = u4y r . Рассмотрим одязыка L
f (n)
ностороннюю машину с подсказкой M с ограничением на недетерминизм и ограничением
на память. Выберем некоторую конкретную подстроку Aw 3. Обозначим через S(Aw ) набор
образов машины M , в которых она будет недетерминированно находиться после обработки
подстроки Aw 3. Для каждого Aw через X(Aw ) обозначим множество подстрок xj в Aw .
Тогда различные наборы X(Aw ) подстрок xj должны давать различные наборы образов
S(Aw ), и наоборот, если для некоторого другого слова w выполняется X(Aw ) = X(Aw ), то
и
S(Aw ) = S(Aw ). Иначе будет существовать такое окончание слова w B, что Aw 3B ∈ L
но при этом S(Aw ) = S(Aw ), и, следовательно, машина M не будет иметь никаAw 3B ∈ L,
кой возможности для различения Aw и Aw . Поэтому для корректного распознавания языка
машиной M , количество всевозможных вариантов Aw 3 не должно превышать количества
L
различных наборов образов машины M . Таким образом, выявлена связь между сложностью
специального языка LCL (n) и возможностями односторонней машины, выраженными характеристикой DCM (n). Использование этой связи будет лежать в основе доказательств
невырожденности иерархии далее.
Лемма 6.1. Пусть даны функции g(n), f (n), h(n) такие, что f (n) = o(n), g(n) ≤ 2f (n) и
h(n) = o(log g(n)). Тогда
g(n)
(f (n)).
SPf (n) ∈ SPACEh(n)
u
Доказательство. В основе доказательства данного утверждения лежит сравнение велиg(n)
чин, выражающих сложностную характеристику LCL1 (n) языка L1 = SPf (n) и вычислительные возможности DCM (n) односторонних машин, соответствующих классу сложноh(n)
сти SPACEu (f (n)). На основе лемм 3.1, 5.1 и 5.2 доказывается соотношение DCM (n) =
o (LCL1 (n)). Таким образом, при достаточно больших n никакая машина M с h(n)-ограничением на недетерминизм и f (n)-ограничением на память, не сможет распознать все
g(n)
g(n)
h(n)
возможные варианты слов из L1 = SPf (n) . Следовательно, SPf (n) ∈ SPACEu (f (n)).
Лемма 6.2. Пусть даны функции g(n), f (n) такие, что f (n) = o(n) и g(n) ≤ 2f (n) . Тогда
g(n)
SPf (n) ∈ SPACEulog g(n) (f (n)).
ВЫЧИСЛИТЕЛЬНЫЕ ВОЗМОЖНОСТИ ОДНОСТОРОННИХ МАШИН ТЬЮРИНГА
85
Доказательство. Идея доказательства этой леммы заключается в использовании машин
Тьюринга, построенных в леммах 4.1 и 4.2. Эти машины модифицируются так, что теперь
g(n)
при обработке слов языка SPf (n) они совершают не gn , а log g(n) недетерминированных
операций.
Теорема 6.1. Для любой функции f (n) = o(n) и любых функций g(n) и h(n) таких, что
h(n)
g(n)
h(n) = o(g(n)) и g(n) ≤ f (n) справедливо SPACEu (f (n)) SPACEu (f (n)).
h(n)
g(n)
Доказательство. 1. Включение SPACEu (f (n)) ⊆ SPACEu (f (n)) выполняется в силу
того, что, позволяя машине совершать больше недетерминированных шагов, мы можем
только увеличить множество распознаваемых языков.
g(n)
g(n)
2. Рассмотрим язык SP2f (n) . По лемме 6.1 язык SP2f (n) не принадлежит классу языков
h(n)
SPACEu
g(n)
(f (n)). С другой стороны, по лемме 6.2 язык SP2f (n) принадлежит классу языg(n)
g(n)
ков SPACEu (f (n)). Таким образом, мы нашли элемент множества SPACEu
h(n)
принадлежащий множеству SPACEu (f (n)).
(f (n)), не
Следствие. Утверждение теоремы 6.1 доказывает существование невырожденной иерарg(n)
хии классов сложности SPACEu (f (n)) относительно ограничения на количество недетерминированных операций
· · · SPACEulog
(k+1)
n
(f (n)) SPACElog
u
(k)
n
(f (n)) SPACEulog
(k−1)
n
(f (n)) · · · .
Литература
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
Sanjeev A., Boaz B. Computational complexity: a modern approach (Princeton University, 2006).
Rosenberg A. L. Real-time definable languages, J. Assoc. Comp. Mach. 14 (4), 645–662 (1967).
Book R. V., Greibach S.A. Quasi-realtime languages, Math. Systems Theory 4 (2), 97–111 (1970).
Patrick C.F., Chandra M.R.K. Real-time computations with restricted nondeterminism, Math. Systems Theory
12, 219–231 (1979).
Bruda S.D., Akl S.G. On the necessity of formal models for real-time parallel computations, Parallel Process.
Lett. 11 (2/3), 353–361 (2001).
Kutrib M. Refining nondeterminism below linear time, J. Automata, Languages and Combinatorics, 7 (4),
533–547 (2002).
Bruda S.D., Akl S.G. Real-time computation: a formal definition and its applications, Internat. J. Computers
and Appl. 25 (2), 1–11 (2003).
Bruda S.D. Sublinear space real-time Turing machines cannot count, Eighth Internat. Conference on Information Technology: New Generations, 976–978 (2011).
Hartmanis J., Lewis P.L. II, Stearns R.E. Hierarchies of memory-limited computations, Proc. of the 6th Annual
IEEE Symposium on switching circuit theory and logic design, 179–190 (1965).
А.Н. Лещев
ассистент, кафедра теоретической кибернетики,
Казанский (Приволжский) Федеральный университет,
ул. Кремлевская, д. 18, г. Казань, 420008, Россия,
e-mail: alex.leshev@gmail.com
86
А.Н. ЛЕЩЕВ
A.N. Leshchev
Computational power of real-time Turing machines with sublogarithmic memory
restrictions
Abstract. In this paper we consider the well-known Turing machine model — nondeterministic
real-time Turing machine. We prove the existence of nonregular complexity classes of languages
that can be recognized by nondeterministic real-time Turing machines with sublogarithmic memory
restrictions. These complexity classes form a strict hierarchy. We define a special language family
and show its properties to prove that hierarchy.
Keywords: real-time Turing machine, nondeterministic Turing machine, memory restrictions.
A.N. Leshchev
Assistant, Chair of Theoretical Cybernetics,
Kazan (Volga Region) Federal University,
18 Kremlyovskaya str., Kazan, 420008 Russia,
e-mail: alex.leshev@gmail.com
1/--страниц
Пожаловаться на содержимое документа