Обобщенный метод "нитей" и его некоторые применения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

НАЦИОНАЛЬНАЯ АКАДЕМИЯ НАУК УКРАИНЫ ИНСТИТУТ КИБЕРНЕТИКИ ИМЕНИ В. М. ГЛУШКОВА

РГб ОД

1 6 опт №

На правах рукопяся

МСИЕНСКИЙ Владимир Андреевич

ОБОБЩЕННЫЙ МЕТОД "НИТЕЙ" И КТО НЕКОТОРЫЕ ПРИМЕНЕНИЙ

Р10/.-00

0£т-05т(Л—теоретические основм информатика и кибернетика (натечатачеожая кнбернетякл)

АВТСРВВЕРАТ диссертация на соискание ученой степени доктора Зяэкко-иатеиатичеоких наук

Киев 1995

Работа выполнена в Белорусском государственном университете (г. Минск)

0*тшалыше оппоненты: доктор 4я»*ко-иатвм»т«чвоюи яау*.

профоосор С. В. Капитонова, доктор финко-математичеоню: иаук, профессор В. К. Будятко, доктор технически наук, профессор Г. И. Луцккй

Ведущая организация - Институт математик* НАН Украиян

Защита диссертации состоится 1995 г>

^ заседании специализированного Совета д oi.39.02 при институте кибернетики имени В. К. Глушкова по адресу: 252650, Киев. ГСП 22. пр. Академика Глушсова. 40.

С диссертацией ,|0ХЯ0 ознакомиться в научно-техниче-оком архиве Института.

Автореферат разослан____________1995 г.

Учены! секретарь специализированного Совета

Д 01.39.02 В. в. Синявский

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теми исследования. Формализация понятия алгоритма в 30-х годах текущего столетия А.Черчем, С.К.Клини, А. Тьюрингом и Э. Постом не только подняла вопросы неразрешимости массовых проблем, но и дала толчок более углубленному исследованию алгоритмически разрешимых проблем. Первым результатом, который невозможно было получить без формализации понятая алгоритма, был результат о том, что существуют сколь угодно сложно вычислимые предикаты, полученный Г. С. Цейтиным в 1956'г. (см. об этом в обзоре {I]) и немного позже М. О, Ра-биным [30] и Дж. Хартманисом и Р. Е. Стирнзом [2].

Правда, эти первые доказательства наличия сложно вычислимых предикатов были основаны на процедуре диагонализахии. Поэтому построенные с ее помощью такие предикаты были "неестественными" или "бессодержательными", поскольку были построены специально для того, чтобы быть трудно решаемыми. Но это не исключает, что во многих точках такие предикаты могут быть просто вычислимыми. Например, в работе ¡50] определенный при помощи процедуры диагонализаник предикат легко вычислим при каждом четном значении аргумента.

Первые экспоненциальные нижние оценки сложности вычислений естественных проблем были получены Мейером и Стокмейе- * ром [31] для одной специальной задачи теории форельных языков и Фишером и Рабиным [з2] для задачи определения истинных высказываний специальной арифметики. Такого рода проблемы- позволяет строить и метод Н.К.Косоеского[з], который дает взаи-иэпредставление недетерминированных вычислений лйКийо-арифые-

- А -

тическими уравнениями е позволяет доказывать экспоненциальную сложность любой функциональной схемы, реализующей проверку разрешимости таких уравнений (полное изложение в [4]).

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

А.О.Слисенко построил быстрые алгоритмы распознавания симметричности с лов [5] и нахождения всех периодичностей в слове [6].

Х.Л.Хачиян нашел полиномиальный алгоритм для задач линейного программирования [7].

Д.Ю.Григорьев построил весьма эффективные алгоритмы ([8], [9]) для вычислений ранга соответствующего тензора и свойств теории первого порядка алгебраически замкнутых полей, имеющие важные применения.

Была доказана неоптимальность алгоритма Гаусса [ю] и построены быстрые алгоритмы умножения матриц ([33 - 35]) к больших чисел [II].

Развивалась и общая теория вычислимости (см. монографии [12] и [13]), в частности, проблемы параллельных вычислений ([14], £15] и др.). Исследовались вычисления с оракулом ([Зб], [37] и др.) и на таких машинах, как недетерминированные ([38], [зэ] и др.), альтернирующие ([16], [17]) и вероятностные ([18], [40] и др.).

Из значительных результатов общей теории вычислимости отметим еще следувдие.

Изложение М.Блюмом аксиоматической теории сложности вычислений с теоремой об ускорении ([19], [20]).

Введение понятия полной функции для данного класса вычис-

лимых функций и первые утверждения об. этом, доказанные С. А. Куком [21] и Л. А. Левиным [22].

Из приведенных Звктов вполне можно заключить, что построение хорошего алгоритма вычисления данной вычислимой функши-это весьма трудоемкая задача. По-видимому, хорошим средством для такого поиска алгоритмов было бы изобретение совокупности методов анализа алгоритмов, которые хотя бы для многих "естественных" вычислимых функций позволяли бы за конечное число действий установить некоторые границы на требуемые для этой функции вычислительные ресурсы, особенно если эти границы нетривиальные.

Совокупность (весьма малочисленная) таких методов для классических машин Тьюринга на сегодняшний день имеется, и все они перечислены в диссертации. Здесь мы остановимся на трех из них; первых двух будем касаться, а третий есть предмет рассмотрения.

Метод "следов". Этот метод был впервые явно использован Ы. 0. Рабиныа[2з|и немного позже - Я. М. Барзди-нем [24]. Он позволяет получать нижние оценки времени вычисления (не выше квадратичных) на одноленточных одноголовых машинах Тьюринга, в том числе и для машин со входом.

Используя метод "следов", Б. А. Трахтенброт доказал [25]в 1964 г. первую теорему о пробелах для временной сложности (правда, так ее не называя; с таким названием эта теорема в общем виде фигурирует в работе [2в], оригинал которой появился в 1971 г.). Для так называемой существенной сложности вычислений первая теорема о пробелах опубликована в 1969 г. в работе [52], теорема 2.

Метод перекрытий. Он появился в работе [27],

где была доказана нижняя оценка )

