1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 58
Текст из файла (страница 58)
Абстрактное устройство подобвого рода, могущее «переходить» иэ одного состояния в другое, иаэывается коиечяым иедетермииироваииым автоматом. Окавывается, что только что описаииый граф, представляющий конечный автомат, полностью характеризует схему Янова. В частности, вопрос об эквивалентности схем Якова сводится к иепосредствеяяому сопоставлению характериэующих эти схемы конечных автоматов. Теория автоматов представляет собой веаависимо и иитеясивно развивающуюся область математики, примыка»ощую к алгебре, теории алгорит.мов и комбииаторике. Тем самым работа Дж. Ратледжэ, впервые обратив виимание яа свяэь автоматов и схем программ, пополнила «техяическую базу» теоретического программирования, существенно развитую впоследствии (см., например, В. М.
Глушков, А. А. Летичевский, Теория автоматов и программирование, . 1-я Всесоюзная конференция по программированию (Плеиариые доклады), Киев, 1968). Работа Дж. Ратледжа была опубликована в 1964 г. в журнале «Ассоциации по вычислительной технике» (7. Кис)едйе, Ов !ало«'э ргойгаш э«Леша«а, 7опгпа) о( 1)»е Аээос(аИоп о1 Сожри«)пй Масййпегу, то). 11, )))о. 1, 1964, 1 — 9). Новосибирские работы. В работе А. П. Ершова «Об операторных схемах Яиоваэ, опубликованной в 20-и выпуске «Проблем кибернетики» (М., эриэ- 9 8.5. ЕЩЕ ОДИЫ ИСТОРИЧЕСКИЙ ОБЗОР матгиз, 1968, 181 — 200) было введено представление схем Янова в виде графов. Это позволило упростить аксиоматику, сделав ее в то же время более полной, в частности, аксиоматизировав с помощью верхней разметки понятие достижимостн операторов и «допуст««мости наборов.
Иаложение 8-й главы в втой книге в целом следует уйааанной работе. В 1968 г. Э. Л. Горел», еще будучи студенткой Новосибирского университета, исследовала аксноматику схем Янова и доказала независимость системы аксиом, приведенной в статье А. П. Ершова. Работа следовала методологии доказательства независимости аксиом, сложившейся в ыатематической логике (см. 1 6.3), однако поиск свойств, характеризующих ту или ияую аксиому, требовал немалой изобретательности, н доклад самой молодо«г участницы 1-й Всесоюзной конференции по программированию выавал заслуженное одобрение специалистов (Э.Л. Горель, Логическая независимость аксиоматики операторных схем Янова. Первая всесоюзная конференция по программированию, А. Вопросы теории программирования, Киев, 1968, 3 — 26)« Несколько позднее Э.
Л. Горел» в работе «О схемах Янова с отношением конечной эквивалентности» (Кибернетика, № б, 1971) построила полную схему аксиом для формальной эквивалентности, прн которой не допускаются конфигурации бесконечной длины, но возможны конфигурации, завершающиеся пустым циклом. Заключение. Автор включил в атот небольшой обзор только те работы, которые непосредственно привели теорию схем Янова к тому виду, в каком она излагается в этой книге. В то же вреыя теория схем Янова в целом существенно шире, она повлияла на ряд других разделов теоретического програмыирования, а ее внутренняя проблематика еще далеко ве исчерпана.
Автор намеревается завершить этот параграф, а вместе с ним и свои беседы обсуждением одной открытой проблемы для схем Янова, за которую брались многие, но которая окааалась достаточно трудной, чтобы ее можно было бы поместйть в книгу, ие боясь отстать от жизни. В описанной теории все операторы в схемах Янова различны и независимы друг от друга.
Вспоминая приведенную мимоходом алгебраическую формулировку, можно сказать, что в этойтеориисхемы Янова рассматривались над свободной полугруппой операторов. Однако еще в своей оригинальной работе Ю. И. Янов отметил важность рассмотрения схем программ, в которых существуют те или иные тождественные соотношения между операторами и их «произведениями». Простейшим случаем соотношений являются опюшения тождества вида А« = А, т. е. Когда, глядя иа схему, мы можем и ней «узнавать» одинаковые операторы, входящие в разные места программы.
Ю. И. Янов, а вслед аа ним и Дж. Ратледж показали разрешимостьформальной эквивалентности и ее равнообъемность с функциональной. Позднее В. Э. Иткин построил полную систему преобразований для схем с тождественными операторами. Наличие тождеств между операторами означает, что в свободнуЮ полу- группу операторов вносятся те или иные определяющие соотношения. Это сразу вызвало к жизни попытку рассматривать схемы Янова иад произвольной лолугруппой операторов. При этом, однако, ораву возникли Две трудности.
Важной информацией об операторах являются их сдвиги, т. е. перечень логических переменных, изменяемых операторами. Рассмотрение сколько-нибудь общих полугрупп оказалось возможным только для «пограничных» случаев — пустого или универсального распределения сдвигов. Для последнего случая А. А. Летичевский охарактеризовал некоторый класс полу- групп операторов, в которых можно гарантировать наличие алгоритма распознавания формальной эквивалентности схем. Другой подводный камень состоял в том, что найденные разрешимые случаи формальной эквивалентности оказывались некорректными, т. е.
формальная эквивалентность не гаравтировала функциональной эквивалентности. Это не поаволяло применять результаты теории к реальным программам. 286 ГЛ. 8. ИСЧИСЛЕНИЕ РАВНОСИЛЬНЫХ ПРЕОВРАЗОВАНИИ Особые усилия были сосредоточены на изучении схем Янова с перестановочнымн операторами, т. е. схемами, в которых возможны тождественкые соотношения вида АВ = ВА. Здесь также был найден ряд разрешимых вариантов формальной эквивалентности, но в общем случае некорректной. О другой стороны, было показано, что некоторые определения эквиьалеит. ности для схем с перестановочными операторами оказываются таковыми, что для них в принципе ие может существовать алгоритма распознавания эквивалентности.
Наконец, некоторые варианты эквивалентности упираются в сравнительно давно известные, но еще не решенные проблемы общего характера, имеющие смысл и для других разделов математики. В то же время продвижение в построении содержательных теорем для схем Янова с перестановочными операторами имело бы не только важное теоретическое значение, но и помогло бы ряду прикладных проблем программирования. Более подробные ссылки и обсуждение можно найти в работе автора «Современное состояние теорем схем программ», опубликованной в 27-м выпуске «Проблем кибернетики» (М., «Наука», 1973, 87 †7).
Автор надеется, что найдутся читатели, которые прочтут зти строчки не просто иа привычки заглядывать в конец, а прочитав зту книгу более или менее подряд. В таком случае, по-видимому, им будет понятно намерение автора не только изложить решение двух задач теоретического программирования, но и постараться продемонстрировать математический метод в действии. Читатель заметит. также некоторую несоразмерность 1-й и 2-й частей. Не исключено, однако, что изложение теории схем Янова, столь, же подробное, как и схем Лаврова, сделало бы книгу слишком затянутой и толстой.
Кроме того, как было сказано во введении, 1-я и 2-я части книги преследуют разные методологические цели. Наконец, тем читателям, которые заинтересуются вопросами теоретического программирования по существу, автор рекомендует монографию В. Е. Котова «Введение в теорию схем программ», выходящую в Сибирском отделении издательства «Наука» (Новосибирск, 1978) почти одновременно с атой книгой. УКАЗАТЕЛЬ ТЕРМИНОВ Адрес 9 Алресная часть 10 Аксиома 205 Алфавит 60 Альтеряатиза 147, 191 Аргумент 10, 64 Буква 60 Верщина 40, 6! — висячая 119 — достижимая 256, 258 — -авеада 131 — ивааидостижимая 255 — квазипродуктивная 255 — продуктивная 258 — !юзлеляющая м2 — связанная 67 — смежав я 40 67 Эоседняя 97 . — сЖйбуйай 133 — терминальная 119 — транзитная 80 Включение 56 Восприятие величины 80 Вход обобщенный 264 — фрагмента 263 Вывод условимй 208 Выводимость 205, 2!4 Выработка величинм 80 Выражение 13 Выход фрагмента 263 Вычисление 83 Гамак 173 Грамматика формальная Граф 40 — двудольный 83 — ин0юрмационный 83 — кеорнентированный 61 — несовместимости 40 — я-полный 127 — сриентированнмй 61 — переходов 48, 64, 242 Дерево !19 — вывода 205 — раввовесное 120 — раабора 195 Дпэъю пня 191 Й' ина !слова) 9, 60 ополнение 59 Дуга 61 Заглушка 259 Заключение 191.
205 Замыкание транзктивнсе О! — — обратное 101 — — ограниченное 92 Имолпнация !91 Интерпретадпя 2М вЂ” формулы 204 История операционная 247 Исчисление 205 — корректяое 206 — полное 206 Итерадия 147 Квантор всеобщности 26з Кся операции 10 Команаа 9 Компонента 54 — связности 69 Кокнатекацня 146 Конфигурация 25! — остаточная 258 Конъюнкция 191 — ортогональная 270 71орень дерева 119 Краска !!0 Марщруг 31, 35, 80 Метаязык 194 Метаперемеиная 203 Минус-с релна Множество 55 — занумерованное 57 — конечное 57 — папопняемсе М вЂ” дризиаковае 144 — равное 56 — стартовое 91 — счетное 57 — упорядоченное 57 — эквивалентное 56 Мощность 57 Набор 54 — допустимый 258, 266 — продуктивный 258 Независимость 206 Непрогиворечввость 213 Несовместимость 39, 85, 87 Номер 57 Носитель 79 Нумерация 57 Область действия 85 — задания 58 Образ 56 — транэитнвный 91 — — ограниченный 93 Объединение 56 — р фов 67 Объект абстрактный 52 — конструктивный 59 Окрестность 1-го порядка !27 Оператор !3, 64, 242' — выполнимый 270 288 УКАЗАТЕЛЬ ТЕРМИНОВ Оператор логический 226 — присваивания 13 — условный !3 — панна !3 Останов 242 Отнсюекие антирефлексивное 61 — бина рное 59 — симметричное 61 Отображение 56 — частичное 59 Отрицание 19! Оденна временнбя 126 — емксстна а ! 26 — сложности 126 Память 9, 64 ПеРебоР полный 1!7 Переменная величина 1О, 58 — — промежуточная 10 — металннгвистическая !94 — препмкатная 245 Пересечение 59 — грабов 87 Плюс-стрелка 230, 242 ПодграФ 81 Подмножество 58 Полуцикл 276 Полюс 64 Посылка 191, 205 Правило вывода 205 Прединат 226 Препшественник 6! Преемник 61 Преобравователь 242 Прианак 144 Программа 9 — символнчесная 11 ПРограммирование структурированное 148 Произведение прямое 59 Просбрав 56 — транзитивный 101 — — ог!юннченный !О! Поацесс порожпающий 252 Путь 80 Равяссильность 204 — тожпественная 204 Г Разметив 256 — верхняя 262 — Нижняя 262 — стационарная 258, 266 Разность 59 Разряд 9 Раскраска !10 — минимальная !!О Распозяаиатель 242 Распределение памяти 64 — — «аноническое 98 — полюсов 64 Расстояние между вершинами 132 Ребро 40, 6! Результат 10, 64 Связка 28, 35 — логическая 191 Свявь информационная 22, 79 Сивнг 242 Сенвенция 214 Сечение 22 — минимаксное !20 Символ нетерминальный !95 — операторный 242 — прединатный 242 — терминальный 195 Синтаксис 194 Скелет 84 Склеивание вершин !31 Слово 60 — машинное 9 Соответствие 55 Состояние памяти 245 Стрелка входная 242 Схема аксиомы 205 — интердретирсванная 245 — каноническая 270 — матричная 270 — операторная 26, 65 — равная 270 — сравнимая 246, 247 — Формулы 203 — зквивалентнан 247 Янова 237, 242 'Габлипа истинности 191 Терминал 118 Тождество 19! Условие 242 — полное 266 Устройство исполнительное 9 цюрма совершенная нормальная 199 Формула логяческая 192 — металвнгвистическая 194 — сбщезначиная 2!1 — эквивалентная 204 Юрзгмент 263 — обобщенный 264 гпуннция 59 — булеза !87 выборки 54 частичная 58 Мепочка 278 — правильная 278 Пикл 278 тзисло хроматическое !!0 Ширина 24 Шкала лагичесная 144 Эквивалентность 247 — операционная 248 — Формальная 252 Функциональная 247 Язык 194 влгорптжзчесний 12 змшиинмй 11 Ячейка 9 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
