1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 45
Текст из файла (страница 45)
Схема зацикливается при единственной свободной интерпретации 1, в которой 1 (р) (т) =- д для любого герма-значения т. При любой другой свободной интерпретации 1 схема остановится после первой же проверки предиката 1 (р), давшей значение О. Г ! ! ! ! ! ! ! ! ! ! ! ! ! Ркс. 9.2. Расшифровка оператора ез »= «д Рвс 9.3. Счотчавовля схема ов. е, которую кельзя трлнолцровать в рокуреяв.
иую схему Предположим, что в классе т" (Л) существует схема Ю, эквивалентная схеме 8 .„и пусть и — максимальная местность определяемых функциойалъных символов, употребленных в схеме Я. Зафиксируем свободную интерпретацию 1, о которой речь шла выше. Множество всех значений, которые переменная р принимает во время бесконечного выполнения программы (Я, 1 ), изобравим в виде следующей таблицы.
Столбец г Столбец о Сто Щец и уле ул+ва оглы, 1готв ва уеа уво 1ва В таблице выделены п+ 2 столбца: столбец О, столбец т,... , столбец п, столбец остальных значений. Так как программа .(8, 1 ) должна эациклитъся, а число столбцов в таблице конечно, должен существовать определяемый функциональный символ тг, каждый аргумент которого при некотором повторном рекурсивном обращении к уравненню, содержащему в левой части этот символ (вылов г), заменяется значениями иэ того же столбца, уа Й'а 1вга 1ву т'-га гвд уг' 1егеа увгеа уел* бед тгоа ув ад вобла увела ' иа которого уже бралось значение при некотором предыдущем вызове.
Предккат 1 (р) тождественно истннен на всех термах- значениях, поэтому повторные вызовы Р происходят в том же порядке, что и предыдущие обращения, и для вначений аргументов, выбираемых из тех же столбцов. Так как максимальное число аргументов Р не больше и, среди столбцов О, 1, 2, ..., п (их и + Ц существует такой, термы из которого не йспользуются в качестве значений аргументов Р при повторных вывовах Р. Следовательно, только конечное число термов ив столбца >, О ~( ( > ~ п, будет появляться в процессе выполнения программы (Я, 1 ), и существует терм 'у»у>а', который никогда не станет значением аргумента условного оператора р (у).
Зафиксируем еще одну интерпретацию 1»„ которая отличается от х лишь тем, что х»> (р)()»8>а') = — О, а для других термов по-прежнему значение преднката — х. Терм '~'у>а' не будет предьявлен предикату >»> (р) при выполнении программы (о', Х»>), поэтому эта программа зациклнтся. В то же время программа (Я з, >»,) останавливается, так как рано или повдно переменная у примет вначение ')»у>а'. Следовательно, схемы Юз,з и о неэквивалентны, что противоречит предположению.
Д Метод, которым доказана теорема, позволяет объяснить при- чину невозможности транслировать произвольную счетчиковую схему в рекурсивную. Счетчиковые схемы могут порождать (при всевозмо>кных свободных интерпретациях) богатые и раэнообраа- ные множества термов-результатов, которые не могут быть поро- ' ждены механизмом рекурсии. Т е о р е м а 9.2. Класс рекурсивных схем не транслируем .е класс счетпчикоеых схем. Д о к а а а т ел ь с т в о. Для рекурсивной схемы Юз.з. Р (х), Р (х) = если р (х) то х иначе ~(Р (у (х)), Р (Ь (х))), : которая не транслируется в стандартную схему, не существует и эквивалентной счетчиковой схемы.
Предоставляем читателю : убедиться самостоятельно, что доказательство теоремы 8.2 пол- ностью проходит и для случая счетчиковых схем. В обоих случаях причина невозможности транслировать эту схему одна и та >ке— память конечна как в стандартных, так ив счетчиковых схемах. ( ) Т е о р е м а 9.3. Класс счетчикоеых схем и класс рекурсивных схем не сравнимы ко мощноппы. Д о к а з а т ел ь с т в о. Факт существования схем Б з и Язв (теоремы 9Л н 9.2) непосредственно доказывает утвер>кдейие теоремы. ( 1 3 в д в в н е 9.3.
А. Трвкслкруйте в схему с одквм счетчиком рекурсивную схему Язл кз в»дания 8ЛА. н. Трвкслкруйтв рзкурсквкую схю>у Яз.> кз зздаккя 8ЛБ в счо>чвковую схему. 2.2. Счетчиковые и стандартные схемы. Т е о р е м а 9.4. Класс счетчикоемх схем строго мои(нее класса стандартных схем. Дока з а тел ъс тв о. Р(с) эд' по определению класса ,У (с).
Счетчнковая схема Я» (см. рнс. 9.3) не имеет эквивалентной рекурсивной схемы. Для нее не может существовать и эквивалентной стандартной схемы, так как в противном случае существовала бы (в силу теоремы ЗЛ) эквивалентная рекурсивная схема. Следовательно, неверно, что Р ~) Р (с), н класс У (с) строго мощнее класса,г". Д Доказанная теорема констатирует тот факт, что имея в своем распоряжении любое число счетчиков, мы получаем возможность конструировать схемы более мощные, чем стандартные. Однако известно,что добавление к бавису стандартных схем лишь одного счетчика не приводит к такому эффекту.
Плейстед установил, что класс схем У ((с) равномощен классу стандартных схем ((30). К сожалению, мы не можем изложить здесь доказательство этого утверждения иэ-за его сложности. Более просто устанавливается следующий результат, который сразу же вносит ясность в »проблему числа счетчиков». Т е о р е м а 9.5. Классы Р (с) и Р (2с) раеномои(нм. Д о на з а т е л ъ с т в о, 5." (с)::;т (2с) по определению. Пусть схема Я иэ класса Р (с) содержит п счетчиков с, с,... ..., с„..., с„.
Упорядочим зтн счетчики и каждый набор длины и значений этих счетчиков кодируем взаимно однозначно следующим значением одного счетчика с (значение счетчика с~ будем обозначать (сг)): 2'"' х 3'"' х... х 4' х... хг'„'«', где г, — г-е простое число в последователъности всех простых чисел. Если в схеме 8 заменить все вхождения оператора с,:= := с; + (, ( ( ге,,н на оператор с:= с Х г„ все вхождения оператора с,:= с, — $ — иа с:= с/г, и все вхождения предиката с, = 0 — на с шог) г, = О, то получим счетчиковую схему, эквивалентную схеме Я.
Построенную схему можно преобразовать в счетчиковую схему иэ класса бг (2с), что предлагалось сделать самостоятельно в задании 9.2. Следователъно, Р (2с) э,г (с), откуда и из ;г (с) ,". :5". (2с) получаем, что классы У (с) и Р (2с) равиомощны. П Таким образом, необходимо два счетчика, чтобы достичь мощности полного класса счетчиковых схем.
2.3. Счетчиковые и магазинные схемы. Т е о р е м а 9.6. Класс счегвчикоемх схем транслируем е класс лгаеаеиннмх схем, т. е. гг (М) ~ О (с). Дока за тел ъот в о. Принцип трансляции счетчиковых схем в магазинные достаточно прост. Каждый счетчик с в ксход- ной счетчиковой схеме заменяется магазином М,. Кроме того, вводится одна дополнительная переменная х (на все счетчики) и одна константа а. Переменной х ораву же после инструкции етарт присваивается константа: х: = а.
Каждое вхождение любого из трех операторов над счетчиками заменяется оператором над соответствующим магазином по следующим правилам: оператор с: = с + [ заменяется на М,:= х; оператор с:= с — [ — на х:= М,; оператор с = Π— на М, = Я. Таким образом, магазин М, имитирует работу счетчика: прибавлению единицы к счетчику соответствует увеличение «длины» магазина на единицу; вычитанию единицы — уменыпеиие длины магазина на единицу; когда значение счетчика равно О, соответствующий магазин пуст. Поэтому при выполнении интерпретированных схем (исходной счегчиковой и построенной магазинной) текущему значению счетчика, равному и, соответствует состояние - -- »..~.» .' ° * ' *.*- ° --..
и и Вопрос о трансляции магазинных схем в счетчиковые отлшким :, до п. 2.6 этой главы, где убедимся, что такая трансляция невоэ: мо>кна, и сформулируем соответствующую теорему (теорему 9Л4). 2 4. Магазинные схемы и схемы с массивами. Т е о р е и а 9.7. Класс схем с массивами транслируем в класс ~,лчаеаеинных схем, т.
е.,У (М) ~з У (А). Д о к а э а т ел ь с т в о. Прежде всего, все счетчики в схеме .с массивами Я заменяются ва магазины так, как зто делалось в доказательстве теоремы 9.6. Каждый массив А в схеме Я заме; няется парой магазинов Мл, Мл н переменной ил, а операторы иад массивами замещаются фрагментамн магазинных схем. Нэ ; рис„9„4, а показан фрагмент, аамещающий оператор А [ с):= у; на рис. 9.4, б — фрагмент, аамещающий оператор у:= А [ с); на рис.
9.4, в, е дана расшифровка совпадающих подфрагментов [ обоих фрагментов. Переменные х, ил и з — новые переменные Фв построенной магазинной схеме 8', они не входили в память схемы Ю. Переменная х играет ту же роль, что и в предыдущей ~:теореме, т. е. хранит константу, ааполняющую «магазины-счет[чики». Предполагается, что начальное значение переменкой ил ) при любой интерпретации 1 равно ! (А), ата переменная не меняет ',: своего значения при выполнении программы (К, !). Переменнав '.
з служит для организации обмена между магааинамн Мл и М„. Зквивалентность схем Я и Ю' достаточно очевидна после со: держательного анализа правил замены счетчиков, массивов и опе. раторов над массивами, магааинами и покаэаннъэзи на рис. 9.4 ,:: фрагментами магазинных схем. При преобрааовании схем с массивами в магазинные схемы использован довольно естественный и понятяый прогрэ»и«вотский прием.
Магазвн Мл отводится для :. хранения состояний массива А, причем первый элемент состояния ' всегда находится на верхушке магазина. Выборка элемента А [с! . »(«е в. к. к««»», в. к. с«е«з»Е з а 20з Ряс. 9А. Запева оператороз нал нассизанк 'фрагнеатамн нагааннних схем: е — фрагмент, ааменяаанпй А И:= Г; б — фрагмент, ааменяющнй З:= := А [е[; е — перекачка на МА а Мл, е — обратная перекачка на М а М из массива имитируется «перекачкой» элементов А [О), А [Ц,... ..., А [с — Ц из магазина Ма в магааин МА, пока нужный элемент не окажется верхушкой магазина МА. В зависимости от того, требуется ли переслать этот элемент в переменную р нлв на его место записать значенне переменной р, используются соответствующие операторы над магазинами. Затем осуществляется обратная перекачка иа Мя в МА для завершения формирования нового «состояния массива».
По определению, состояния массива — бесконечные последовательности элементов из области интерпретации, а состояния магазинов — конечные последователь ности (перед выполнением программ (8, 1) и (Ю', 1), где 1— 210 произвольная интерпретация, состояние массива А — бесконечная последовательность, состоящая из одного и того же элемен"та 1 (А), а все магазины в (К', 1) пусты). Здесь на помощь приходит переменная ил, хранящая значение 1(А).
Фрагменты магазинной схемы на рис. 9.4 устроены таким образом, что магазин Мл на каждом шаге выполнения программы (Я', А) хранит начальную часть состояния массива А, длина которой равна макси:мальному к данному моменту порядковому номеру элемента, вы' биравшегося из массива или засланного в массив. Если же при : очередной имитации выборки из массива или засылки в массив порядковый номер элемента больше глубины магазина (т. е. числа : элементов в его текущем состоянии), то используется перемен) ная ил и механизм подгонки длин состояний при перекачке иэ ) Мл в Мл (см. рис.
9.4, в, проверка Мл — — О и последующая пере) сылка Мл:= ил). П Т е о р е и а 9.8. Класс магазинных схем транслируем в класс :.схем с массивами, т. е. У (А) ~,У (М). Д ока з а тел ь с т в о. Алгоритм трансляции магазинных схем в схемы с массивами проще, чем обратное преобразование. :;Каждый магазин заменяется массивом Ам и счетчиком см, а опе'раторы над магазинами замещаются следующими фрагментами „схем с массивами: ): х:= М на $, заменяется на фрагмент ):.т:=- Ам )см), см:= см — $ иа )г' ): М:= х на й,— на фрагмент ): см .. = см + 1, Ам )см):= х иа й; ): если М = Я то й иначе т — на оператор й если с = 0 то й иначе т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