временной сложности вычисления умножения на машинах Тьюринга, работавшие on-fine (т. е. г темпе поступления информации). В работе [28:было дано хорошее изложение этого метода и обсуждены типы машин, к которым он применим; в ней также доказана для временной сложности гичисления умножения на таких машинах

нижняя оценка

Метод "ки т е й". Он изложен в работах (¡43 -45]) и применим для анализа вычислений одноленточнкх одноголовых машн Тьюринга, хотя в работе [53J он применялся для анализа заключительной части вычислений машин Тьюринга со входом , работающее оп-Йпе (когда оставшаяся часть входных слов одна я та же). С помощью втого метода получены следующие результаты.

Доказан ряд утверждений

([43]. И) о переносе информации на лентах одколенточньа одноголовых машин Тьюринга.

Передоказан [44] результат из [24].

Получена [49] нелинейная нижняя оценка временной сложности вычислений одного класса универсальных машин Тьюринга.

Доказана ([53], [54]) нижняя оценка выше квадратичной временной сложности а-обраченлй при одном ограничении на длину рабочей зоны (при других ограничениях а-обращения рассматриваются в [47J, [48] ).

Доказана [53] оптимальность "школьного" метода умножения для машин Тьюринга со входом, работающих on-line синхронно.

Доказана [55] нижняя оценка 3.(У1 -to^n) числа существенных шагов при вычислении умножения на машинах Тьюринга со входом и одной рабочей лентой, работающих on-line (но без условия синхронности).

На языке метода "нитей" можно пвредоказать (ранее Доказанные автором [41] , [42] , [51]) оптимальные нижние оценки существенной, ленточной и других сложностей рассматриваемых тыоринговых вычислений через их временную сложность.

В [2э] на примере существенной сложности а-вычислекий обращений двоичных слов [4б] было доказано, что метод "нитей" сильнее, чем метод "следов". В первой главе диссертации изложен обобщенный метод "нитей". Ясно, что и он также сильнее, чем метод "следов".

Доказательство нетривиальной нижней оценки сложности вычисления любой вычислимой функции невозможно без исследования какого-то инварианта вычислений, т.е. того, что присуще всем вычислениям данного вида. Такой инвариант образует то, что составляет- основу соответствующего метода анализа вычислений. Поэтому описание метода анализа вычислений, с помощью которого можно получить нетривиальные нижние оценки некоторых сложностей вычислений хотя бы нескольких "естественных" проблем, представляется актуальным.

Цель работы. Доказательства нетривиальных нижних оценок сложностей вычислений являются, как правило, сложными и всегда опираются на исследования какого-то инварианта этих вычислений. Одним из таких инвариантов для тыоринговых вычислений является понятие "нити", на котором основан метод "нитей". Чтобы оправдать это название (т.е. то, что метод "нитей" - это действительно метод анализа тыоринговых вычислений), нужно достичь указанную цель: продемонстрировать получение с его помощью нетривиальных нижних оценок сложностей вычислений. Будет достигнута эта цель и еще показано, что понятие "нити" позволяет сделать некоторую унификацию теории тьюринговых вычислений.

Научная новизна. Инвариантом тьюринговых вычислений, позволившим М. Рабину|23] (в 1963 г.) доказать нетривиальную нижнюю опенку временной сложности одной "естественной" задачи, было понятие следа вычисления, определяемого одногодовой одно-ленточной машиной Тьюринга. Согласно определению след в некоторой точке и такого вычисления - это слово в алфавите внутренних состояний машины, определяющей это вычисление, с отметкой, которая говорит о направлении первого прохода точки ¿ считывающей головкой этой машины. (Если ленту такой машины изобразить в виде горизонтальной полоски, то в данном вычислении следы в точках этой ленты можно считать вертикальными образованиями.)

Ъ методе "нитей" за инвариант вычислений на таких же машинах Тьюринга берется понятие "нити", точнее

ж) -

нити, где Т* есть некоторая рассматриваемая машина Тьюринга, сС - ее некоторое вычисление. Л* - клетка ленты этого вычисления, а УУЪ - натуральный параметр, характеризующий эту нить. (В обобщенном методе "нитей" используется понятие обобщенной "нити", отличающееся от обычной тем, что клетка К зависит от вычисления к, значит, в различных вычислениях та-

х) ,

ш клетки могут быть разными.) Содержательно , /¿о^Л, -нить есть упорядоченный набор возрастающих моментов времени вычисления сС , в которые считывающая годозка посещает все различные клетки некоторого участка лекты, начиная с клетка /С и правое ее, причем любые две Т(с1,К,М)- и Т(о/,^ Ланита ке хкеот общих моментов при }П . (Если прздержн-

ваться того же изображения ленты, которое мы использовала при *> „ ' '

Точные формулировки довольно объемны (см> ниже).

описании следа, то можно сказать, что "нити" - это горизонтальные образования, но неверно, что "нить" - это горизонтально положенный "след".)

Используется еще и понятно "¿((¿¡К/ Л^-нити, отличающееся от описанного направлением движения считывающей головки, начиная с клетки К •

