1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 30
Текст из файла (страница 30)
Подклассы О, Э' и У мало отличаются друг от друга: для них характерно, что при любой интерпретации их базисов зна- чения переменных хг и х совпадают после выполнения начальник фрагментов программ. Точно так же подклассы У, и Уз имеют общее свойство: начальные значения переменных х, и х в общем '' случае различим и при любой свободной интерпретации символ хг не входит ви в один терм-значение переменной х„а х, не вхо- дит ни в один терм-значение переменной хг (или, как говорят, переменные хг и х, разделены).
Такое отличие подклассов первой группы от подклассов Р, и Уз существенно влияет на разреши- ' мость проблем пустоты и эквивалентности. В литературе имеются ' примеры еще более простыл неразрешимых подклассов стандарт- выл схем, чем Рм 'т'з, У . Так, в некотором смысле минимальным подклассом с неразрешимой проблемой пустоты является под- класс Рю исследованный Непомнящим И8, 125). Базис этого под- класса: у, = ((х„хд, д<п), (рп>), (х,:=~(х,), х,:= ~(хз), хг:= хм р (х,), стоп (х1, .т ))).
Сравнивая «близкие» подклассы, одни из которых разрешимы, другие неразрешимы, удается выделить те особенности схем этик подклассов, которые обеспечивают характер разрешимости. На- пример, проблема пустоты разрешима в классе,У с базисом Яг = =- ((х, д) Ф' Ю. (рот) (хг:= Ь (х). хз:= уз(х). хз:= := хт, р (хг), р (хз), стоп (хг, хз))) (48, 125). Сравнение класса Ж, с классом Р показывает, что для раз- решимости существен тот факт, что на разные переменные «воздействуют» разные функциональные символы. Если сравнить класс И» с представленным ниже классом У», в котором проблема пустоты раэрешвма (48, 125), то можно заметить, что существенным является использованне в У условных операторов, содеРжащих обе пеРеменные: 5»« = ((хд, хд), ()ддд), (Р<дд), (х,:= := 1(хд), х»:= 1(хд), х,:= х», х» д= хд, р (хд, х»), стоп (хд, х»))).
Выделение разрешимых и одновременно достаточно интересных с точки зрения практики программирования подклассов стандартных схем требует внвыательного научения различных аспектов схем, отбора и классификации тех свойств схем, которые могут повлиять на разрешимость. Такой анализ может привести к успеху только при активном сочетании программистской интуиции с изучением известньдх методов и результатов теории разрешимости в логике, теории алгоритмов, автоматов и формалъных языков.
$1. Свободные стандартные схемы 1Л. Проблемы пустоты и тотальности. Напомним, что в свободных схемах все цепочки являются допусткмыми. Переход от общего случая к свобошдым схемам ие кажется существенным сужением класса стандартных схем: программы с недопустнмымн цепочками хотелось бы считать программистским недосмотром. Но пример в конце этого параграфа (схема Яд», для которой не существует эквивалентной свободной схемы) опровергает такое рассуждение: схемы с недопустимыми цепочками дают бблыпие воаможности при программировании.
Свободные схемы представляют особый интерес в схематологии в силу того, что проблемы распознавания некоторых свойств этих схем значительно упрощаются. В частности, очень просто устанавливается разрешимость проблемы пустоты и тотальности в классе свободных схем. Т е о р е и а 7.1, Проблема пусодоты сеободнмх стандартных схем разрешима. Д о к а э а т е л ъ с т в о. Действительно, из определения стандартной схемы и определения свободной схемы следует, что свободная схема Ю пуста тогда и только тогда, когда в ней не существует ни одной конечной цепочки, т.
е. путв, ведущего иэ началъной вершины в заключительную. Если такая цепочка существует, то она допустима н существует интерпретация 1, при которой программа (8, 1) останавливается. Таким образом, распознавание пустоты свободной схемы сводится к известной процедуре 175] обнаружения того факта, что начальная и заключительная вершины в графе схемы не связаны ни одним путем. ( ) Т е о р е и а 7.2. Проблема топдальносдпи с«ободных стандаряпдмх схем разраиима. Дока за тел ь от в о. Свободная схема не тотальна тогда к толъко тогда, когда граф схемы содержит контур, т.
е. путь (1, )д, 1, ..., 1), где 1 — вершина графа. Процедура распознавания наличия контура в графе навестив (75). ( ) !36 Итак, неразрешимые в общем случае проблемы пустоты к тотальности становятся разрешимыми в классе свободных стандартных схем. А как обстоит дело с проблемой эквивалентности свободных схему Эта проблема остается открытой иа сегодияшнвй день. Многие исследователи склонны поддержать гипотезу Патерсона (119, 126) о разрешимости этой проблемы на том основания, что не удалось доказать ее неразрешимость общепринятыми методами. Но мало и результатов, поддерживающих зту гипотезу.
Решение проблемы эквивалентности свободных схем будет значительным событием в схематологии и углубит наше знание о природе неразрешимости в схемах. 1.2. Проблема изоморфизма. В задании 4.3 были определены два корректных отношения эквивалентности схем. Схемы иэоморфвы, если совпадают мьожества всех цепочек операторов этих схем. Схемы Бг и Яз в базисе М интерпретационно изоморфны, если любая интерпретация базиса порождает совпадающие цепочки операторов в Яг и Я . В задании 5.3 предлагалось доказать, по отношение интерпретационного изоморфизма не является частично разрешимым в классе стандартных схем.
Сейчас мы убедимся, что ситуация меняется, если ограничиться свободными схемами: для свободных схем интерпретационный изоморфизм равносилен нх изоморфизму, а иэоморфиэм схем можно распознавать с помощью алгоритма, очень похожего на алгоритм распознавания эквивалентности конечных одноленточных автоматов (см. гл. 3).
Обозначим через С (Ю) множество всех цепочек операторов схемы Я, а через С (Я, 1) — цепочку операторов, порожденную в 8 интерпретацией г. Л е м и а 7.1. Сгободнме схемы Я~ и 8 интернрепнщионно игоморфни тогда и только нюгда, когда они игоморфнм, т.е. С(Я,) = С(Я,). Д о к а з а т е л ь с т в о. Достаточность. Пусть С (Яг) = = С (Бз),но существует интерпретация г такая, что е = С (Яы г) чь ез = С (Яю Х). Тогда сУществУет номеР позиции 1 в обеих цепочках, до которой (включительно) префиксы цепочек ег и ез совпадают, а в позиции 1 + 1 стоят разные операторы (в случае условных операторов может быть один и тот же оператор, но с разными верхними иидексамк О и 1). Так как С (Бд) = С (Яз), змеем е„ез <Б С (81).
Это значит, что ег и г должны содержать один н тот же условный оператор на некоторой позиции у, ) ~ 1, ио с разными верхними индексами О и 1. Но это невозможно. так как в протоколах программ (Я„У) и (8, г) соответствующие состояния памяти в любой (-й конфигурации, где ) ~ 1, равны. Необходимость. Очевидна. ( ) Т е о р е и а 7.3. Проблема изоморфизма стандартных схем алгоритмичееки рогреиаьва. Д о к а з а т е л ь с т в о. Алгоритм распознавания изоморфизма состоит иа двух частей. Сначала по заданным схемам стровтся 137 конечные одноленточные автоматы, моделирующие в некотором смысле эти схемы. Затем выясняется, эквивалентны ли этк автоматы, и на основаник результата анализа делается вывод о том, изоморфны исходные схемы или нет. Пусть Я и Б — две стандартные схемы.
Зафиксируем конечное множество (гп ..., в„), состоящее из всех операторов присваивания обеих схем к условных операторов в двух экземплярах — с верхними индексами 1 и О. Выберем произвольный алфавит У, элементы которого находятся во взаимно однозначном соответствии К с элементами этого множества. По каждой из заданных схем Ю построим конечный однолеиточный автомат А (Б) над алфавитом У. Множество состояний автомата Л (8) включает: начэлъное состояние д«, состояние д„ спецвалъное «самозацикливающеесяз состояние д и состояния д, ..., д„взаимно однозначно соответствующие дугам графа схемы 8; обозначим это взаимно одяоавэчное соответствие через Ь.
Дуги графа автомата проводятся согласно правилам, изображенным на рис. 7.1, где слева показаны фрагменты графа схемы 8, а справа — соответствующие фрагменты графа автомата А (Б). На этом рисунке й: х: = т — произволъный преобразователь схемы Я; Рл если р [л,..., у) то [ иначе 1 — произволъный распознаватель схемы; К (етарт (л,..., у)), К(л:= т), К(рг (х,..., у)), К(р«(х,... У)) — элементы алфавита У; Е($, 1) — состояние автомата Л (Б), соответствующее дуге, ведущей в Я от вершины с меткой 1 к вершине с меткой у. Все осталъные дуги в графе автомата проводятся к «самозацикливающемусяз состоянию автомата д (мы не изображаем этих дуг на рис. 7.1 и 7.2).
Закшочительными состояниями автомата А [Б) объявим состояния д«, дд,..., д„д„незаключительным — состояние д . На рис. 7.2, а и 7.2, б показаны две (изоморфные) стандартные схемы Къ~ в Б ., а на рис. 7.2, е и 7.2, г — построенные по ним в соответствии с только что описанными правилами автоматы А (8 . ) и А (К,. ). Здесь У = (а, Ь, с, д, е), где а = К (старт. (х)), Ь = К(р«[л)), с = К (р«(х)), «) = К (л:= ~(х)) е = = К (стоп [х)). (Убедитесь, что автоматы А (К»т) и А (Къ«) эквивалентны.) Покажем, что Я, и Ю изоморфны тогда и только тогда, когда А (8 ) и А (Б«) эквивалентны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
