Классы алгоритмов и вычислений

• Автор: Костенко, Константин Иванович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 129 c. : ил

Введение:
Глава I. Внутренние свойства алгоритмических систем
§ І.І Определение и простейшие свойства алгорит
мических систем.
1.1.1 Основные понятия, связанные с алгоритми- 16 ческими системами.
1.1.2 Рекурсивно перечислимые алгоритмические 24 системы.
IЛ.3 Алгоритмические системы и математические
модели вычислительных машин.
1.1.4 Алгоритмические системы 2- и 2
1.1.5 Алгоритмические системы с конечным числом 38 состояний.
§ 1.2 Максимальные алгоритмические; системы
§ 1.3 Базисы алгоритмических систем
1.3.1 Универсальная ^"-система без рекурсивно 59 перечислимых базисов.
1.3.2 Преобразование ^"-систем без р.п. базисов 70 в іР-системы с р.п. базисами.
1.3.3 Достаточное условие существования р.п. 75 базисов у #-систем.
Глава 2. Внешние свойства алгоритмических систем
§2.1 Определение и простейшие свойства морфизмов
алгоритмических систем.
§ 2.2 Существование морфизмов для АС„ представляю
щих некоторые модели алгоритмов.
§ 2.3 Моделирующие р.п. системы
Литература

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

собами повлекла изучение связи между различными моделями. Оказалось, что предложенные уточнения равносильны в том смысле, что классы функций, вычисляемых алгоритмами из указанных моделей, а также из предложенных позднее моделей А.А.Маркова,
А.Н.Колмогорова и других, - эквивалентны.
При изучении алгоритмов из этих моделей оказалось, что многие их свойства алгоритмически неразрешимы. Это повлекло поиск таких классов алгоритмов, в которых были бы разрешимы неразрешимые в общем случае свойства алгоритмов. Последнее способствовало созданию новых моделей, в том числе и значительно отличавшихся от тех, которые уже имелись.
С появлением вычислительных машин для теории алгоритмов возникла новая область применения. Это объясняется тем, что аппарат указанной теории оказался удобным для формального изучения задач, возникающих из практики работы с ЭВМ. В частности, появились новые для теории алгоритмов задачи : эквивалентных преобразований, проверки правильности программ, построения алгоритмов с малой вычислительной сложностью.
Влияние программирования на теорию алгоритмов проявилось в создании таких моделей, в которых уточнялись понятия, связанные с машинными алгоритмами. Из них отметим определения логических схем программ А.А.Ляпунова, машин Шепердсона-Стур-гиса, дискретных преобразователей В.М.Глушкова.
Можно указать две общие схемы, согласно которым определяется всякая из предложенных к настоящему времени моделей алгоритмов.
По первой схеме модель строится на основе выделения некоторого множества элементарных операций, комбинации которых образуют алгоритмы. При этом простейшие операции являются очевидно эффективными и, в известном смысле, неразложимыми

у*'- рассматривается как номер отрезка некоторого на-чального вычисления в 2. ,х2+1- это ^ -номер следа, с которым должно быть продолжено вычисление, начинающееся из рассматриваемой конфигурации.
это значение следа конфигурации, в которую переходит рассматриваемая конфигурация, если выполнены некоторые дополнительные условия, х^Зг это -номер кортежа, используемого для продолжения начала вычисления в 2. , имеющего
номер 4 ,ф* - рассматривается как ц -номер кортека, который при выполнении дополнительных условий определяет значе-

ние /^ конфигурации, в которую переходит данная конфигура-. ция, т.е. задаёт след, с которым продолжается вычисление.
Для всякой конфигурации (х±9Хг) и числа х3£л/ определим значение из следующих соотношений.
Рассмотрим случай, когда ХгФ О
1.1 Пусть : а. х£ является номером отрезка г±|... некоторого начального вычисления в 21 , б. =о , в.х3+г -это ^ -номер кортежа (х° хг) , а6(%^ы/гУ)Щ где
6=0 /" и -Т(ък+И1^к^ |2, Xе') , 6 = 1 г . Тогда определим значение ^*3)=(£с(х°,О)) , где Х°г - это номер отрезка ^, гк ,ТX0) вычисления в АС И
1.2 Пусть выполнены условия а., б. из 1.1 и условие г.
х|+<2 - это ^ -номер такого кортежа (х°ъ..., хг) , что^^л
Уо'Я =0) •где х
Пусть при ЭТОМ Ц(х1+2) • ПОЛОЖИМ 7^$^,Х^ =^з,б^°,Хз)),
где /р° и х| определяются следующим образом, х; - ЭТО номер отрезка ^вычисления в 2! , а
= Г Ь=1 *±:г
•еоли *-*3 шЪкуок