Понятие Т(о1, -нити, используемое в методе "ни-

тей" (а также и в обобщенном методе "нитей") отличается от инвариантов, используемых во всех других известных методах анализа рассматриваемых вычислений. Поэтому утверждения, получаемые в методе "нитей", не повторяют утверждений из других методов.

Первая глава диссертации посвящена изложению обобщенного метода "нитей"-. Доказывается восемь лемм о перекосе информации на лентах вычислений рассматриваемых машин, когда каждое вычисление згаеет соответствующую нить. Кроме этого, в этой же главе рассматривается частный случай нити, называемый путем (когда сдвиги считывающей головки во все моменты, составляющие нить, кроме одного ыемзнта, в одну и ту же сторону), и для этого варианта нитей доказываются еще две леммы; одна из шгх об одном свойстве путей, а другая - о новой оценке переноса информации на участках лент рассматриваемых машин. Также глава I содержит две у: эммы, не связанные с оценкой переноса информации на лентах рассматриваемых вычислений.

В главе II сравниваются методы "следов" к "нитей". На примере существенной сложности тьюринговых вычислений (понятие которой было введено автором в работе [52]) для одной и той же задачи доказывается, что использование метода "гатей" позволяет получить более высокую нижнюю оценку этой сложности, чем

при использовании в этой же задаче метода "следов" [Wj.

Последняя глава III посвящена описанию некоторых применений метода "нитей".

При определении эффективной нумерации всех вычислимых функций обычно рассматриваются те универсальные машины Тьюринга, в которых код моделируя;ой машины, содержательно говоря, i каждый'момент времени вычисления занимает один сплошной участок ленты (этот факт формализуется через понятие неудаляемого слова вычисления универсальной машины). Для таких универсальных машин Тьюринга доказывается, что для почти всех Л. мо-делгрование И-+-2 шагов вычисления хотя бы одной машины

потребует У1 J шагов универсальной машины [4э]. Согласно описанному в этой работе |4э] кодированию машин Тьюринга этот результат является неулучшаемым, потому что на участке

ленты длины

может быть задано КОДО]

различных капган.Тьюринга.

Следующий результат, полученный при помощи метода "нитей! касается временной сложности вычисления умножения на машинах Тьюринга со входом, работающих on-line синхронно. Этот результат гласит, что временная сложность.вычисления любой такой малины с одной рабочей лентой, работающей on-Jliie синхронно и вычисляющей умножение даух двоичных чисел, длина записи'каждого из которых есть У\ , пои достаточно больших УЬ равна

п ) [53]

. Поскольку "школьный" метод умножения выполни! на таких машинах, то полученный результат является неулучшаем:

Заметим, что условие синхронности, которое используется при получении этого результата, подсказано работой нормальных алгорифмов Маркова и самим "школьны;/." методом умножения. Под-

черкнем, что условие синхронности не уравнивает временные сложности вычислений операций сложения и умножения двух двоичных чисел на таких машинах Тьюринга, поскольку осуществима машина рассматриваемого типа, которая вычисляет сложение двух двоичных чисел с линейной временной сложностью.

После этого рассматриваются машины Тьюринга со входом, работающие on-|lne, но без условия синхронности. Ваделяется подкласс этих машин (называемых вполне реагируемыми), который не является сужением по существу класса всех таких машин, так как существенные сложности вычислений эквивалентных машин совпадают. Доказывается [55J, что существенная сложность вычисления каждой вполне реагируемой машины с одной рабочей лентой, вычисляющей умножение, есть М, ^^Н-) пра каждом достаточно большом Yl

Эта нижняя оценка совпадает с нижней оценкой из работы [¡28],.но так как наш результат о существенной сложности вычислений, а результат из [28] о временной сложности вычислений, то можно предположить, что временная сложность вычисленийгга-шин со входом и одной рабо-.ей лентой, работающих on-line л вычисляющих умножение, больше по порядку, чем ; это еще в некоторой мерз оправдываот условие синхронности.

