1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 48
Текст из файла (страница 48)
е. У (А) ) )У (К) и У (А) ) У(Р). Д о к а э а т е л ъ с т в о. Так как класс У (М) строго мощнее классов У (В) и У (Р) (см. теорему 9.12), а классы У (А) и Э' (М) равномощны (см. теорему 9.9), класс ег (А) строго мощнее класса У (Н) н класса Э' (Р). ) ) Т е о р е м а 9Л4. Клаве магллиниых схем строго модциее класса ечедичикомзх схем, т. е.,У (М) ) У (с). 221 Д о н а з а т е л ь с т в о.
Э' (М) ~ У (с) по теореме 9.6. Если предположить, что классы У (М) н Э' (с) равномощны, то окажется (см. теорему 9Л2), что иласс У (с) строго мощнее класса У (К), а зто противоречит теореме 9.3 ( ) Т е о р е и а 9Л5. Класс схсм с массивами свзнмо можаев клагва счгтчикогых схаи, т. г. 'У (А) ) 'г (с).
Д ока за тел ь от в о. Э'(А) г У (с) по определению. Если предположить равномощность классов У (А) и Э' (с), то окажется (теорема 9ЛЗ), что класс У (с) строго мощнее класса $ (К), а зто противоречит теореме 9.3. [ ) Т е о р е м а 9Л6. Класс магазинных схем строго моор»гг класса стандартных схем, т. г..'г (М) ) Э'. Докааательство. Следует из теорем 9Л5 и 8.3. Д Творе ма 9Л7.
Класс схем с массивами строго мощнгг класса стандартных схем, т. г. У (А) ) ~У. Д о к а а а т е л ь с т в о. Следует из теорем 9Л5 п 9А. ( ) Диаграмма на рис. 9.9 дает полную информацию о сравнительной мощности классов схем У, У (с),,У (К), У (Р), У (М) и У (А). Стрелки указывают на возможность транслировать один класс схем в другой, номера около стрелок — ссылки на теоремы.
Рас. 9.9. Сраеаеавв аогзых частых классов схем арггргыы Диаграмма на рис. 9.9 покааывает, что классы магазинных схем и схем с массивами являются уннверсалънымн в том смысле, что схемы из любого класса можно транслировать в схемы, обогащенные магааинамн нли массива»ж. В то же время, нз етой два»раммы ие видно, какое минималыюе количество дополнительных средств необходимо, чтобы достичь выразительной мощности того пли нного класса.
В частности, в диаграмме нет информации о том, какой класс является »минимальным увиверсальныы», т. е. являясь универсальным, использует минимум дополнительных средств. Диаграмма на рис. 9ЛО дает частичный ответ па ати вопросы. л22 Ркс. 9.10. Мкаамальвые классы, раэкомолшые полным классам Чтобы не загромождать рисунок иабыточной информацией, некоторые стрелки, указывающие транэитввную транслируемость, опущены. Введены дополнительные обозначения: У (и), где л = $, 2,..., обозначает класс стандартных схем, базис которого содержит конечное число неремепных, ве большее л; И (Ф) — класс магазинных схем, в которых отсутствует условный оператор проверки пустоты магазина; У (В, 1п) — класс линевных унарных рекурсивных схем; У (В, г1п) — класс праволинейных унарных рекурсивных схем; Р (В, л) — класс рекурсивных схем с п переменными.
Около стрелок, указывающих не обсуждавпгиеся в этой главе результаты, поставлены ссылки на литературу. Диаграмма не требует специальных комментариев, аа исключением одного: остается открытым вопрос о мощности класса схем с двумя магазинами,У (2М). Существует пшотеэа [87), что этот класс не является универсальным, хотя я «близок» к универсальным классам У ($М, 2«),,У (ЗМ), У (1А).
После того, как построена диаграмма сраввителыюй мощности равных классов схем программ, естественно возникает вопрос, какие свойства тех илн иных программных средств (н методов программирования) ответственны эа положение соответствующего класса схем в иерархии классов. Анализ доказательств позволяет выделить следующие интуитивные факторы, определяющие мощность данного класса.
$. Объем яалюаи. Стандартные схемы имеют ограниченную память. Возрастание числа переменных в стандартных схемах увеличивает их мощность, но в ограниченных пределах. Счетчиковые схемы имеют также ограниченную память. Поэтому ставдартвъю и счетчиковые схемм, свободно кнтервретнрованные, не могут строить «слишком длинные» термы. Переход к рекурсивным схемам, имеющим неограниченную «внутреннюю» вамять, введение магажшов н массивов, емкость которых не ограничена, снимают этот недостаток стандартных я счетчиковых схем.
2. Гибвосшь управлеиия. Добавление к стандартным схемам счетчиков (более одного) дает дополнительную воаможвость контролировать ход вмнолнения интерпретированных схем и, тем самым, удается более оперативно организовать «синхронизацию» циклических фрагментов, прекращение выполнения н т. п. Магазины и массивы сочетают воэможности не ограниченной памяти с воэможностями счетчиков (магазины могут моделировать счетчики, схемы с массивамн содержат счетчики). Поэтому не удивительно, что У(М) и У (А) — сам»в мощные из рассмотренных классов.
(Заметим, что если одного массива достаточно, чтобы класс стал универсальным, одного магазина мало, так как он может моделировать лишь один счетчик.) Краткий ебзер и ком»«евтарни Работы Стронга (»38, $39), Патерсона и Хьюитта (»29) по исследованию трансляции рекурсивных схем в стандартные и, в частности, доказательство того факта, что класс рекурсивных схем строго мощнее класса стандартных схем, а добавление счетчиков увеличивает выразительные воэможности схем, стимулировали сравнительные исследования различных классов схем, полученных обогащением стандартных и рекурсивных схем дополнительными программными конструкциямн.
Достаточно полная сводка результатов атих исследований со ссылками на работы, в которых ови были получены, содержится в диаграммах на рис. 9.9 н 9ЛО. Иэ последней диаграммы видно, что наиболее активно изучались магааинные схемы, н здесь еще работа не завершена (открыта проблема двух магазинов).
В лвтературе рассматривались и другие обобщения стандартных и рекурсивных схем. Прн доказателъстве транслируемоств классов У (В) и,У (Р) в класс У(М) нсполъэовались в качестве промежуточных схем 2«4 магаавнвые схемы, в которых есть воаможность запоминать метки. Лемма 9.4 говорит о том, что классы У (1М, Ь) и У ($М) равно- мощны. Более общий факт установлен Грисом и Констеблем [921: классы У (М), У (А), Р (М, Ц и,У (А, Ц равномощны, но пары У (М), 4У' (М, 1.) и У (А), Р (А, А) не являются эффективно равномощнымн, а именно: хотя для л1обой схемы иа класса д".
(А, Ь) (или У (М, Х)) существует эквивалентная схема в классе У (А) (илн Э' (М)), эффективно транслировать первую во вторую нельзя. Грис и Констебль [921, а также Браун и Шымански [871 обогащалн схемы маркерами. Каждая схема ямеет конечное множество символов-маркеров [т1, тг, ..., т„), ивтерпретврованвые переменные для аапоминания маркеров и два оператора над марнерами: и: = т — оператор гапоминанил маркера, и = т — оператор проверки еовпаденил маркера, хранимого в переменной и, е маркером т. Показано, что класс У (А, Ц и класс У (А, т) (т. е.
класс схем с массивами н маркерамн) раввомощны. Добавление же маркеров в стандартные я рекурсивные схемы не увеличивает, против ожидания, мощности атих классов, т. е. классы У и У (т) равномощны и классы У ([Д) я У (11, т) равномощны. С другой стороны, усиление дзумагаэинных схем нз класса У (2М) маркерамн дает класс У (2М, т), который равномощен классу,У (М). Введение многомерных массивов не увеличивает мощности класса У (А) [871.
Чандра [881 рассмотрел стандартные схемы, обогащенные очередями. Очередь — это потенциально бесконечная память типа гПгО (г[гз$-1п-Г[гзФ-Оэь — данное, записанное первым, выбирается первым), в то время как магазин — память типа в[10 (г[гэ$-[п-1аз$-Оиз — данное, записанное последним, выбирается первым). Состояние очереди — конечный набор элементов 4, Аг, ..., е[„ нз области интерпретации.Над очередями определены тря оператора: д:= х — вопиеь в очередь д; х:= д — выборка иг очереди д; д = Π— проверка пустоты очереди д. Оператор записи в очередь д:= х меняет состояние очереди 4, е[г,..., И„на новое состояние Им Ыг,..., И„, 4 где И вЂ” текущее значение переменнон х. Оператор х:= д меняет состояние очереди Ыг дг.
° ° " 4» на состояние Иг,..., И„, а г[г становится значением переменной х. Установлено, что класс схем с очередями У (д) и класс схем с массивами У (А) равномощвы. В частности, равномощны классы Р ([д) и й". (1А), поэтому класс У (1д) строго мощнее класса У (1М), н зто говорит о том, что очередь является более мощным средством, чем магазин. Понятно, что обогащение стандартных схем такими иавествыми конструкцяямн, как операторы цикла, условные операторы типа есля (логическое выражение) то (оператор) виаче (оператор) илн введение блочной структуры не добавляют новых возможностей: любая схема из такого обогащенного класса легко трансформируется в стандартную. Существенно новыми свойствами обладают стандартные или рекурсивные схемы, если их расширить за счет добавления проверки равенства термез, что было сделано Чандрой н Манной [88, 90[.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
