Примитивные программные алгебры

• Автор: Буй, Дмитрий Борисович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Киев
• Количество страниц: 151 c. : ил

ГЛАВА I. ОСНОВНЫЕ ПОНЯТИЯ

§ I. Примитивные программные алгебры /ППА

§ 2. Примеры ППА

Глава II. ПОЛНОТА ППА В ОСНОВНЫХ КЛАССАХ ВЫЧИСЛИМЫХ ФУНКЦИЙ

§ 3. Полнота ППА в основных классах арифметических вычислимых функций

§ 4. Слабые и ограниченные ППА. Изоморфизм ППА

§ 5. Полнота ППА в основных классах целочисленных вычислимых функций

§ 6. Полнота ППА в основных классах рациональных вычислимых функции

§ 7. Полнота ППА в основных классах словарных вычислимых функции

Глава III. АЛГЕБРАИЧЕСКИЕ СВОЙСТВА АРИФМЕТИЧЕСКОЙ ППА

§ 8. Расширенные ППА ц -арных функций и предикатов,

К*Г,2,
§ 9. Взаимная нецроизводность основных операции арифметической ППА и смежные вопросы
§10. Некоторые подалгебры арифметической ППА
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

ПРИЛОЖЕНИЯ
A. Арифметические функции, представляющие в нумерации
'Г целочисленные функции <Х,э
Б. Арифметические функции, представляющие в нумерации
У рациональные функции Х+У1 ХУ *
B. Доказательство леммы 7,5
Г. Доказательство теоремы 10.6
Д. Разрешимый фрагмент элементарной теории класса всех
примитивных программных структур
- 5 -
Одна из актуальных задач современной теории программирования заключается в формализации семантики языков программирования. Из-за сложности этой задачи возникло несколько различных методов ее решения /см., например,[ 6^]/. Предлагаемая работа основывается на композиционном подходе, заложенном в работах
В.Н.Редько 1-5?-59 }.
В рамках композиционного метода было достигнуто не только существенное продвижение в формализации семантики языков программирования /см., например,[30, 55/, но и реализован ряд систем программирования, например, система автоматизированного построения процессоров ДЕФЙПС[(3 , /ЗЪ
Сущность композиционного подхода раскрывается в его принципах [53 ], среди которых мы отметим принцип функциональности и принцип комлозиционности.
В силу первого принципа семантикой любой программы является функция, отображающая множество исходных данных в множество результатов. Т.о., в качестве семантики языка программирования, рассматриваемого как класс программ, выступает соответствующий класс функций.
По принципу комлозиционности для описания таких классов функций необходимо рассматривать алгебры функций, называемые в этом случае программными алгебрами /ПА/, замыкания в которых и будут задавать упомянутые классы функций.
- £0
Из вышесказанного вытекает
Теорема I. Замыкание множества функций в ограниченной целочисленной ППА в точности совпадает с классом целочисленных прф.
5.2. Полнота в классах целочисленных орф и чрф.
Здесь по аналогии с прф мы дадим алгебраическую характеристику классов целочисленных орф и чрф. Для этого, ввиду лемм I, 3, 6 и следствия I, очевидно, достаточно доказать аналог леммы 2 для новых классов функций.
Лемма 7. В целочисленной ППА /в слабой целочисленной ППА/ из функций множества 6>г строится расширение /доопределение/ каждой целочисленной чрф /орф,соответственно/.
Доказательство копирует доказательство леммы 2 с заменой всюду ограниченных циклирований на циклирования или на слабые циклирования.
Т.о., имеет место
Теорема 2. Замыкание множества функций 6% в целочисленной ППА /в слабой целочисленной ППА/ в точности совпадает с классом целочисленных чрф /орф, соответственно/.
§ 6. Полнота ПДА в основных классах вычислимых рациональных функций.
В этом параграфе будет дана алгебраическая характеристика в ППА классов рациональных прф, орф и чрф, причем эти классы определяются аналогично случаю целочисленных функций, т.е