Последнее применение касается рассмотрения а-обращекий на ограниченной рабочей зоно. Полученный результат [53J гласит, что временная сложность вычисления а-обрадений не менее

Sic YL-Vvfilb) , если эти а-обращения осуществляются машинами Тьюринга на рабочей зоне длины Ц +2,- [^i^n-J-f-S. В описанных в литературе ( [46j,[48j) мавшах длина рабочей зоны не менее Я. + 3/i^ rtj »Тем самым в »той теореме ограничение на длину рабочей зоны более жесткое, чем в пзвестных машинах.

Но хотя эта теорема является теоремой существования, она есть первый пример доказательства нижней оценки временной сложности вычисления по порядку больше для конкретной задачи (о

ней било объявлено в 1984 г. (см. [54]) ).

Все описанные применения метода "нитей" касались обычного использования метода ане.жза вычислений. Но возможно и другое применение этого метода, о чем говорится в заключении.

Определим специальную нить с параметром ¿. как отрезок моментов времени данного вычисления, начиная с некоторого специфического момента ¿ (эти моменты могут быть разными для различных специальных нитей). Например, для данного внчисле-ния существенная нить с параметром I есть отрезок моментов времоь^ этого вычисления между ¿-и включительно к существенными шагами этого вычисления. В работе [42] бшш а0~ лучены оптимальные нижние опенки между различными сложностями тьюринговых вычислений и их временной сложностью. Все эти нижние оценки были получены в [42] рассуждениями следугошего типа.

В произвольном конечном вычислении оценивалось сверху число всех шагов между двумя последовательными шагами, которые "считает" рассматриваемая функция. Например, для получения нижней сценки числа существенных шагов через число всех шагов в произвольном конечном вычислении оценивалось сверху число всех шагов между двумя последовательными существенны;® шагаю: этого вьмисления, что, согласно сказанному выше, является длиной существенной нити с соответствующим параметром. Следовательно, все указанные нижние опенки будут получаться еще- одним применением метода "гатей".

На языке метода "нитей" еще могут быть переизложены верхнее оценки мегду некоторыми собы гаями (например, соседними по-

воротами считывающей головки, существенными шагами и др.) как в произвольных конечных, так и в бесконечных тыэринговых вычислениях, которые были получены в работах ([4l],[5l]).

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

Методы исследований. Б основе большинства утверждений, доказанных при описании метода "нитей", лежит- свойство детерминированности рассматриваемых машин, используемое в следующем виде. Зсли на выделенных участках лент в рассматриваемом множестве вычислений машины Т написано различных

слов, причем во всех этих вычислениях считывающие головки находятся на левых (или соответственно правых) концах этих участков, то число слов на лентах вне этих участков этого множества вычислений после любого числа шагов будет увеличено не более, чем в cf-0 раз, где есть число всех внутренних состояний машины Т , не считая заключительного.

При исследовании вычислений конкретных функций доказываются факты, вытекающие из свойств этих функций (например, доказываются утверждения, вытекающие из того, что умножение является сложной функцией).

При исследовании существенной сложности on- line вычислений умножения доказывается ряд свойств существенной сложности вычислений на машинах Тьюринга произвольного вида.

При получении нижних оценок всех других сложностей тью-ринговых вычислений через их временную сложность использовались процедуры из теории конечных разностей.

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

Апробирование и публикации. Результаты диссертации изла- | гались на Седьмой всесоюзной конференции по математической логике (Новосибирск, 1934), в Международном математическом центре имени С. Банаха (Варшава, 1985), в Софийском университете (1988), на семинарах по дискоетйой математике и ее приложениям в Московском университет?, на конференции математиков Беларуси (Гродно, 1992), а такхе на некоторых других семинарах.

Результаты диссертации опубликованы в работах [41 - 55].

Структура и объем работы. Диссертация состоит из введения, трех глав, эаюрочьЕия и списка литературы. Каждая глава содержит по 4 параграфа и заканчивается выводами. Объем работы 15(5 страниц (в тексте расстояние между строками равно полтора к гервала), включая 9 страниц цитированной литературы. В списке литературы 102 наименования.

',. . 0СН0ВН02 СОДЕРЖАНИЕ РАБОТЫ

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

Глава I посвящена изложению обобщенного метода "нитей" (первоначальный метод "нитей" был изложен в работах [43 - 4ф. С помощью этого метода оценивается перенос информации на лентах одноголозых однолекточных детерминированных маиган Тьюринга, ленты которых в каждый момент конечны. Основным в этом изложении является понятие обобщенной "нити", которое мы сейчас определил.

Б начальной конфигурации на ленте записано некоторое слово в фиксированном'алфавите - по одной букве в каждой клетке ленты, а считывающая головка (СГ) находится над крайней слева клеткой ленты при начальном внутреннем состоянии машины. В про-

цассе работы катины, когда СГ сдвигается в отсутствующа клетку, сразу яе пристраивается новая пустая клетка, так что лента потенциально не ограничена как вправо, так и влево.

В начальной конфигурации клетки ленты считаем занумерованными слева направо числами I, 2, 3, ... . Если в процессе работы машины Тьюринга (МГ) на правом (соответстгенно левом) конце ленты пристраивается новая пустая, клетка ленты, то ей присваивается номер, на единицу больше (соответственно меньше) номера клетки, находящейся непосредственно слева (соответственно справа) от нее.

Пусть А - произвольное множество вычислений некоторой рассматриваемой Ш\ Для каждого вычисления оС из множества . А зафиксируем:

1) некоторый момент его времени "¿г (возможно, начальный);

оО

2)некоторую клетку К'ленты этого вычисления.

В этих обозначениях конкретные значения и М.: времени

с/

и клетки соответственно вычисления сС представляем в виде

и ^^/Л/ • Поэтому можно определить

иоС . У

В дальнейшем отсчет времени в вычислении сС ведем- от момента .

оС ,

Через обозначим момент времени вычисле-

ния оС ( если он существует) такой, что

-162) в момент Т С0^^ 1) СГ посещает клетку К

и сдвигается вправо;

3) если в этом вычислении оС есть момент , отличный от Т(о!., /Г .У/и > , .в который СГ посе-

ос ^ 7 со

щает клетку Л' и сдвигается вправо, то T(c¿ К; j ~¿. .

o¿ f 2

Другими словами, через fí^.K. i) обозначим момент вре-

л

мени вычисления (если он существует), в который СГ по-

сещает клетку К . '/в этот момент она первый раз с момен-оС

та сдвигается с клетки К вправо. c¿ _, сС

Через Т (o¿ К й) обозначим момент времени вычисления оС (если он существует), в который СГ посещает клетку

А' , причем первый раз с момента У1 (<¿ К i) ока d _cL>

сдвигается с этой клетки влево. Еще введем Т Coi К 0) ,

оС J

полагая (o¿ К 0) ~

Т (oL.K, xi) .

cL' oLJ

Пусть в данном вычислении оС уже определены моменты

T'CoLjK^m) и TU^Mt) ДЛя каждого

Через T0¿j , К 1)

обозначим первый после

к, момент времени вычисления o¿ (если он су-

«с '

шествует), в который СГ посещает клетку К и сдвигается —/ оС

вправо; через Т (oíjK , К +1) обозначим первый после ^ оС

Т > момент времени вычисления оС (если он

существует), в который СГ посещает клетку К и сдвигается

сС

влево.

Пусть в данном вычислении оС определены моменты

Т'&ьК^М.) и т'и^пг) ■

Через ¿/7^ К, , УП-) ,УП=1 -. обозначим клетку ос }

ленты вычисления такую, которая посещается СГ с момен-

та тМ-) по момент Т (оС^К^^ № ) включительно, но в этом временном интервале СГ ни разу не посещает клетку й'и^М)*!. Через Т'СеС,^, М),

/У2— • . обозначим первый после (сС^ /Г, } УУ1)

момент времени вычисления оС , в который СГ посещает клетку \) • Далее, если сегмент

[к^+1, З'Ссс.к^т)-1]

содержит хотя бы одну клетку ленты, то для каждой клетки^ / I — К ... к)(о1 % 23 этого сегмента через

) обозначим первый после Т(oiJ /С^ ^ УП.)

>мент времени вычисления с/. , в который СГ посещает клетку

у / .

Упорядоченный набор < Т(о1, К , Ш ) Т{о1 К )71 Г К + /7

/и' > с > > с1 />

..; К^ гп] Уи^ту!)^

Па-нитью, ■■■ .

П7

/

Через L (К y №) обозначим множество всех различных

А , л

слов на участках лент всех вычислений oL из множества п , когда в каждом из этих вычислений oL рассматривается участок ленты левее клетки К и в оС есть первый момент из

.,■■-■■. cL

T'CoÎ К У>1Ч-1) -яхт. и оно рассматривается в этот первый момент.

