1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 40

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 40)

Отметим, что га1(Яа«, 1«) = га1 (Язп 1«), где Юз — рекурсивная схема из п. 1.2 йастоящей главы, а 1 — интерпретация из п. 2.5 гл. 4. Обе программы вычисляют 41, однако при других интерпретациях результаты схем Яз «и Язл могут различатъдя, так что рекурсивные схемы Яз «и Б„т неэквивалвнтны.

Рекурсивную схему назовем лияейлой, если в любом вызове Р (т„..., т„) термы т,..., т„(называемые также фактическими лараметрали этого вызова) являются базовыми. В доказательстве теоремы 8Л мы фактически доказали болев сильное утверждение: класс стандартных стем эффективно транслируем в класс линейных рекурсивных схем. Описанный алгоритм трансляции стандартных схем в рекурсивные не строит «оптималъные схемыэ. Из него следует, что стандартная схема с ш отличными от преобразователей вернпшами и я переменными транслируется в рекурсивную схему с т уравнввиямтьи с я переменными.

Можно лисконструировать алгоритм, которыя транслировал бы любую стандартную схему (или хотя бы любую унарную стандартную схему) с и переменными в рекурсивную схему, в которой любая определяемая функция имеет меньшее колвчество переменных, скажем, и — И Ответ на этот вопрос, и ответ отрицателъный, дал Чандра (881. Для следующей стандартной схемы Юз т с переменными уы... $81 ..., У„не существует эквивалентной рекурсивной схемы, в ко- торой все определяемые функции содержали бы не более п — 1 переменных. у„л: (старт, 1: уе..=а, 2: Уе:= у(У1) 3-' Уе -= ~ (Уе) ° и: у„:= ~(У„1), п + 1: еслв р (у,) то и + 2 иначе Зп + 1, и+ 2: еслв р(у) то и+3 иначе Зп+1, 2и: если р (у„) то 2п + 1 иначе Зи + 1, 2п+ 1: У1:= у(уг)» 2п + 2: уе: = у (уе), Зи: у„:= у (у„) на и +1 Зи+ 1: стоп (уг)) Зада ы не 8А.

докажете утэерждевэе о тревелвдэв схевм Ле.». 2.3 Трапслвцнв рекурсивных схем в стандартные. Т е о р е м а 8.2 (Патерсон — Хьюитт). Лласс рекурсивных схвв нс гнранслирусм в класс стандарвпяех схем. До к а за тел ъ ство. Патерсон и Хьюитт привели пример рекурсивной схемы, для которой не существует эквивалентной стандартной схемы [129).

Это линейная схема Лье из примера з п. 1.2 этой главы: ~е е' р (х)» р (х) = если р (х) то х иначе ~ (р (у (х)), Е (й (х))). В общих слонах, причина нетранслируемостн этой схемы состоит в следующем. Прн варьировании интерпретаций возникает необходимость запомнить сколь угодно большов число промежу"гочных значений, в то время как память любой стандартной схемы подержит фиксированное конечное число переменных. Рассмотрим класс свободных интерпретаций (Е„! п ~ О), в которых прадикатный символ интерпретируется следующим образом: 1 , если т содержит ровно и вхождеивй символов из Е„(р) (т) = множества (у, й), О в противном случае. Резулътатом произволъной программы (Яе.е, 1„) служит термэначение т„такой, что те =,э т, = 7 (у (х), й (х))', г„= 'У (те,1 (у (х)), г 1 (й (х)))'.

Например, результатом программы (о а, Тд) является бесскобочный терм т, = 'Иуу йул!Ф ~~ ~. Термы-результаты можно представить в виде следующих деревьев: Т (для т ), Т (для г ) и т. д., показанных на рис. 8.2. Вершины З1 41 Рлс. 8.2. Прадстлллояяо теряев-результатов в виде деревьев: а — Тд для тд, б — да для дд; а — Тд для тд деревьев перенумерованы по уровням — корень имеет номер 1, номера вершин второго уровня 21 и 22 и т.

д. В дереве Т„для терма г число уровней равно и + 1. Предположим, что существует стандартная схема 8, эквивалентная схеме Юа д. Без потери общности можно предположить, что схема Я не содержит новых функциональных символов, и все операторы присваивания, использующие символ Г, имеют вид у,:= ~(у., у„), где уо уд, у„— переменные из памяти схемы Ю. Рассиотуйи пРогРаммУ (Б, 3„). Если о' ва.а, то чад (Ю, 4 ) = = т„. Каждой вершине дерева Т„соответствует подтерм — промежуточное значение при вычислении герма т„.

Подтерм однозначно восстанавливается из поддерева, корнем которого служит зта вершина, и будет называться значением вершины. В протоколе выполнения программы каждому очередному выполнению оператора уд:= ~ (ут, у„) с двухместным функциональным символом ~<ад соответствует продвижение вверх по дереву от двух соседних вершин одного уровня к вершине следующего уровня. При этом значение каждой вершины дерева Т„должно запоминаться и храниться до тех пор, пока не станет возможным переместиться на следующий уровень. Следующий фрагмент соответствует выполнению оператора у;:= Е(уп уз): где уг хранит терм сн уг — терм т„а у; — терм Е т~т,.

Переменная уг может быть или уп или у„, но в целом такой фрагмент требует по краиней мере две переменные для запоминания промежуточных результатов. Индукцией по л легко устаяовнть, что для вычисления терма т„в программе (8, Е„) необходимо иметь и + 1 переменную для запомвнания промежуточных значении вершин дерева Т„.

Действительно, при и = О требуется одна перемеяная. Дерево Т„конструируется из деревьев Т и Т г по следующей схеме: Если Т„требует яг переменных и Т„1 — н переменных, то дерево Т„потребует шах (нг, н~ + 1 переменную, т. е., учитывая начальный шаг индукции, Т„потребует и + 1 переменную.

Предположим, что стандартная схема Я, эквивалентная рекурсивной схеме 8 г, имеет й переменных. Результат рекурсивной программы (Юьг, Ег) — терм тю Для того„чтобы программа (Я, Ег) вычислила тот же терм, необходима Й+ 1 переменная, что приводит к противоречию. Таким образом, не существует стандартной схемы, эквязалентной рекурсивной схеме Ю л. ( ) Итак, установлена транслируемость стандартных схем в рекурсивные и одновременно существование линейной рекурсивной схемы, для которой иет эквивалентных стандартных схем. Эти два факта объединены в следующий теореме. Т е о р е м а 8.3.

Класс рекурсивных стев строго мощнее класса стандартннх сеем. Д о к а за тел ь ство. Прямое следствие из теорем 8.1 в 8.2, 1з1 3 э д э в и о 8.5. Устоковвто, хожво лв траксэкровэть в стэвдартаиь схемы следу«яцко р«кур«квакв схокы: а) д«.«: Р (в). Р(я) = всяк р(я) то )(я) вва»е Л(я, Ру»(я))); В) схоку дь«. $ 3. Лииеииые уиариые рекурсивные схемы ЗЛ. Проблема трансляции. После того, как установлена невозможность трансляции проиэволъной (линейной) рекурсивной схемы в стандартную, естественно начать поиск такого подкласса рекурсивных схем, который транслируем в стапдартныв схемы. Интерес представляет подкласс рекурсивных схем, построенный по аналогии со схемами Янова. Класс укорных рекурсивных схем имеет базис с е)п»нстввнной переменной х и одноместными функциональными и предикатными символами. Класс линейных унарных рекурсивнь»х схем (или класс схем де Беккера — Скотта) — это подкласс унарных схем, в которых всякий вызов содержит в качестве фактических параметров только базовые термы.

