Классы алгоритмов и вычислений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение:

Глава I. Внутренние свойства алгоритмических систем.

§ I.I Определение и простейшие свойства алгорит- 16 мических систем.

1.1.1 Основные понятия, связанные с алгоритми- 16 ческими системами.

1.1.2 Рекурсивно перечислимые алгоритмические 24 системы.

1.1.3 Алгоритмические системы и математические 34 модели вычислительных машин.

1.1.4 Алгоритмические системы и Z.

1.1.5 Алгоритмические системы с конечным числом 38 состояний.

§ 1.2 Максимальные алгоритмические; системы

§ 1.3 Базисы алгоритмических систем.

1.3.1 Универсальная -система без рекурсивно 59 перечислимых базисов.

1.3.2 Преобразование ^"-систем без р.п. базисов 70 в Jf- -системы с р.п„ базисами.

1.3.3 Достаточное условие существования р.п. 75 базисов у ^"-систем.

Глава 2. Внешние свойства алгоритмических систем.

§ 2.1 Определение и простейшие свойства морфизмов алгоритмических систем.

§ 2.2 Существование; морфизмов для АС„ представляющих некоторые модели алгоритмов.

§ 2.3 Моделирующие р.п. системы

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

Рассматриваемые классы алгоритмов - множества алгоритмов в алгоритмических системах (АС ) - составляют основной предмет исследования. Определение алгоритмической системы предлагается в качестве формального уточнения для понятия модели алгоритмов, Потребность в таком уточнении вызвана развитием теории алгоритмов, а также созданием и использованием вычислительных устройств.

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

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

Возможность уточнения понятия алгоритма несколькими способами повлекла изучение связи между различными моделями» Оказалось, что предложенные уточнения равносильны в том смысле, что классы функций, вычисляемых алгоритмами из указанных моделей, а также из предложенных позднее моделей А.А.Маркова, А.Н.Колмогорова и других, - эквивалентны.

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

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

Влияние программирования на теорию алгоритмов проявилось в создании таких моделей, в которых уточнялись понятия, связанные с машинными алгоритмами. Из них отметим определения логических схем црограмм А.А.Ляпунова, машин Шепердсона-Стур-гиса, дискретных преобразователей В.М.Глушкова.

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

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

По второй схеме элементарные операции, из которых строятся алгоритмы, могут быть сколь угодно сложными. Примерами соответствующих моделей являются логические схемы программ, машины Шепердсона-Стургиса, автоматы Бухбергера Е19 J.

Известны попытки создания общего комбинаторного определения алгоритма, объемлющего существующие оцределения. Из них следует отметить то, которое было предложено А.Н.Колмогоровым, а также появившееся сравнительно недавно определение введённое Н.А.Криницким.[ю J . f,Множество всех предложенных моделей уже достаточно обширно. Оно постоянно пополняется и становится всё более труднообозримым. Последнее вызвано значительным разнообразием средств, используемых в определениях существующих моделей. Поэтому всё более важной становится задача описания множества всех возможных, моделей алгоритмов. Её решение позволило бы рассматривать существующие модели с единой точки зрения, а также способствовало более полному осмыслению вводимых новых моделей. Это одна из цричин, сделавших актуальным уточнение понятия модели алгоритмов.

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

Целесообразность такого представления объясняется несколькими причинами.

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

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

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

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

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

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

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

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

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

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

В-третьих, при изучении алгоритмических вычислений появляется возможность рассматривать связь одних семантических свойств алгоритмов с другими их свойствами, не сталкиваясь явно с явлением неразрешимости. Это связано с тем, что сами вычисления - это достаточно сложные объекты, свойства которых могут быть нетривиальными и неразрешимыми.

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

В работе Бухбергера и РойдераЦ 19 ]определяется достаточно общая модель, алгоритмы в которой называются автоматами. Пусть сг обозначает множество одноместных общерекурсивных функций. Всякая четвёрка CjS^f^g) функций из Cf образует автомат, у и у называются кодирующей и декодирующей, а f и - образующими функциями этого автомата. Функции -f и ^ определяют вычисления на множестве натуральных чисел Л/, элементы которого называются конфигурациями. Если не. л/ и