Наконец, поскольку мы собираемся оценивать сверху число различных слов на участках лент рассматриваемого множества вычислений А , то требуется предполагать, что его мощность /Л/ не меньше правых частей вписываемых ниже неравенств.

В леммах I и 2 из главы I величина jL-^^Kj оце-

нивается сверху через величины

ILjK,m-i)\ и L (KJ-1).

л • А ' л 'о

где rnz,2. 1 m-i • • Л

Лемма 3 посвящена оценке сверху специальной величины, связанной с (1_ Уп)I )(когда в вычислениях cL нет

А '

первого момента из

Основное утверждение этой главы гласит, что

т.

где ± < £ (^ есть

число внутренних состояний рассматриваемой машины, не считая заключительного), причем величины определяются кон-

структивно. Согласно этому неравенству число различных слов на

рассматриваемых участках лент вычислений возрастает пошагово.

(.<*■)

Лемма 10 из этой главы содержательно говорит, что и >

> 1 , если считывающей головкой было просмотрено больше различных слов на соответствующих участках лент во всех вычислениях, чем их учтено при переносе. В леммах 7 - 9 рассматрива-

<*)

ются другие случаи, связанные с и > 1 ни —9,'

т уп. г

Частным случаем нити является путь, состоящий из всех моментов (кроме одного), в каждый из которых СГ сдвигается в одну и ту же сторону (для одного варианта пути - вправо, для другого - влево). Доказываются одно свойство таких путей (лемма II). я новая верхняя опенка (лемма 12) о переносе информации на участках лент рассматриваемых машин.

Эта глава еще содержит вспомогательные утверждения (это леммы 4 к 6).

Глава II посвящена сравнению методов "следов" и "нитей". Для этого вводятся понятия существенной сложности тьюринговкх вычислений а а-вычислений. . .

Существенным шагом тьвркнгового вычисления называется выполнение той команды, которая предписывает изменения или внутреннего состояния глазики, пли считываемого-символа (в случае многоленточных■ машин,, зготя би на одной ленто). Число всех существенных шагов в данном конечном вычислении называется его существенной сложностью [52]. .

Доказана (теорема I) опталальная по порядку нижняя оценка существенной сложности тьвринговых вычислений через их временную сложность [52^.

А-вычисления характеризуются тем, что входной алфавит ма-

викы совладает с ее рабочим алфавитом, а каждая пристраиваемая в процессе работы машины новая клетка ленты содержит один и тот же входной символ. Для определения концов входного слова в начальной конфигурации а-вычкслений на ленте задается еще специальное слово одно и то же для всех входных слов одной в той же длины. Доказывается (теорема 2), что для любой вычислимой словарной функции в алфавите г\ , когда JA 1*2. ложно осуществить ее а-вычисление [^б].

А-вычисления обращений двоичных слов называются а-обра-щениями. Описывается одно а-обращение с оптимальными по порядку временными и емкостными сложностями вычислений (лемма 3) и два а-обращения (теорема 3), рабочая зона которых не меньше, чем Yl+^ Jj&Xj^l'] при а-обращении слов длины YL . когда

Я- есть достаточно большое натуральное число [4в]. Оказывается, что если к этой длине рабочей з'оны добавить еще L-^2ttj/м клеток ленты (), то можно построить

(машина из теоремы 3) оптимальное по временной сложно-

сти а-обращение. Но этого не удается сделать, если ¡J&j^l/ttl

заменить на УУ1 (машина из теоремы 3);

это, в некотором смысле, закономерно согласно теореме 8 из главы III.

При помощи метода "следов" доказано (теорема 4), что при а-обращении слов длины П. , когда П. есть достаточно большое натуральное число, на рабочей зоне длины не более

П + С- . где п) . НО ^Си) = o(n),

нижняя оценка существенной сложности а- обращений есть

£ С r^/fCn)) .

С помощью метода "нитей" для этой же задачи при тех же ограничениях на длину рабочей зоны доказано (теорема 5), что существенная сложность а-обращений слов длины Ц при достаточно больших KL по порядку равна УХ.

Последняя глава III посвящена описанию некоторых применений метода "нитей".

Часто рассматриваются те универсальные машины Тьюринга, в которых код моделируемой t/аиины, содержательно говоря, в каждый момент времени вычисления занимает один сплошной участок ленты (этот факт формализуется через понятие неудаляемо-го' слова вычисления универсальной машины). В § I для таких универсальных машин доказывается (теорема I), что для почти

всех KL моделирование Kl 2. шагов вычисления хотя бы

_ 2

одной машины потребует Jl.(YL ) шагов универсальной [4эЗ- В доказательстве этой теоремы основным является анализ нитей над участком ленты, содержащим неудаляемые слова.

Следующий параграф этой главы посвящен исследованиям вычислений на машинах Тьюринга со входом, работающих on-tlne синхронно, и временной сложности вычисления умножения на таких машинах. Вычисления на машинах со входом, работающих on-line (т. е. в темпе поступления информации) исследуются давно (¡,2?] и др.). Условие синхронности, по-видимому, применяется впервые. Оно состоит в том, что з каждый момент подачи очередного входного символа считывающие головки на каждой рабочей ленте находятся в их начальных клетках.

Условие синхронности подсказано следующим обстоятельством. Известно, что для.иашин, работающих on-line, никакой другой на сегодняшний день известный метод умножения, кроме "школьного", но подходит. В "школьном" методе утюжения множимое на

на каждом этапе обрабатывается, начиная с самого младшего разряда, т.е. с одного и того же места. Аналогичная ситуация имеет место в вычислениях, осуществляемых нормальными алгорифмами Маркова. Из условия синхронности прямо о временной сложности вычисления умножения на таких машинах ничего сказать нельзя. Это условие используется в доказательствах лемм I, 2 и следствия I. Подчеркнем также, что условие синхронности не уравнивает временные сложности вычислений операций сложения и умножения двух двоичных чисел на таких машинах.

С использованием одной леммы из [z?} о сложной функции (а умножение является сложной функцией) доказываются еще леммы 4 - 6 ж свойства I - 3. После этого уже можно доказать (теорема 2), что временная сложность вычисления любой машины с одной рабочей лентой, работающей on-line синхронно х вычисляющей умножение двух двоичных чисел, длина записи каждого из которых есть П. , при достаточно больших YV равна

£lCnz) [53]. Полученная в этой теореме нижняя оценка является оптимальной по порядку, поскольку "школьный" метод умножения может быть выполнен на машинах, работающих on-line,

