ПРОГРАММИРОВАНИЕ, 2013, No 6, с. 3-11
- ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ -
УДК 681.3.06
ОГРАНИЧЕННАЯ МОНОТОННАЯ РЕКУРСИЯ И МГ-АВТОМАТЫ *
© 2013 г. С.С. Марченков МГУ им. М.В. Ломоносова, факультет вычислительной математики и кибернетики 119991 Москва, ГСП-1, Ленинские горы, МГУ, д. 1, стр. 52 E-mail: ssmarchen@yandex.ru Поступила в редакцию 10.12.2012
На основе ограниченной монотонной рекурсии определен класс ВМИ словарных функций над алфавитом {1, 2}. Введен новый тип вычислительного устройства — многоголовочный нестираюгций автомат с выходом (МГ-автомат). Доказано, что класс ВМИ совпадает с классом МИЛ словарных функций, вычислимых на МГ-автоматах за полиномиальное время. Приведены многочисленные примеры словарных функций из класса ВМИ.
1. ВВЕДЕНИЕ
Первые работы по теоретическому программированию принадлежат A.A. Ляпунову [1] и Ю.И. Янову [2]. Уже в [2] отмечалось, что моделирование программ схемами программ ограничивается рассмотрением только алгоритмической составляющей программ. Дальнейшие формализации понятия программы были выполнены Р.И. Подловченко в работах [3,4]: в [3] строились схемы программ без рекурсии, в [4] — с рекурсией. В этих работах фактически учитывались лишь разделение операторов и описание процедур, входящих в описание реальной программы. Таким образом, естественно возникает задача о подходящей реализации рекурсивных функций. Кроме того, в связи с общей тенденцией в теории сложности вычислений актуальными становятся исследования, посвященные выделению классов рекурсивных функций, вычислимых за полиномиальное время.
В теории рекурсивных (вычислимых) функций рекурсия является основным инструментом определения и исследования функций. Общие виды рекурсии рассматриваются сравнительно редко, используется главным образом примитивная рекурсия и некоторые ее частные случаи.
* Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект 10-01-00768).
Как правило, новый вариант рекурсии вводится либо с целью определения некоторого подкласса примитивно рекурсивных функций, либо для рекурсивного описания уже имеющегося класса функций, заданного в сложностных или в "машинных" терминах.
В ряду достаточно большого числа вариантов примитивной рекурсии выделяются ее "монотонные" формы, когда в ходе рекурсивного определения функции все предыдущие значения функции в известном смысле "суммируются". Типичным примером здесь может служить ограниченное суммирование и - с некоторыми оговорками - ограниченное мультиплицирование (см., например, [5,6] и [7,8], где операция ограниченного суммирования рассматривается в рамках экспоненциальных расширений класса функций, элементарных по Сколему).
Варианты монотонной рекурсии можно рассматривать не только в числовой, но и в словарной форме, когда шаг рекурсии зависит от последнего символа переменной рекурсии, а "суммирование" превращается в конкатенацию. Именно так выглядит "конкатенационная рекурсия по обозначениям" (англ. термин concatenation recursion on notstion [9-11]). Отметим, что в [9-11] используется довольно слабая форма монотонной словарной рекурсии.
В настоящей статье мы хотим ввести более
общее понятие монотонной словарной рекурсии и, ориентируясь на некоторый класс словарных функций, вычислимых на многоголовочных автоматах, исследовать класс BMR функций, определяемых на основе монотонной словарной рекурсии. При этом, правда, нам придется ограничить рост функций, возникающих при использовании данного типа рекурсии, - иначе могут получиться сколь угодно сложно вычислимые функции. Для этого мы применяем известный в теории рекурсивных функций инструмент -ограниченную рекурсию (см. [5,6]). Таким образом, в статье будет рассматриваться ограниченная монотонная словарная рекурсия, которую мы в дальнейшем называем ограниченной монотонной рекурсией. Следует отметить, что интерес к монотонным словарным рекурсиям в значительной степени связан с исследованиями по полиномиальным вычислениям [9,10].
В работе [12] начато изучение так называемых многоголовочных автоматов (далее МГ-автоматы). МГ-автомат по существу представляет собой вариант нестирающей двуленточной машины Тьюринга с несколькими головками на входной ленте и выходной лентой, используемой только для записи результата. В [12] в основном рассматривались вычисления словарных функций над произвольными алфавитами, исключение составил класс функций, вычислимых над однобуквенным алфавитом, который оказался равным классу E2 иерархии Гжегорчика (см. также [13]).
В последние годы наметился определенный интерес к классам рекурсивных функций, порождаемым с использованием монотонной словарной рекурсии. Эти классы содержат функцию smash сверхполиномиального роста (определение функции smash см. ниже), но вместе с тем все функции из изучаемых классов вычислимы за полиномиальное время. Мы хотим сделать еще один шаг в данном направлении: с одной стороны, мы вводим новый, более общий тип словарной рекурсии и с его помощью определяем некоторый класс BMR словарных функций, а с другой стороны, обобщаем определение нестирающего (и в этом смысле — монотонного) МГ-автомата из [12] и получаем описание класса BMR в автоматных терминах. Мы полагаем, что оба обобщения задают некоторую естествен-
ную границу — дальнейшие обобщения выводят за пределы класса функций, вычислимых за полиномиальное время. Более того, с использованием результатов и техники данной статьи можно показать (в статье это не делается), что класс ВМЫ в точности состоит из всех функций, вычислимых за полиномиальное время.
Завершая вводную часть, отметим, что все словарные функции, рассматриваемые в настоящей статье, суть функции над алфавитом {1, 2}, а переход от словарных функций к числовым функциям осуществляется на основе диадиче-ского представления натуральных чисел, предложенного в [14].
2. ОСНОВНЫЕ ПОНЯТИЯ
Дадим необходимые определения. Следуя [14], зададим взаимно однозначное отображение множества X* всех слов в алфавите £ = {1,2} на множество N = {0,1,2,...}: произвольному непустому слову ат ... а\ао из £* сопоставим число
т
V (ат .. .а0) = аг • 2г.
г=0
Пустому слову Л сопоставим число 0. Слово ат . . . а0
числа V (ат ...ао )• Имея в виду диадическое
представление натуральных чисел, всякую
£*
одновременно рассматривать как соответствующую числовую функцию на множестве N.
Определим ряд словарных функций на мно-£*
конкатенация соп(Х1, Х2), которую будем обозначать как Х1 * Х2 (или даже в виде Х1Х2). Слово Х1 * Х2 получается из слова Х1 приписыва-Х2
Л*Х=Х*Л=Х
Через | х | обозначаем длину слова Х, пола-| Л| = 0
применяем степенные обозначения: например, 1п есть слово, состоящее из п единиц. Пусть I обозначает множество всех селекторных функций еП (1 < % < п, п = 1, 2,...), где для любых слов Х1,..., Хп из £* имеем
еп (х1 ,..., xг,..., Хп) = Хг.
Положим
si(x) = x * 1, s2(x) = x * 2.
Словарную функцию sub определим соотношениями
{y, если y — такое (единственное) слово, что y * x2 = x1, Л в остальных случаях.
Для функции sub(xi,x2) будем также использовать обозначение xi ^ x2- Отметим, что словарная функция xi ^ x2 существенно отличается от числовой функции xi ^ x2, рассматриваемой в теории рекурсивных функций. Легко видеть, что при любом x имеем x ^ x = Л.
Функцию smash зададим равенством
smash (xi,x2) = 1|xi|^x21,
xi = Л x2 = Л
smash(xi,x2) = Л. Другие словарные функции, используемые в статье, будут определяться по мере необходимости.
На множестве всех функций на X* определим операции суперпозиции и ограниченной монотонной рекурсии. Говорим, что функция f (xi,..., xn) получена из m-местной функции go и n местных функций gi,...,gm с помощью операции суперпозиции, если f(xi,...,x„) = go(gi(xi,... ,xn),..., gm(xi, . . . ,x„)). (1)
Пусть далее go — (n — 1)-местная, gi, g2 — (n + 1)-местные и g3 — n-местная функции, функция f (xi,..., xn) получается из функций go,gi, g2,g3 с помощью операции ограниченной монотонной рекурсии, если выполняются соотношения
f (xi,... ,xn-i, Л) = go (xi,... ,xn-i),
f (xi,... ,x„-i,si(x„)) = f (xi,...,x„)*
*gi(xi,... ,x„, f(xi,... ,x„)), f (xi, . . . ,x„-i,S2(x„)) = f (xi, . . . ,x„)*
*g2(xi, . . . ,x„, f(xi, . . . ,x„)), If (xi, . . . ,xn)| < |g3 (xi, . . . ,xn)|.
(2)
При п = 1 в качестве go берем функцию-константу.
Обозначим через ВЫИ, множество всех словарных функций, которые можно получить из исходных функций
с помощью операции суперпозиции и ограниченной монотонной рекурсии. Легко видеть, что класс ВМЫ состоит только из примитивно рекурсивных функций, но (ввиду четвертого соотношения из (2)) не из всех таких функций.
Перейдем к определению МГ-автоматов. МГ-автомат А представляет собой вариант одно-ленточной нестирающей машины Тьюринга с несколькими головками на ленте и выходом.
А
в каждой из которых может быть записан один из символов 1, 2 или •, где • есть граничный маркер. На входной ленте расположены к читающих головок, которые могут независимо друг от друга находиться в любых клетках ленты (допускается, что в одной и той же клетке одновре-
А
имеет множество состояний {^1,..., дг}, состояние считается начальным состоянием, состояние дг — заключительным. Функционирование А
состоит из команд вида
ai ... акqi ^ Di ... DkqjPiP2,
(4)
где аь...,а& е {1,2,•}, г = г, А,...,^ е {£, Е, Б} и Р1, Р2 — слова в алфавите £ (допускаются случаи Р1 = Л и Р2 = Л). Программа ав-А
с заданной левой частью.
А
/(ж1,...,жп), необходимо в начальный момент времени записать на входной ленте слово
»xi • x2
1 xn
(5)
si, s2, sub, smash, I
(3)
привести автомат в начальное состояние и установить все головки на крайний левый символ слова (5). Предполагается, что программа А
процессе вычисления ни одна из головок не выходит за пределы слова, ограниченного на ленте
•
кой вариант МГ-автомата, где слово Р1 записывается на входной ленте непосредственно перед •
что в любой момент вычисления на входной ленте автомата А имеется ровно п + 2 символов •, причем изменяться может лишь часть слова, заключенная между (п + 1)-м и (п + 2)-м символа-
ми •). Слов о Р2 подается па вы
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.