J (п.) -О , то конфигурация гь называется , заключительной. Вычисление автомата, начинающееся в конфигурации /г „- это пос

Г 0 Г k ледовательность } (it),., -у (п) ,. „ которая содержит к конфигураций, где к = jut С ^-f (п) = о)+±.

Обозначим как Lfфункцию, которая для каждого /гед/ определяет последнюю конфигурацию вычисления, начинающегося в конфигурации п. . Автомат (<> вычисляет функцию у Lf § . Множество всех автоматов образует предложенную Бухбергером модель алгоритмов.

С семантической точки зрения под алгоритмами естественно понимать объекты, удовлетворяющие следующим условиям: I. всякий алгоритм работает на бесконечном разрешимом множестве конфигураций, 2. множество заключительных конфигураций для каждого алгоритма - разрешимо, 3. существует эффективная процедура, которая для всякой незаключительной конфигурации Ъ определяет такую конфигурацию , что Z переходит в за один шаг работы алгоритма.

Нетрудно видеть, что с точностью до изоморфизма развёрток всякий алгоритм, удовлетворяющий условиям I.-3., представляется в виде некоторого автомата Бухбергера.

В диссертации предлагается иное определение для алгоритмов, удовлетворяющих тем же условиям. Это сделано потому, что в модели Бухбергера связь между вычислениями и вычисляемой функцией не прямая, а опосредована кодирующей и декодирующей функциями. В известном смысле автомат Бухбергера представляет собой композицию трёх алгоритмов : кодирующего, основного и декодирующего. Изменив множество конфигураций, можно сделать эти функции излишними. Тем самым достигается упрощение общего определения и удаётся устранить недостаток изложенной модели.

В работе Шепердсона [ 21 J, по-видимому, впервые было сформулировано общее определение вычисления. В качестве множества конфигураций в работе выбрано множество натуральных чисел. Шепердсон определил вычисления как рекурсивно перечислимые последовательности конфигураций. Для каждой конфигурации в вычислении разрешимо свойство быть заключительной. Под развёрткой алгоритма в указанной работе понимается рекурсивно перечислимое семейство вычислений, порождаемых с помощью некоторой рекурсивной функции, которая определяет переходы конфигураций в конфигурации в вычислениях. При этом множество заключительных конфигураций в вычислениях алгоритма должно быть рекурсивным.

В работе Ю.И.Янова[18 ] рассматривается представление множеств вычислений с помощью нагруженных ориентированных деревьев. Вершинам этих деревьев соответствуют множества конфигураций. Вычисления представляются в виде ветвей таких деревьев. Содержательно, если две вершины вычислительного дерева соединены стрелкой, то это означает, что всякая конфигурация, приписанная вершине в начале стрелки, переходит в некоторую определенную конфигурацию из множества, соответствующего вершине в конце стрелки, за один шаг работы алгоритма.

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

В основном указанная работа посвящена исследованию одного специального класса деревьев. Рассматриваются преобразования деревьев - операции свёртки - и изучается вопрос о том, какие свойства деревьев сохраняются этими операциями.

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

Новым в подходе Ю.И.Янова является стремление определять и изучать алгоритмы с помощью их развёрток. Его можно назвать структурно-семантическим, поскольку основным в определении алгоритма является строение множества вычислений, которое задается с помощью ориентированного нагруженного дерева.

Однако простота основных используемых в указанном подходе понятий, по-видимому, затрудняет получение общих определений вычисления, алгоритма и его развёртки.

Понятие алгоритмической системы является новым и в данной диссертации исследуется впервые. Поэтому выполненное в ней исследование характеризует стремление проанализировать оцределение АС со многих сторон. Это объясняется необходимостью лучшего понимания вводимых в работе новых понятий, связанных с АС.

Определение алгоритмической системы основано на представлениях об общих и существенных чертах имеющихся моделей алгоритмов. Для кавдой из них характерны три цризнака:rl. разрешимое множество данных или конфигураций, на которых работают алгоритмы в модели, 2. некоторый язык, элементы которого воспринимаются как программы алгоритмов, 3. описание работы алгоритмов, которое по записи всякого алгоритма в модели определяет вычисления, порождаемые им на множестве конфигураций.

Настоящая диссертация состоит из введения и двух глав. В первой главе определяется понятие алгоритмической системы и изучаются различные характеристики отдельных АС. Там же вводится общее определение алгоритма. Оно основано на представлениях о том, что всякий алгоритм - это алгоритм в некоторой АС.

1. Барздинь Я.М. Сложность распознавания симметрии на машинах Тьюринга. - В кн.: Проблемы кибернетики, вып. 15, 1965, с. 245-248.

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

3. Глушков В.М., Летичевский А.А. Теория дискретных преобразователей. В кн.: Избранные вопросы алгебры и логики. Новосибирск: Наука, 1973, с. 5-39.

4. Ершов А.П. Вычислимость в произвольных областях и базисах.- В кн.: Семиотика и информатика, вып. 19, М.: ВИНИТИ, 1982, с. 3-58.

5. Ершов Ю.Л. Теория нумераций. М.: Наука, 1977, - 416 с.

6. Колмогоров А.Н., Успенский В.А. ,К определению алгоритма.- УМН, т.13, №4, 1958, с. 3-28.

7. Костенко К.И. Системы алгоритмов. Тезисы У1 Всесоюзной конференции по математической логике. Тбилиси, 1982, с.86.

8. Костенко К.И. Модели вычислимости. Тезисы 1У Всесоюзного симпозиума по системному и теоретическому программированию, Кишинёв, 1983, с. 212-213.

9. Костенко К.И. Классы алгоритмов и вычислений. ДАН,

10. Криницкий Н.А. Алгоритмы вокруг нас. М.: Наука, 1977, -224 с.

11. Ляпунов А.А. О логических схемах программ. В кн.: Проблемы кибернетики, вып. 37, 1980, с. 195-213.

12. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1965. - с.

13. Мендельсон Э. Введение в математическую логику. М.: Наука, 1976. - с. 320.

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

15. Стронг Х.Р.- Вычисления с ограниченной глубиной. В кн. Сложность вычислений и алгоритмов. М.: Мир,, 1974, с. 349363.

16. Трахтенброт Б,А. Сложность вычислений и алгоритмов. -Новосибирск: НГУ, 1967,. с. 258.

17. Хартманис Д. Сложность вычислений на одноленточных машинах Тьюринга. В кн.: Проблемы математической логики. М.: Мир, 1970г с. 282-300.

18. Янов Ю.И. Несколько теорем о свертках. ИПМ им. М.В. Келдыша. Препринт № 95 за 1978 г.

19. ОасЛве^ек в., ftoidenb. %.put-ocrfpat codinQ алоС tmn-6Ltion function in effcctiuc ^nAvinatLonatJoiwal Gtnml tyternb.,У&М, a/2>, 20i- 203.

20. Щтлг1 W.y tym^dmai&L V. ilruLmwJi oudjomsia. wiiL1игф>2ль 4ouncL -^Lnudcction "time. . ^nfovnatcO/b oact contort^ (fo£. ig-?s.

21. J-C. ^aduruL wrifi^cumiiori Qnct ufwt ргоб&мл of сtiifrb defjm. of (JWaiiTaJkEii^. IzilyJiuft 9rkdi. lofrc unji Qurtdl- dui

22. SLpwbvK J •, H. (ЬщраЫьЩ of- ЪсиШЬС fwidtir*, J/jCM , Vol.4, тъ, 517-255.23. ibona НЯ. ЩЖ-шовЩ ffnm&led ъмлМос fuAcUonУкоъ^. ImJ. Ъшж?., ms, 4gs-w.