и требует не более OLyC) шагов, а условие синхронности

добавляет не более 0(И^) шагов.

В доказательстве этой теоремы нити применяются для анализа рассматриваемых вычислений после моментов, когда в машину поступают одинаковые окончания (довольно длинные) входных слов.

•В этой главе § 3 посвящен исследованию существенной сложности вычислений произвольных машин, а также и машин со входом, работающих on-line (но без условия синхронности) и вычисляющее умножение двух двоичных чисел.

Сначала устанавливаются несколько свойств существенной сложности вычислений произвольных машин (теоремы 3 и 4) и один комбинаторный факт (теорема 5) о числе различных слов в произвольном конечном алфавите с данным числом серий, обобщающий аналогичную оценку из [44].

Машины Тьюринга, удовлетворяющие теореме 4, называются вполне реагируемыми; их основное свойство следующее: для каждой машины любого типа можно построить ей эквивалентную вполне реагируемую машину того же типа, существенные сложности вычислений которых соответственно совпадают, а в вычислениях.; вполне реагируемых машин в каждом существенном шаге происходит изменение внутреннего состояния машины н под действием разных символов - различные изменения внутренних состояний.

После этого доказываются еще три леммы о свойствах вычисления умножения на машинах Тьюринга со входом и одной рабочей лентой, работающих on-line.

Основной результат этого параграфа следующий. Пусть произвольная вполне реагируемая машина Тьюринга со входом и одной рабочей лентой, работающая on-line, вычисляет умножение двух двоичных чисел, представленных каждое словом длины yl .

Тогда ее существенная сложность вычисления есть jLЯ-) при каждом достаточно большом YL [55].

Последний параграф этой главы посвящен доказательству нижней оценки временной сложности вычислений а-обращений равной , когда эти а-обращения рассматриваются

при одном ограничении на длину рабочей зоны [бз]. Из определения а-обращений следует, что при а-обращении слов длины длина рабочей зоны не менее, чем С-, тле С^О .

В работе [4в] описаны два а-обращения (с различными по порядку временными сложностям), когда длина рабочей зоны каждого из них не менее , причем возможна машина с оптимальной временной сложностью вычисления а-обра-щений на длине рабочей зоны асимптотически равной

Пч-Ъ

В приведенном доказательстве этой нижней оценки временной сложности вычисления а-обращений требуется ограничить длину рабочей зоны величиной )-+-^-^' ® этом

доказательстве используется один комбинаторный факт (теорема 7), но главным в нем является анализ конфигураций, возникающих в моменты из нитей над довольно длинным участком лент, над которым число нитей в почти всех вычислениях есть

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

Таким образом, на защиту выносятся следующие основные результаты, полученные в диссертации.

1. Предложен метод анализа тьюринговых вычислений, с помощью которого

а) доказан ряд утверждений о переносе информации на лентах одноленточных одноголовых детерминированных машин Тьюринга; ■■;.■■■"......

б) возможно передоказать (ранее доказашше автором) оптимальные нияниа оценки других сложностей тьюринговых вычислений через их временную сложность.

2. Определены вычисления словарных функций на машинах Тьюринга без дополнительных ленточных символов (названные а-

вычислениями) и доказана возможность построения а-вычисления для любой вычислимой словарной функции, определенной в произвольном алфавите А при |А|^2 .

3. Исследована существенная сложность вычислений одно-ленточных одноголовых машин Тьюринга и на примере существенной сложности а-вычислений обращений двоичных слов доказано, что метод "нитей" сильнее, чем метод "следов".

4. Исследованы свойства вычислений на машинах Тьюринга со входом, работающих on-line синхронно и с помощью метода "нитей" доказана оптимальность "школьного" метода умножения для таких машин с одной рабочей лентой.

5. Исследована существенная сложность вычислений кашян Тьюринга произвольного вида и с помощью метода "нитей" доказана нижняя оценка числа существенных шагов вычисления умножения на машинах Тьюринга со входом и одной рабочей лентой, работающих on-line.

6. С помощью метода "нитей" доказана нижняя оценка 2>

временной сложности а-вычисленнй обращений

двоичных слов при использовании рабочей зоны длины не более для каждого достаточно большого УЬ

ЛИТЕРАТУРА

I. Яновская С. А. "Математическая логика и основания математики", Математика в СССР за сорок лет, 1917 - 1957. T. I.-Л.: Зизматгиз, 1959. - Сч 13-120. ¿. Хартканис Дж., Стирнз Р. К. 0 вычислительной сложности алгоритмов/ Кибернетический сборник, нов. серия, вып. 4. -. М.: Мир, 1967. - С. 57-86.

3. Косовский Н. К. Сложность разрешимости булевых функциональных уравнений/Вычислительная техника и вопросы кибернетики. - М., 1978. - Вып. 15. - С. 104-Ш.

4. Косовский Н. К. Основы теории элементарных алгоритмов. -Л.: Изд-во Ленингр. ун-та, 1987. - 152 с.

5. Слисенко А. О. Упрощенное доказательство распознавания симметричности слов в реальное время на машинах Тьюринга^ Зап. научн. семинаров Ленингр. отд. Матем. ин-та АН, 1977, 68. - С. 123-139.

6. Слисенко А. 0. Нахождение в реальное время всех периодич-ностей в слове^ДАН, 1980, 251:1. - С. 48-51.

7. Хачиян Л. Г. Полиномиальный алгоритм в линейном программировании/ДАН, 1979 , 244:5. - С. 1093-1096.

