Содержание к диссертации
Введение
Глава I. Внутренние свойства алгоритмических систем. 16
1,1 Определение и простейшие свойства алгоритмических систем
1.1.1 Основные понятия, связанные с алгоритмическими системами.
1.1.2 Рекурсивно перечислимые алгоритмические системы.
1.1.3 Алгоритмические системы и математические модели вычислительных машин.
1.1.4 Алгоритмические системы 2- и Z. 36
1.1.5 Алгоритмические системы с конечным числомсостояний,
1,2 Максимальные алгоритмические; системы 43
1.3 Базисы алгоритмических систем. 59
1.3.1 Универсальная система без рекурсивно 59 перечислимых базисов.
1.3.2 Преобразование систем без р.п. базисовв Jf--системы с р.п„ базисами.
1.3.3 Достаточное условие существования базисов систем.
Глава 2. Внешние свойства алгоритмических систем. 81
2.1 Определение и простейшие свойства морфизмов алгоритмических систем.
2.2 Существований морфизмов для АС представляющих некоторые модели алгоритмов.
2.3 Моделирующие . системы 115
Литература 126
- Определение и простейшие свойства алгоритмических систем
- Основные понятия, связанные с алгоритмическими системами.
- Определение и простейшие свойства морфизмов алгоритмических систем.
Введение к работе
В данной работе изучаются свойства множеств вычислений, порождаемых алгоритмами и классами алгоритмов. При этом семантические аспекты алгоритмов не только составляют главную цель исследования, но и сама работа основана на семантическом подходе к изучению алгоритмов. Он состоит в том, что вычислительные процессы делаются главными объектами исследования и изучение всех вопросов, относящихся к алгоритмам, проводится в терминах порождаемых ими вычислений.
Рассматриваемые классы алгоритмов - множества алгоритмов в алгоритмических системах (АС ) - составляют основной предмет исследования. Определение алгоритмической системы предлагается в качестве формального уточнения для понятия модели алгоритмов. Потребность в таком уточнении вызвана развитием теории алгоритмов, а также созданием и использованием вычислительных устройств.
К настоящему времени в теории алгоритмов предложено несколько разных моделей алгоритмов. Создание первых таких моделей: было связано с задачами математической логики. Для их решения потребовалось уточнить понятие эффективной процедуры. Было предложено несколько различных уточнений этого понятия, множества алгоритмов в каждом из них образовывали конкретную модель алгоритмов, К таким моделям относятся машины Тьюринга, системы Поста, рекурсивные функции.
Предложенные модели различались между собой по форме задания алгоритмов, множествам данных, на которых они работают, интерпретациям выполнения вычислений. Они оказались удобными для доказательства неразрешимости ряда задач математической логики, а впоследствии и задач из других областей математики.
Возможность уточнения понятия алгоритма несколькими спо- - 4 -собами повлекла изучение связи между различными моделями. Оказалось, что предложенные уточнения равносильны в том смысле, что классы функций, вычисляемых алгоритмами из указанных моделей, а также из предложенных позднее моделей А.А.Маркова, А.Н.Колмогорова и других, - эквивалентны.
При изучении алгоритмов из этих моделей оказалось, что многие их свойства алгоритмически неразрешимы. Это повлекло поиск таких классов алгоритмов, в которых были бы разрешимы неразрешимые в общем случае, свойства алгоритмов. Последнее способствовало созданию новых моделей, в том числе и значительно отличавшихся от тех, которые уже имелись.
С появлением вычислительных машин для теории алгоритмов возникла новая область применения. Это объясняется тем, что аппарат указанной теории оказался удобным для формального изучения задач, возникающих из практики работы с ЭВМ. В частности, появились новые для теории алгоритмов задачи : эквивалентных преобразований, проверки правильности программ, построения алгоритмов с малой вычислительной сложностью.
Влияние программирования на теорию алгоритмов проявилось в создании таких моделей, в которых уточнялись понятия, связанные с машинными алгоритмами. Из них отметим определения логических схем программ А.А.Ляпунова, машин Шепердсона-Стур-гиса, дискретных преобразователей В.М.Глушкова.
Можно указать две общие схемы, согласно которым определяется всякая из предложенных к настоящему времени моделей алгоритмов.
По первой схеме модель строится на основе выделения некоторого множества элементарных операций, комбинации которых образуют алгоритмы. При этом простейшие операции являются очевидно эффективными и, в известном смысле, неразложимыми - 5:- на более простые. Примерами моделей, основанных на этой схе* ме, являются машины Тьюринга, системы Поста, алгоритмы Колмогорова, дискретные преобразователи Глушкова.
По второй схеме элементарные операции, из которых строятся алгоритмы, могут быть сколь угодно сложными. Примерами соответствующих моделей являются логические схемы программ, машины Шепердсона-Стургиса, автоматы Бухбергера Е19 J,
Известны попытки создания общего комбинаторного определения алгоритма, объемлющего существующие определения. Из них следует отметить то, которое было предложено А.Н.Колмогоровым, а также появившееся сравнительно недавно определение введённое Н.А.Кринипким.[Ю J . хМножество всех предложенных моделей уже достаточно обширно. Оно постоянно пополняется и становится всё более труднообозримым. Последнее вызвано значительным разнообразием средств, используемых в определениях существующих моделей. Поэтому всё более важной становится задача описания множества всех возможных, моделей алгоритмов. Её решение позволило бы рассматривать существующие модели с единой точки зрения, а также способствовало более полному осмыслению вводимых новых моделей. Это одна из причин, сделавших актуальным уточнение понятия модели алгоритмов.
Определение и изучение алгоритмических систем опревдано не только внутренней потребностью теории алгоритмов. Существует другая, возможно даже более важная, сторона такого изучения. Она связана с тем, что модели алгоритмов можно рассматривать как математические модели вычислительных машин.
Целесообразность такого представления объясняется несколькими причинами.
Достаточно естественно рассматривать модель вычислитель- ного устройства не как отдельный алгоритм, а как систему, способную выполнять различные алгоритмы, записываемые в виде; программ в некотором языке программирования.
В настоящее время имеется несколько абстрактных моделей вычислительных устройств. G определенной степенью точности каждую из них можно считать математической моделью для вычислительных машин. Развитие средств вычислительной техники приводит к усложнению структуры и функционирования ЭВМ. Поэтому представляется справедливым, что исследование свойств реальных ЭВМ в терминах существующих моделей может оказаться неадекватным или быть загромождено несущественными деталями.
Изменение реальных машин должно сопровождаться изменением их математических моделей. В качестве таких моделей в настоящей работе предлагается брать алгоритмические системы и проводить изучение свойств вычислительных машин в терминах характеристик соответствующих этим машинам АС.
Интерпретация всякой АС как математической модели некоторой ЭВМ позволяет проводить изучение свойств произвольных машин. Это делает возможным не только исследование существующих вычислительных устройств, но также позволяет предсказывать и оценивать направления будущего развития таких устройств.
Важная особенность настоящей работы состоит в том, что в ней реализуется семантический подход к изучению алгоритмов. В известном смысле он составляет метод исследования.
Заметим, что до сих пор изучение алгоритмов обычно было связано с рассмотрением их синтаксических или функциональных характеристик. Поэтому до сих пор исследовались преимущественно либо некоторые формы задания алгоритмов в виде языковых конструкций : сложность таких представлений, их преобразования и т.п., либо свойства вычислимых функций.
Исследование алгоритмов с этих двух сторон затруднено быстрым проявлением алгоритмической неразрешимости как для функциональных свойств, так и для связи между синтаксическим заданием алгоритмов и их семантикой. Под семантическими свойствами алгоритмов понимают такие свойства, которые характеризуют вычисления, порождаемые этими алгоритмами.
Сложность проведения исследования, основанного на синтаксических и. функциональных характеристиках требует другого, более гибкого подхода к изучению алгоритмов. Достаточно естественной альтернативой к указанным двум подходам является семантический, подход к изучению алгоритмов. Он основан на исследовании алгоритмов с точки зрения множеств порождаемых ими вычислений и обладает рядом достоинств.
Во-первых, только синтаксическими и функциональными свойствами алгоритмы характеризуются не полностью. Полное представление можно связывать с другой стороной всякого алгоритма -множеством порождаемых им вычислений ( развёрткой ) . В этих множествах проявляются, по-видимому, все представляющие интерес свойства алгоритмов, в том числе синтаксические и функциональные.
Во-вторых, изучение алгоритмических процессов должно облегчить понимание таких свойств алгоритмов, которые плохо проявляются в синтаксическом и функциональном подходах. В частности это может помочь в нахождении случаев, когда имеет место разрешимость в общем случае неразрешимых свойств алгоритмов, а также сделать возможным более точное отделение классов алгоритмов, в которых разрешимы некоторые их свойства, от классов, в которых эти же свойства неразрешимы.
В-третьих, при изучении алгоритмических вычислений появляется возможность рассматривать связь одних семантических - 8 -свойств алгоритмов с другими их свойствами, не сталкиваясь явно с явлением неразрешимости. Это связано с тем, что сами вычисления - это достаточно сложные объекты, свойства которых могут быть нетривиальными и неразрешимыми.
Среди работ по теории алгоритмов можно указать несколько таких, в которых исследуются общие свойства вычислительных процессов. Они оказали существенное влияние на формирование вводимых в диссертации новых понятий.
В работе Бухбергера и РойдераС 19 ]определяется достаточно общая модель, алгоритмы в которой называются автоматами. Пусть & обозначает множество одноместных общерекурсивных функций. Всякая четвёрка CjS^f-^g) функций из и образует автомат, о и % называются кодирующей и декодирующей, а ^ и J - образующими функциями этого автомата. Функции -^ и О- определяют вычисления на множестве натуральных чисел Л/, элементы которого называются конфигурациями. Если tie. л/ и а(іг)-0 , то конфигурация гь называется.заключительной. Вычисление автомата, начинающееся в конфигурации /г „- это пос-ледовательность J (п),..., -у (п) ,.. „ которая содержит к конфигураций, где K^jutCaj (п) =6)+1.
Обозначим как Lj,^D функцию, которая для каждого /гед/ определяет последнюю конфигурацию вычисления, начинающегося в конфигурации /г . Автомат Cp,^,f»j) вычисляет функцию у Lf,^J . Множество всех автоматов образует предложенную Бухбергером модель алгоритмов.
С семантической точки зрения под алгоритмами естественно понимать объекты, удовлетворяющие следующим условиям: I. всякий алгоритм работает на бесконечном разрешимом множестве конфигураций, 2. множество заключительных конфигураций для каждого алгоритма - разрешимо, 3. существует эффективная процедура, - 9 -которая для всякой незаключительной конфигурации ї определяет такую конфигурацию ± , что ї переходит в *і за один шаг работы алгоритма.
Нетрудно видеть, что с точностью до изоморфизма развёрток всякий алгоритм, удовлетворяющий условиям І.-3., представляется в виде некоторого автомата Бухбергера.
В диссертации предлагается иное определение для алгоритмов, удовлетворяющих тем же условиям. Это сделано потому, что в модели Бухбергера связь между вычислениями и вычисляемой функцией не прямая, а опосредована кодирующей и декодирующей функциями. В известном смысле автомат Бухбергера представляет собой композицию трёх алгоритмов : кодирующего, основного и декодирующего. Изменив множество конфигураций, можно сделать эти функции излишними. Тем самым достигается упрощение общего определения и удаётся устранить недостаток изложенной модели.
В работе Шепердсона [21 3, по-видимому, впервые было сформулировано общее определение вычисления. В качестве множества конфигураций в работе выбрано множество натуральных чисел. Шепердсон определил вычисления как рекурсивно перечислимые последовательности конфигураций. Для каждой конфигурации в вычислении разрешимо свойство быть заключительной. Под развёрткой алгоритма в указанной работе понимается рекурсивно перечислимое семейство вычислений, порождаемых с помощью некоторой рекурсивной функции, которая определяет переходы конфигураций в конфигурации в вычислениях. При этом множество заключительных конфигураций в вычислениях алгоритма должно быть рекурсивным.
В работе Ю.И.Янова[18 ] рассматривается представление множеств вычислений с помощью нагруженных ориентированных де- - 10 -ревьев. Вершинам этих деревьев соответствуют множества конфигураций. Вычисления представляются в виде ветвей таких деревьев. Содержательно, если две вершины вычислительного дерева соединены стрелкой, то это означает, что всякая конфигурация, приписанная вершине в начале стрелки, переходит в некоторую определенную конфигурацию из множества, соответствующего вершине в конце стрелки, за один шаг работы алгоритма.
Класс алгоритмов,которые можно представлять с помощью вычислительных деревьев, достаточно широк. Отметим, что такое представление допускают все машины Тьюринга.
В основном указанная работа посвящена исследованию одного специального класса деревьев. Рассматриваются преобразования деревьев - операции свёртки - и изучается вопрос о том, какие свойства деревьев сохраняются этими операциями.
Полученные результаты используются для доказательства разрешимости некоторых семантических свойств машин Тьюринга, принадлежащих определённым классам таких машин.
Новым в подходе Ю.И.Янова является стремление определять и изучать алгоритмы с помощью их развёрток. Его можно назвать структурно-семантическим, поскольку основным в определении алгоритма является строение множества вычислений, которое задается с помощью ориентированного нагруженного дерева.
Однако простота основных используемых в указанном подходе понятий, по-видимому, затрудняет получение общих определений вычисления, алгоритма и его развёртки.
Понятие алгоритмической системы является новым и в данной диссертации исследуется впервые. Поэтому выполненное в ней исследование характеризует стремление проанализировать определение АС со многих сторон. Это объясняется необходимостью лучшего понимания вводимых в работе новых понятий, - II - связанных с АС.
Определение алгоритмической системы основано на представлениях об общих и существенных чертах имеющихся моделей алгоритмов. Для кавдой из них характерны три признака:гI. разрешимое множество данных или конфигураций, на которых работают алгоритмы в модели, 2. некоторый язык, элементы которого воспринимаются как программы алгоритмов, 3. описание работы алгоритмов, которое по записи всякого алгоритма в модели определяет вычисления, порождаемые им на множестве конфигураций.
Настоящая диссертация состоит из введения и двух глав. В первой главе определяется понятие алгоритмической системы и изучаются различные характеристики отдельных АС. Там же вводится общее определение алгоритма. Оно основано на представлениях о том, что всякий алгоритм - это алгоритм в некоторой АС.
В качестве множества конфигураций для всякой АС выбрано множество пар натуральных чисел. Поэтому в определении каждой конкретной АС множество конфигураций специально не уточняется. Определение всякой АС содержит три элемента. Первый - это некоторое множество номеров общерекурсивных функций (о.р.ф.) в вычислимой нумерации двухместных частично рекурсивных функций. Элементы этого множества называются образующими и выступают в качестве программ алгоритмов в АС. Функция, соответствующая образующей некоторого алгоритма из АС, на каждой конфигурации (это пара натуральных чисел ) принимает определенное значение. Последнее используется для определения шага работы соответствующего алгоритма в выбранной конфигурации.
Два других элемента определения каждой АС - это операторы перехода и остановки конфигураций. С помощью этих операторов по каждой образующей определяются вычисления, порождаемые соответствующим алгоритмом.
Выбор в качестве языка программ некоторого множества номеров о.р.ф. объясняется двумя причинами. Во-первых, изучение алгоритмов в данной работе проводится на основе их развёрток, и поэтому синтаксическое строение программ может не уточняться. Во-вторых, попытка определения общего понятия программы алгоритма, в котором бы уточнялось синтаксическое строение программ, привела бы к слишком громоздким формулировкам.
Множество всех алгоритмов не является рекурсивно перечислимым. Поэтому возникает вопрос о рекурсивной перечислимости класса типов изоморфизма алгоритмов. Содержательно два алгоритма изоморфны, если изоморфны их- развёртки.
Этот вопрос является основным в первом параграфе и его решение позволяет ответить на другой вопрос : о возможности определения всех, с точностью до изоморфизма, алгоритмов, которые удовлетворяют условиям 1.-3,, на основе построения конструктивного множества их программ. Доказанный результат но-;: сит негативный характер. Множество классов изоморфных алгоритмов неперечислимо.
Тем не менее достаточно обширные семейства алгоритмов могут определять рекурсивно перечислимые (р.п.) множества типов изоморфизма. Например, класс всех алгоритмов, которые порождают только конечные вычисления и имеют бесконечные множества заключительных конфигураций.
В общем случае алгоритмические системы содержат непере-числимые множества алгоритмов. Например, АС, соответствующая модели Шепердсона-Стургиса, поскольку множество алгоритмов в последней не является рекурсивно перечислимым.
Неперечиелимы семейства алгоритмов и в АС с наибольшими возможными множествами образующих ( такие АС называются # -системами). При этом семейства одноместных частично рекурсив- - ІЗ -них функций (ч.р.ф.) , вычисляемых алгоритмами из этих систем, могут быть рекурсивно перечислимыми.
Поэтому важен вопрос о нахождении таких конструктивных подмножеств множеств алгоритмов в АС, которыми вычисляются семейства ч.р.ф., вычисляемых всеми алгоритмами в соответствующих системах. Основной результат третьего параграфа первой главы состоит в построении универсальной $- -системы, для которой таких конструктивных подмножеств алгоритмов не существует. Т.е. всякую одноместную ч.р.ф. можно вычислять некоторым алгоритмом в этой АС, но никакое р.п. семейство алгоритмов в этой системе не вычисляет все одноместные ч.р.ф.
Этот результат принципиально новый для теории алгоритмов, поскольку в ней до сих пор не было моделей,обладающих указанным свойством.
В том же параграфе в терминах замкнутости множеств вычислений алгоритмов в АС относительно определённых операций формулируется достаточное условие при котором подходящее р.п. подмножество алгоритмов существует.
Вторая глава диссертации посвящена изучению преобразований алгоритмических систем в алгоритмические системы, назы-% ,-ж ваемых морфизмами.
Преобразования моделей алгоритмов в модели алгоритмов до сих пор практически не рассматривались. Исключение составляют преобразования, состоящие в потактном моделировании алгоритмов в одной модели алгоритмами в другой модели. Недостаток таких преобразований состоит в том, что по отношению к моделируемости алгоритмов алгоритмами многие модели оказываются равносильными. Например, это так для машин Тьюринга и машин Шепердсона-Стургиса. Хотя очевидно, что алгоритмы в первой модели проще алгоритмов во второй модели.
Содержательно морфизм - это такое отображение вычислений в одной АС в вычисления в другой АС, которое связано с эффективным преобразованием конечных фрагментов вычислений в первой АС в конечные фрагменты вычислений во второй АС. Дополнительно требуется, чтобы развёртка каждого алгоритма в одной АС отображалась в развёртку некоторого алгоритма в другой АС. Т.е. моделирование в этом случае проводится для всех вычислений, порождаемых алгоритмами в АС и не зависит от программ алгоритмов, которыми эти вычисления порождаются.
Во второй главе решается вопрос о существовании морфиз-мов для АС, которые соответствуют следующим моделям алгоритмов : конечным автоматам, однородным рефлексивным структурам, машинам Тьюринга, алгоритмам Маркова, машинам Шепердсона-Стур-гиса.
Доказано, что морфизмы между этими системами существуют лишь соответственно тому порядку, в котором перечислены представляемые ими модели. Интуитивно такой результат достаточно естественней и нетрудно привести неформальные доводы подтверждающие, что указанные модели перечислены в порядке усложнения функционирования алгоритмов в них.
Модель Шепердсона-Стургиса является наиболее общей среди всех моделей, поскольку можно доказать, что в соответствующую ей АС мономорфно преобразуется всякая АС.
Оказалось, что аналогичная АС существует и в классе всех алгоритмических систем с рекурсивно перечислимыми множествами алгоритмов С р.п. АС) . Построен пример такой р.п. АС, в которую мономорфно преобразуется всякая р.п. АС. Последний результат интересен ещё и потому, что множество всех р.п. АС не является рекурсивно перечислимым.
В диссертации не приводятся определения общепринятых теоретико-рекурсивных понятий. В случае необходимости их точные определения можно найти в работах С 5 J и С143 .
Укажем основные обозначения, используемые в дальнейшем. Для множеств п -местныхобщерекурсивных функций (о.р.фО и XI -местныхчастично рекурсивных функций (ч.р.ф.) используются символы & и 97 . N - это обозначение множества натуральных чисел. Функция, которая задаёт канторовскую нумерацию пар натуральных чисел (х,^) обозначается как с(х,а) . Обозначения Ъ(х) и С(к) применяются для функций, которые по X -с(иу0") определяют правую и левую компоненты пары (и^О") соответственно. Если f - это некоторая функция, то множеств во её значений будем обозначать как сЫ-f
Возьмём некоторые главные нумерации [5J множеств Э-с , с = 4.,2,3 , которые обозначим как ^ , ^=4.,2, . Для множеств \ти j f i-sJL,2?s » применим обозначения Я , Индекс в обозначении Я" обычно будем опускать.
Определение и простейшие свойства алгоритмических систем
Определение I.I Конфигурацией называется всякая пара (х хр натуральных чисел.
Первую компоненту конфигурации (хА1х2) назовём следом, а вторую - состоянием этой конфигурации. Если я(\» Ха) , то-обозначим Х как ї\ и Хг как Цг
Определение 1.2 Оператором перехода называется всякая пара Т= ( , 2) трёхместных о.р.ф.
Оператор Т переводит конфигурации в конфигурации следующим образом : если =( 2) 1 то для всякого фиксированного Х3 оператор Т переводит ї в C Vfeifc)» 4 &Лхз)) т е функция щ определяет след, а Лг - состояние конфигурации,; в которую Г переводит конфигурацию Z для заданного значения Х-ь . Если рассматривать действие оператора Т" на конфигурации 3L для всех значений х2 ел/ , то он переводит Ъ в некоторое множество конфигураций.
Действие Т на множестве конфигураций станет однозначным, если для каждой конфигурации выбирать только по одному значению Х3 . Рассмотрим случай, когда 8 ) » где ш є (у . Если лри этом Т переводит Ъ в 2 , то пишем ъ (ъ) или ї == . . Для (---( -Д применяем обоз-начение или г — . Полагаем ї = Ї . Действие "Т при заданных Ї и Хя, , состоящее в переводе г в (г) назовём шагом работы Нетрудно видеть, что определение оператора перехода равносильно другому определению : оператором перехода называется всякое эффективное отображение П Л/ — hi .в некоторых случаях удобно определять оператор Т , задав отображение N в N и не указывая явно составляющие его функции А± и А . Определение 1.3 Оператором остановки называется всякая трёхместная о.р.ф.
Для обозначения операторов остановки будет использоваться символ S ( возможно с индексами ) .
Основные понятия, связанные с алгоритмическими системами
Для всякой АС . обозначим множества функций, вычисляемых алгоритмами в Z , развёрток алгоритмов и их следов как F(Z), GfZb G(2)j±.
В определении алгоритмической системы уточняются интуитивные представления о моделях алгоритмов. Это, в частности, означает, что в виде АС должна представляться всякая из предложенных к настоящему времени моделей алгоритмов. Поясним, что понимается под представлением модели алгоритмов в виде АС.
Будем говорить, что AC Z представляет модель алгоритмов G , если существует такое инъективное отображение J± -конфигураций в модели во множество пар натуральных чисел и такое биективное отображение „а - множества алгоритмов в модели на множество алгоритмов в Z , для которых :
Первое из этих условий достаточно естественно. Второе возникает потому, что в ряде существующих моделей множества конфигураций, на которых работают алгоритмы - это различные подмножества множеств всех конфигураций в моделях. Например, это так для машин Тьюринга с разными ленточными алфавитами. При определении представляющего алгоритма необходимо задать его функционирование и для тех конфигураций, которые не являются образами конфигураций представляемого алгоритма. Для того чтобы представляющий алгоритм не очень сильно отличался от представляемого алгоритма, такое доопределение нужно делать по возможности простейшим способом.
Определение и простейшие свойства морфизмов алгоритмических систем
В этой главе рассматриваются свойства преобразований алгоритмов и алгоритмических систем, называемых морфизмами. В понятии морфизма уточняются интуитивные представления о конструктивных преобразованиях алгоритмов и алгоритмических систем.
В основе точного определения лежат соображения о том, что такое отображение вычисления в вычисление. Последние обобщаются на множества вычислений, порождаемых отдельными алгоритмами, и множества разверток алгоритмов в АС.
Поскольку в основных имеющихся определениях алгоритмы задаются с помощью программ в некоторых языках, то рассматривавшиеся до сих пор преобразования алгоритмов, как правило, были связаны с изменением их программ. В качестве примера можно привести потактное моделирование, в котором всякая команда моделируемого алгоритма заменяется группой команд моделирующего алгоритма. Моделирование выполнения команды одного алгоритма состоит в выполнении соответствующей последовательности команд другого алгоритма.
Систематическое исследование таких преобразований затрудняется быстрым проявлением алгоритмической неразрешимости. По-видимому, это можно объяснить тем, что даже простые преобразования программ алгоритмов способны значительно изменять свойства порождаемых этими алгоритмами вычислений.
Кроме того, преобразования алгоритмов, состоящие в изменении их программ, оказываются слишком сильными. Например, известна потактная моделируемость алгоритмов алгоритмами для почти всех моделей алгоритмов. Т.е. такие преобразования не позволяют различать эти модели, например, по сложности функ - 82 ционирования алгоритмов в них.
В настоящей работе будут рассматриваться преобразования алгоритмов, состоящие в изменении конечных фрагментов порождаемых ими вычислений. Возможно, преобразования алгоритмов, основанные на отображении порождаемых ими разверток, окажутся более удобными, чем преобразования программ, поскольку обозримые изменения конечных фрагментов вычислений влекут обозримое изменение свойств самих вычислений и порождающих эти вычисления алгоритмов.
Похожие диссертации на Классы алгоритмов и вычислений
