1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (Котов, Сабельфельд 1991 - Теория схем программ), страница 2

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

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

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

На базе одного иэ наиболее изученных классов схем — класса стандартных схем — вводятся главные понятия, конструкции и проблемы схематологни. В пятой главе сосредоточены «отрицательные» результаты о невозможности получения алгоритмического решения главных проблем для стандартных схем и их поднлассов. Шестая и седьмая главы посвящены разрешимым случаям проблемы эквивалентности стандартных схем: разр«впнмость достигается либо эа счет рассмотрения эквивалентности более сильной, чем функциональная (отношение изоморфизма схем, логнко-термальная экшшалентность), либо эа счет сужения класса рассматриваемых схем (класс сквозных схем).

В восьмой главе изучаются схемы рекурсивных программ, проблемы взаимной трансляции рекурсивных схем и стандартных схем. Девятая и десятая главы содержат изложение результатов сравнительной схематологин, изучающей различные классы схем программ, отношения между ними и задачи трансляции одних классов схем в другие. Несколько слов о том, как возникла эта книга. В 1978 г. (.ябирское отделение издательства «Наука» издало небольшим тиражом монографию «Введение в теорию схем программе, которую первый из авторов написал на основе чнтавшегося им в $973— $976 гг.

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

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

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

обзор и комментарии к гл. 8). В основном тексте ссылки на литературу приводятся не всегда, чаще онн сосредоточены в обзорах, завершающих каждую главу. Список литературы в конце кпвги ни в коей мере не претендует на библиографическую полноту; за редким исключением он содержат только упоминаемые в тексте публикации. Авторы считают своим прпнтным долгом выразить благодарность А. П. Ершову, В. А. Непомнящему, И. В. Поттоснну, А. А.

Летичевскому, С. С. Лаврову и Р. И. Подловченко за плодотворные дискуссии, повлиявшие на формирование взглядов авторов на современную теорию схем программ. гллвл т ВЬФЧИСЛИМОСТЬ И РАЗРКШЖИОСТЬ Основу рабочего аппарата теории схем программ составляют собственные, оригинальные понятия, являющиеся абстракциями реальных объектов программирования. Математический инструментарий, нсполъзуемый для конструирования этих понятий, н техника исследований занмствуются из классических разделов дискретной математики — теории алгоритмов и автоматов, логики, алгебры, теории графов, математической лингвистики. Такое разнообразие применяемых математических средств — следствие объективной сложности основного объекта исследований — программы.

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

$1. Вычислимые функции, алгоритмы 1 1. Функция. Все объекты и понятия в этой книге строятся (или, прн неформальных определениях, могут быть построены) из сия«алое (букв, цифр, математических и специальных знаков) н нелмз неотрипаюпелъмыз чис«л (будем их называть просто числами) с помощью теоретлко-множественных понятий — множеств, упорядоченных множеств (наборов), фулкцнй и отношений. Мы полагаем, что читатель знаком с элементамн теории мноаеств н логики, поэтому ограничимся лишь некоторымк соглашениями об обозначениях. Множества будут аадаваться явным перечислением (с использованием многоточия) своих элементов, заключенным в фигурные скобки, а наборы — таким же перечислением в круглых скобках. Другой способ задания множества: 9 (х~ р(хЦ, где х — переменная, значениями которой являются некоторые объекты, а Р— свойство тех и только тех значений х, которые являются злементами задаваемого множества.

Например, ((х, у) (х и у — числа, и х с у) — множество всех пар чисел таких, что первое число не превосходит второе. Напомним, что ' Мг х Ме Х... х ̄— декартово произведение множеств М, М,, М„, т. е. множество ((т„т,..., т„) [ тг ~ б= М„те Е= Ме,..., т„6= М„), а М" обозначает произведение МХМХ...

ХМ. а пм Приведем также общее определение функции, чтобы иметь далее воэможность сравнить зто определение с определением вычислимой функции. Фующией, отобрасхакпцей мнохсестео Х ео мнохсеапео У (обозначение Г: Х -+ У), называехся множество Г ~ Х Х У такое, что для любых пар (х, у) б= Г и (х', у') б= Г нз,т = х' следует, что у = у'. Множество (х ~ (х, у) ~ Г) — область онедеяения функции Г (илн множество значений ее аргумента); множество (у ~ (х, у) б= е— : Г) — область значений фунтреи. Коли областью определения функции Г: Х-+ У служит все множество Х, то à — есюду определенная фунт)ия, в противном случае — частичная.

Конкретные функции будут задаваться не только в виде множества, как предписывает определение функции, но и менее формально, по следующей схеме: Г(х) = Е, где х — переменная- аргумент со.значениями во множестве Х, а Š— выражение, связывающее значения функции (алементы из У) со значениями аргумента х. Например, Г(х) = х, нли Г ((х„х)) = х + х, или ~ а, если х)а, Г(х) = 1 Ь в противном случае. Функцию Г: Х-+ У называют и-местной функцией над множеством М, если У = М и Х = М". Так, если х и х в примере — переменные, значениями которых являются числа, то функцию Г ((х1, х )) = хг + х можно считать двухместной функцией над множеством чисел (и упростить запись, убрав одну пару скобок).

Суперпозиция двух функций сопоставляет паре функций Г: Х У и Г; У Е третью функцию Ге: Х-~Я такую, что (х, з) б= Г, если и только если х б= Х, з б= Я и существует у б= У, при котором (х, у) ~ Г, и (у, з) Е- "Ге. Запись Гз (х) = Г, (Г (х)) тдает Г как суперпозицию функций Г1 и Г . Определение супер- позиции пары функций естественным образом переносится на наборы функций проиавольной конечной длины.

Предикатом называют функцию, областью значений которой служит множество символов-цифр (О, х). При атом говорят, что 10 предикат Рз Х-»- (О, Ц истинен для х 6= Х, если Р (х) = 1, и лозсен, если Р (х) = О. Оп»нои»ение на мнохсескые Х вЂ” это двухместный предикат Р: Хз-». (О, Ц. 1.2. Словарные функции. Выделим класс словарных функций, играющий в дальнейшем особую роль наряду с числовыми функциями, т. е.