8. Григорьев Д. Ю. Алгебраическая сложность вычисления семейства билинейных форм^Журнал вычисл. матем. и матем. физ.,

' 1979, 19:3. - С. 563-580.

9. Григорьев Д. Ю. Сложность разрешения теории первого порядка алгебраически замкнутых полей-/Изв. АН СССР, сер. матем., 1986. - Т. 50, вып. 5. - С. 1106-1120.

10. Шграссен В. Алгоритм Гаусса не оптимален/Кибернетический сборник, нов. серия. Вып. 7. - М.: Мир, 1970. - С. 67-70.

11. Шенхаге А., Штрассен В. Быстрое умножение больших чисел^ Кибернетический сборник, нов. серия. Вып. 10. - М.: Мир, 1973. - С. 87-98.

12. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972. - 624 с.

13. Мальцев А. И. Алгоритмы и рекурсивные функции. - М.: Наука, 1986 (2-е издание). - 368 с.

14. Алгоритмы, математическое обеспечение и архитектура много-

процессорных вычислительных систем. - Под ред. А. П. Ершова.-М.: Наука, 1982. - 336 с.

15. Михалевич В. С., Капитонова Ю. В., Летичевский А. А., Молчанов И. Н., Погребинский С. Б. Организация вычислений в многопроцессорных вычислительных системах/Кибернетика,

а 3, 1984. - с. 1-10.

16. Пауль В., Праусс Э., Райшук Р. Об альтернировании. 1/Ки-бернетический сборник, нов. серия. Вып. 20. - М.: Мир, 1983. - С. 107-122.

17. Пауль В., Райшук Р. Об альтернировании, и/Кибернетический сборник, нов. серия. Вып. 20.- М.: Мир, 1983.- С. 123-140.

18. Фрейвадц Р. В. Ускорение распознавания некоторых множеств применением датчика случайных чисел^Проблемы кибернетики. Вып. 36. - М.: Наука, 1979. - С. 209-224.

19. Блюм М. Машинно-независимая теория сложности рекурсивных функций. - В кн.: "Проблемы математической логики", М.: Мир, 1970. - С. 401-422.

20. Блюм М. Об эффективных процедурах для ускоряющих алгоритмов. - В кн.: "Сложность вычислений и алгоритмов", М.: Мир. 1974. -С. 127-149.

21. Кук С. А. Сложность процедур вывода теорем/1'Кибернетический сборник, нов. серия. Вып. 12. - М.: Мир, 1975. - С. 5-15.

22. Левин Л. А. Универсальные задачи перебора/Пробл. передачи информации, 1973, 9:3. - С. 115-116.

23. Рабин М. 0. Вычисления в реальное время. - В кн.: "Проблемы математической логики", М.: Мир, 1970. - С. 156-167.

24. Барздинь Я.М. Сложность распознавания симметрии на машинах

Тьюринга//Йроблемы кибернетики, вып.15.-1965.- С. 245-248.

25. Трахтенброт Б, А. Тыоринговы вычисления с логарифмическим замедлением//Алгебра и логика. Семинар, 1964, 3:4. - С.

. 33-48. "

26. Хартманис Дх., Хопкрофт Дх. Э. Обзор теории сложности вычисление/Кибернетический сборник, нов. серия. Вып. II,