Иапрнмер, рекурсивные схемы 8 и Ю из задания 8Л являются унарными, схема Я„д — линейной унарной. Т в о р е м а 8.4 (Патерсон — Хьюитт, Гарланд — Лакхзм). Класс линейных унарных рекурсивных схем транслируем в класс стандартных схек. Доказательство. Предварительные эам е ч а и и я. Не уменьшая общности, можно предполагать, что все логические выражения имеют вкд р (х), где х — переменная, главный терм схемы — вид Р (х), а сама рекурсивная схема В задана в следующем виде: о) р» (х), Р, (х) = волн р» (х) то и»Р»»ер»х иначе у»Р,»»> 6»х ($ «~ Ф ~ и), где р» — некоторый предикатный символ; а;, р», у», 6» — цепоч ки иэ базовых функциональных символов; Рд»>, Р,»»» — опрвде ляемые функциональные символы левой и, соответственно, пра вой альтернатив, причем О «~ » (») ч, и и О~ г (») ч: и. Условимся, что Ро — пустая цепочка, и если» (») = О, то с»» пусто, а если г (») = О, то у» пусто.

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

Если этот символ— Ри то очередное значение в протоколе получается с помощью под«) Если правая часть кекс«срого уравнения — простой терм «, то ого можно заковать вв условный терм; сова р (я) то т вквчо т, где р — проиавольвий предккэтяый символ.

»35 сгановки на его место одной из альтернатив»-го уравнении. Пусть выход схемы достигается после л» шагов выполнения схемы при некоторой свободной интерпретации !. Результатом программы (В, 1) будет тогда бвсскобочный терм-значение Р„Р,... Р, Я„,Я„,,... Яап»х, левая часть реаультата лрааая часть реатльтата Рч»зи если (Рч»а»)» (и„,...

Характеристики

Список файлов книги