1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 25
Текст из файла (страница 25)
Следовательно, построенная схема свободна тогда и только тогда, когда задаинаи система Поста ие имеет решений. Имея вовможность строить подобные схемы и предположив частичную рьзрешимость проблемы своболд, получаем алгоритм частичного ргспозвавания пустоты системы Поста, что приводит к противоречию.
( ) $08 Рис. б.у. Стацвартваи схема 8з.р, построевиаи по системе Песта (Х, У) Задавив б.б. Полазать, что ие яелавтси частично рззрешвиымп следувицие проблемы: а) проблема пустотм сппсыртвых стем па миоиыстее коиечвыи иитерпрзтаций; б) проблеме потеицмзльиой зацииливаемостп (иетстальвости) стпидартмыл сзвм — алема 8 потепциальио зациилпваетси (ие тотвльиа), если существует мота бы одиа и птерпретацпи 1 базиса саемм твиая, что протрзммв (8, У) зациилпваетси; в) проблема пптерпретациопиото пзоморфиама ствпдартвыа стем. 3 а д е и в е 5.4.
Локаэеть, что частичке реерешвмм следующие проблемы: е) проблема потепциельиой остановки (пепустатм) стэвдертвмх схем— схеме б потекциельво сстеиаелвяеется (ие пуста», если сущесткует хотя бм одна иитерпретация у базисе схемы такая, что программе (о, 1) естекаелв веется: б) проблеме питеициальиой остепоеки при коиечиой кктерпретецви: е) проблема потенциальной еециклиееемости при коиечкой иятерпретецаи. Краткий обзор и комментарии Неразрешимость проблемы функциональной эквивалентноств была установлена неэависымо Патерссном совместно с Лакхэмом в Парком [т26, И9) и Латичевским (3(, 32).
Докааателъство Патерсона использует нераарешнмость проблемы пустоты двухголовочыых автоматов (Лакхэм и Парк ранее дали косвенное доказательство нерва решимости функционалъыой зквнвалеятности). Доказательство Летичевского опиралось на неразрешимость функционалънойэквивалентности дискретных преобразователей †автоматов, предложенных Глуп)ковым дтя моделирования вычислительных процессов (6, 7). В работах (И9, т26) показана неразрепшмость целого ряда проблем для стандартных схем, в том числе неразрешимость проблемы свободы н неразрешимость слабой эквивалентности схем (см. задание 4.3Б).
Показано, что любое отыошекпе эквивалентности схем более сильное, чем слабая эквивалентность,но более слабое, чем функциональная эквивалентность, ые является частичыо разрешимьпт. Иткин н Звиногродский П08) показали, что любое нетривиальное интерпретационное отношеяие экзивалептностк в полном классе стандартных схем ие будет разрешимым. Нетривиальность отношения эквивалентности состоит в том, что (т) из неэквивалентности схем 8, и 8, следует, что существует ивтерпретацяя 1 такая, что та) (8ю 1) чъ та! (8„1) плв одна на программ останавлывается, а другая аацнкливэется; (2) для того, чтобы 8 и 8 были веэквквалентными, достаточно существоаания такого оператора в общем базисе, который бы входил в цепочку схемы 8„ порождаемую некоторой интерпретацией 1, но не входил бы в цепочку схемы 8„ порождаемую той же интерпретацией, вля наоборот. Неразрешимость проблемы фуыкциональыой эквивалентности стандартных схем может быть также выведена как следствие из установленной Карпом и Миллером (ИЦ неразрешимости функциональной эквивалентности схем параллельных программ.
ГЛАВА 8 ЛОГИКО-ТЕРМАЛЬНАЯ ЭКВИВАЛЕНТНОСТЬ СТАНДАРТНЫХ СХЕМ Логике-термальная эквивалентность была введена в п. 3.5 гл. 4 как неивтерпретацнонная эквивалентность, т. е. при ее определении мы не испольэовали понятия явтерпретации. Важность этой эквивалентности обусловлена обстоятельствами, имеющимн существенное значение с практической точки зрения.
1. Лт-эквивалентность, как показано в гл. 4, корректна. Это означает, что если мы ограничимся преобразованиями, сохраняющими лт-эквивалентность, то такке преобразования не будуг нарушать и функциональную эквивалентность схем. 2. Лт-эквивалентность, в отличие от функциональнои эквивалентности, является разрешимой. Более того, как будет показано в этой главе, существует не слишком сложный (полиномнальвый) алгоритм распознавания лт-эквивалентности стандартных схем. 3, Класс схем, лт-эквивалентных заданной схеме, является достаточно «широкимз, чтобы допускать такие преобразования, как перестановку преобразователей на линейных участках (т. е. фрагментах, не содержащих распознавателей), расщепление операторов (например, замену оператора у:= у Ц (х)) на последовательность г:= ~ (х), у:= у(г)), переименование перемецных, встав-.
ку и удаление неиспользуемых преобразователей. В этой главе будет построена полная система лт-эквивалентных преобразований стандартных схем. Из определения лт-эквивалентности вытекает, в частности, что для подкласса стандартных схем, не содержащих распознавателей, лт-эквивалентность совпадает с функциональной эквивалентностью. С другой стороны, лт-эквивалентность не допускает существенной перестройки логической структуры схемы, в частности, лт-эквивалентность нарушается уже при удалении таких, например, инструкций, как если р (х) то ш иначе ш.
В атом смысле лт-эквивалентность является как бы антиподом яновской эквивалентности (77), которая фиксирует последовательность преобразователей, но позволяет осуществлять глубокие преобразования логических фрагментов. $ $. Фрагменты и их преобразование $.1.
Фрагменты. Для формализации понятия (правила) пре. образования нам понадобится понятие фрагмента стандартной схемы. Понятие фрагмента является обобщением пошпия схемы. Обобщение, по-существу, состоит в том, что снимается ограннче- Ш. «г« ние, сформулированное при определении стандартных схем: граф фрагмента, в отличие от графа схемы, может содержать свободные дуги (входи и выходы). При атом входы и выходы фрагмента занумерованы натуральными числами таким обрааом, что номер каждого входа отличен от номеров всех остальных свободных дуг фрагмента (заметнм, что всякая висячая дуга получает при этом два различных номера — номер входа и номер выхода). Толъко такие нумерации свободных дуг, называемые лраалльлмми, н будут рассматриваться в дальнейшем. Кроме того, каждой свободной дуге фрагмента приписано некоторое конечное множество переменных, называемых резуаьтагпами охода в случае входа н аргументами емхода в 4 случае выхода фрагмен- «х) «х«та (отметим снова, что «;У) висячие дуги имеют как й'в м у:-Гулу реаультаты входа, так и аргументы выхода).
Прн «г« этом выходи с одинакот ными номерами имеют Раь. 6Л. Првкер фрагяеата одинаковые множества аргументов. В приведенном на рис. 6.1 примере фрагмента три входа е номерами 1, 3, 4 и два выхода с одним и тем же номером 2; (у) — множество аргументов каждого из выходов с номером 2, (х, у) — множество результатов входа с номером 1, «х) — множество результатов каждого иэ входов с номерами 3 и 4. Оператор старт (х» ..., х„) вместе с выходящей иэ него дугой, если только он присутствует во фрагменте, условимся также считать входом фрагмента с номером «) и приписанным ему миожеством результатов (х, ..., х ).
Тогда понятие схемы становится частным случаем понятия фрагмента. Пусть Вх (6) означает множество номеров входов, а Вих (6)— множество номеров выходов фрагмента 6. Всякое отношение эквивалентности Е, заданное для схем, моншо теперь распространить на пары фрагментов См С, для которых 1) Вх(6,) = Вх(6,); 2) Вх(6;) Д Внх(бу) =О (1~1, /ч 2, «чьу)„- 3) выходы с одинаковыми номерами имеют одинаковые множества аргументов выхода.
Для пари фрагментов б, См удовлетворяющих этим условиям, зафиксируем какой-нибудь линейный порядои т на объединении множеств переменних, встречающихся в этих фрагментах, а также натуральное л ® Вых (6,) Ц Вих (С ). Пусть С вЂ” один иэ фрагментов пары С, С. По всяким натуральным «Е= Вх (С) н / ЕБ Внх Щ Ц Вых (Сэ) Ц (л) построим схему Са Л, которая получается из С следувицим образом. 1. Из С удаляются все входи, кроме входа е номером у. 2. Все выходы с номерамв, отличники от у, присоединяются к оператору петля (добавляющемуся к С, если его там нет). ых 3. Если ) ~ и, то все заключительные операторы фрагмента заменяются ва операторы петля (ведущие к ним дуги остаются без иэмененвй).
4. Если в б есть выход с номером ), то он првсоединяетсн к добавляемому к б оператору стон (рт,..., уе), где ут,..., у„— аргументн выхода с номером у в том порядке, который индуцируется порядком т. В далънейшем мн ограничимся рассмотрением только правильных (ораглеплим С, т. е. таких, что либо Вх (С) = Я, либо для всех ) ~ Вх (б) и для всех ) Е- "Внх (б) Ц (и) б<'и — правильная схема. При перечисленных условиях мн говорим, что фрагменты бт в С Е-акеиеалептни, если схемы б~т' и бе~' Е-эквивалентны ц )) ). )) пля всех ) ~ Вх (С,) и для всех р' Е Вых (Ст) Ц Внх (бе) ) ) (и).
Заметим, что это определение объявляет эквивалентными (в любом смысле) всякие дза фрагмента оеэ входов и согласовано с определением фушщноналъной эквивалентности схем. Понятия пути, цепочки, термалъного значения терма на пути, а также лт-исторнн пути естественным образом переносятся на фрагменты. 1.2. Икфорншп)оияые мар)пруты, зацеплеиноеть и влвание. Ииформациоипым маршрутохе перехееппой х во фрагменте б называется всякий путь )о, = А А ... А„,А„такой, что 1) А, — вершина илн вход с результатом х; 2) А„ — вершина или выход с аргументом х; 3) путь Ае... А„не содержит ии одной вершины с результатом х.
При этом вершины, содержюцнеся в пути А ... А т, называются епутреппих)и еершилах)и этого х)ари)рута. О каждой иэ дуг пути )е говорят, что маршрут проходит по этол дуге. )х) Опишем, как строить информационный граф заданного фрагмента б. Вершянами информационного графа являются реэулътаты операторов и вхсщов фрагмента б, ))) х ) х:-т) х 1 а также аргументы операторов н выходов фрагмента С.
Информацвонваядуга проводится отреэультата х оператора или входа А) к аргументу х оператора или выхода У ' У' стев ( у ) А тогда и тольно тогда, когда в б существует маршрут Ат... А рве. а.х ф)нтиеат ое. н его наперемениой х с началом А, и кон- Форкалвоавий граф цом А„. Иэ наших определений следует, что все аргументы и результаты, прннадлежащве одкой и тои же компоненте связности информационного графа фрагмента, должны соответствовать одной переменной. Две переменные фрагмента 6 аа((еплеыы, если в 6 имеется хотя бы одна дуга, по которой проходкт маршрукы каждой нэ этих переменных.
В противном случае переменные мг за((еялемы в 6. Понятие аацеплевкости переменных понадобится нам для формулировки преобразования замены переменных. Например, во фрагменте Сг,т на рис. 3.2 переменные х и у не аацеплены, поэтому все вхождения переменной р можно заменить на переменную х. Будем говорить, что пери(има (или резулыаат входа) А елилегя ма вершину (илв выход) В фрагмента 6, если выполнено одно из следующих условий: () А — преобразователь, в существует маршрут А ... В некоторой переменной х во фрагменте 6; 2) А — результат некоторого входа С, и существует маршрут С ... В некоторой переменной л во фрагменте 6; 3) существует некоторый преобразователь С такой, что А влияет на С, а С влияет на В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