(*^1974. - с. I3I-I7S.

27. Кук С. А., Аандераа С. О. О минимальном времени вычисления функций//Кибернетический сборник, нов. серия. Вып. 8, 1971. - С. 168-200.

28. Патерсон М. С., Фишер М. Дх., Мейер А. Р. Улучшенный метод частичного пере^ытия для умножения, выполняемого в темпе поступления информации//Кибернетический сборник, нов. серия. Вып. 14, 1977. - С. 78-94.

29. Мощенский В. А, 0 существенной сложности тьюринговых вы-• числений. - Автореферат канд. диссер. - М.: Вычислительный центр АН, 1981. -12 с.

30. Rabin И.О., Degree

of difficulty of computing a function and a partial ordering of recursive seta, Technical Report 2, Hedrew University, Jerusalem, I960.

31. Ыеуег A-.R. and Stockmeyer L.J., The equivalence problem for regular expressions with squaring requires exponential space, Proceedings of the I3th IEEE Symposium on Switching

V. ..... ,and Automate Theory (1972), pp. 125-129.

32. Fischer U.J., Rabin il.O., Super-exponential complexity of Presburger arithmetic, Complexity of Computation (R.Karp, editor), SlXii-AIE Proceeding, ' vol¿7',-American Mathematical Society, Providence, Rhode Island, 1974, pp. 27-42.

33- Strassen V,, Relative bilinear complexity and matrix mul-

tiplication.- J. Reine u. /.ngew. Kath., 1987, B. 375/376, pp. 406-443.

34. Schonhage A., Partial and total matrix multiplication.-Preprint. Math. Inst., Univ. Tubingen, I9SQ.

35. Ja"Ja"Joseph, Takche Jean. Improved lower bounds for some matrix multiplication problems.- Inform. Process. Lett., 1935, vol. 21, Ho. 3, PP- 123-127.

36. Yao A. C., Separating the polinomial-time hierarchy by oracles, Proceeding of the 26th IEEE Symposium on Foundations of Computer Science (1985), pp. I-IO.

37. Baver 2., Gill J. and Solovay R., Relotiviaations of the P=?Ii? queotion, SIAU Journal on Computing (1975), vol. 4, pp. 431-442.

38. Cook S.A., A hierarchy for nondeterministic time complexity //J. of Сотр. and Syst. Sci., 1973, vol. 7, pp.343-353-

39. Savitch W., Relationship between nond< terministic and deterministic tape complexities // J. Сотр. and Sy3t. Sci., 1970, 4:2, pp. 177-192.

40. Berlekenp E.R., Factoring polynomials о ■ :r large finite fields 11 liathemstics of Computations, vol. 24 (1970), pp. 713-735.

Работы автора по томе диссертации

41. Мощенский 3. A. 03 одной оценке последовательности состояний малин Тыорлнга//Кибернетика, 1971.- Ц 4.- С. 39-43.

42. Мощенский В. А. Об оценке некоторых функций, характеризующих работу машин Тьюринга// Кибернетика, 1971,- ft I. -

С. 34-40. .

43. Мощенекий В. А. Об одном методе анализа тьюринговых вычис-

-30' золений. l/lКибернетика, 1977.- * 3. - С. 8S-94.

44. Мощенский В. А. Об одном методе анализа тьюринговых вычкс-леннй. 11//Кибернетика, 1986.- * 2.- С. 24-29.

45. Мощенский В. А. Об одном методе анализа тьюринговых вычислений. III/Кибернетика. 1987.- Я 2.- С. 26-29.

46. Мощенский В. А. Тьюринговы а-вычислекия и существенная сложность а-обращений двоичных слов. - Сб. "Методы диск- < ретного анализа в теории булевых функций и схем". Вып.

35.- Новосибирск, 1980. - С. 83-92.

47. Мощенский В. À. А-обращения при ограничениях на длину рабочей зоны. - Труды семинара по дискретной математике ж ее приложениям. Изд-во Московского ун-та, 1992.

48. Мощенский В. А. А-обращения при ограничениях на длину рабочей эоны/Весц! АН РБ, сер ф.-м. н., 1994. - * 3. -

С. II3-I20. ■■■■■

49. Мощенский В. А. Нижняя оценка временной сложности одного класса универсальных машин Тьхфинга. - Сб. "Методы дискретного анализа в теории графов и схем". Вьш. 42. - Новосибирск, 1985. - С. 72-79.

50. Мощенский В. А. К теореме о неограниченности сложности вн-числений/Весц! АН РБ, сер. ф.-м.н., 1990.- » 5.-С.96-99.

51. Мощенский В. А. К анализу тьюринговых вычислений/Известия АН ^Беларуси, сер.ф.-м.н., 1972.- »2. - с. 47-55.

52. Мощенский В. А. К вопросу о сложности тьюринговых вычисле-ний^ДокяаДЫ АН Беларуси, т. XIII, № 10 (1969).- С.876-878.

53. Мощенский В. А. Некоторые сложные тьюринговы вычисления.-Препринт « I, Белгосуниверситет, 1992. - 30 с.

54. Мощенский В. А. Пример кедиагонального вычисления с вре-хТ~~-'

Имеется английский перевод В Cybernetics. Consultante Bureau, New York - London (Translation of Kibernetika (Kley))

менной сложностью по порядку большей П. . - Седьмая всесоюзная конференция по матем. логике. Тезисы докладов. -Новосибирск, 1984. - С. 114.

55. Мощенский В. А. Свойства вычислений на машнах Тьюринга со входом, работающих on-line синхронно, и сложность вычисления умножения. - Конференция математиков Беларуси. Тезисы докладов. Часть 4. Гродно, 1992. - С. 91.

АННОТАЦИИ I. Мощенский В. А. "Обобщенный метод "нитей" и его некоторые применения".

Диссертация представляется в виде рукописи на соискание ученой степени доктора физико-математических наук по специальности 01.05.01 - теоретические основы информатики н кибернетики (математическая кибернетика).

Институт кибернетики км. В. Ы. ГЛУШКОВА HAH Украины.

Диссертация содержит изложение метода анализа вычислений на одноленточкых одноголовых детерминированных машинах Тьюринга, называемого обобщенным методом "нитей". С его поиощьп " доказан ряд утверждений о переносе информации в процессе вычислений на лентах таких иапаи.

Определены вычисления словарных функций на иаиннах Тьюринга без дополнительных ленточных символов (названные а-ви-числеюиши) и доказана возможность построения а-вычнслеяид любой словарной функции, определенной в произвольном алфавите А при 2 . На примере существенной сложности а-ви-чкслений обращений двоичных слов доказано, что метод "нитей" сильнее, чем метод "следов".

С помощью обобщенного метода "нитей" доказаны:

1) нижняя оценка равная для временной сложности а-вычислоний обраяекий двоичных слов при использовании рабочей зоны длины не более Ц -+ Z / ^fa nJ + $ ;

2) оптимальность "школьного" метода умножения на патанах Тьюринга со входом, работавших on-jlne синхронно;

3) нижняя оценка равная 5Z(n €пп.) для существенной сдоя-ности вычисления умножения на манатах Тьюринга со входом, работавших on-line (но без условия синхронности);

4) квадратичная нижняя оценка числа всех вагов специальных универсальных папаш Тьвриига при моделировании ft. + 2. шагов обычной машины.

К л ю ч о в I слова: машина Т'юркнга, внд1чвкня, часом складн!сть вхл!чення, 1стотна складн!сть вих1чекня, нихн1 оц!нки складном!, складност! внд!чення множення.

2. Moshchenskii У. The Generalized Thread Method and Its Some Applications.

The thesis carries the form of manuscript to stand for a scientific degree of doctor in theoretical bases of information and cybernetics, speciality 01.05.01 .

The thesis defence will be held in the V.M.Gluehkov Institute of Cybernetics, WAS of Ukraine, Kiev, 1995.

The generalized thread method is described for analysis of one head, one tape Turing machine computations. This method allows to prove a number of assertions about carry of information on tapes of these machines.

The notion of a-computatione of alphabet functions is defined. Using substantial complexity of word reversal a-computations it was proved that thread method if stronger than trace one.

By means of the generalized thread method it has been proved that

i-"school" method of multiplication is optimal for the synchronized on-line Turing machines with one working tope;

ii-Si(tl^^n) ie a low bound of time complexity of Turing machines which a-compute binary word reversal with tape complexity ft +

ill- ie a low bound of substantial etep number of

on-line Turing machines which compute multiplication; iiii- a square low bound ie the low bound of all step number of special universal Turing machines for modeling f\[ + -f 2. steps of ordinary Turing machines.

Подписано в печать 25.05.95 г . Заказ » 693. Тира* 100 экз. Отпечатано на ротапринте в Белгосуняверситете (г.Минск)