1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 38
Текст из файла (страница 38)
Множество специальных символов — другое, а нмеинеч (если> то, вначе, (, ),, ). Что касается множества функциональ- 173 ных симзолов, то оно имеет единственное, но сущестзенное отличие от множества функциональных снмзолоз базиса стандартных схем. Отличие состоит в том, что зто множество разбито на даа непересекающихся подмножества: множество багоеых ~дуняциональных симеолое и множество определяемых б)ующиональных еимеолое.
Чтобы отличать их, будем определяемые функциональные символы обозначать прописными буквами, например, ГП>, б~з>, Н<Н,... (Такие буквы уже нспользозались для обозначения функций. В рекурсивных схемах важно наглядно отделить базовые и определяемые символы, поэтому мы пошли на двусмысленное использование прописных букв Г, 6, Н, ..., надеясь, что контекст поможет восстановить смысл обозначения.) В базисе рекурсивных схем нет множества операторов, вместо пего — множество логических зыраженвй и множестзо термоа.
Ирастые термы определяются точно так же, как определялись термы-зыражения в стандартных схемах. Среди простых термов выделим багоеые термы, которые не содержат определяемых функциональных сямзолоз, а также еыгоеы — термы вида Г<") (т„... ..., т„), где т,..., т„— простые термы, а ГЧ"> — определяемый функционалъный символ. Логическое еыругкение — слово вида р~"> (т, т,..., т„), где р~"> — предикатвый свмзол, т, т,..., т„— базоаые термы. Терм — зто 1) яростей терм, вли 2) услоеный терм, т. е. слово вида еелв я то тг яваче т, где я — логическое выражение, т, и тг — простые термы, называемые лесей н соотзетстзенно красой а.ььтернатиеой.
Примеры термез: ((х, у(х, у)) ( й(й (а)) / ((Р(х),у(х,Р(у))) ~ Н (Н(а)) Р(х) Н(Н(а)) еслн р(х, у) то Й(Ь(а)) иначе Р(х) — условный терм. Наряду с обычвмм представлением тернов будем использовать бесскобочную форму: сели рху то Ьла иначе Рх. Пусть Ф вЂ” некоторый базкс. Расширим множество спецвальных символов дополнительным символом =. Реяурсиеным ураенением, или определением ~уикли Р нааоаем слово вида Гт"> (хп..., х„) = т (хп..., х„), где Рос — и-местный определяемый функциональный символ; ч(хь,..., х„) — терм, содержащий переменные нз множества 1Н переменных (х„..., х„», нааываемнх Формалъкыми парамет- раки (ФРП) функции Г, и никаких других переменных.
Рекурспвной схемой называется пара (т, М), где т — терм, нааывавмый елаекмм термом схемы (нли ее входом), а М вЂ” такое множество рекурсивных уравнений, что все определяемые функ- ционалъные символы в левых частях уравнений различны и вся- кий определяемый символ, встречающийся в правой части ыеко- торого уравнения или в главном терме схемы, входит в левую часть некоторого уравнения. Другими словами, в рекурсивной схеме имеется определение всякой еыаъшаемой в ней функции, причем ровно одно.
Примеры рекурсивных схем: $) Яе;. Р(х), Р (х) = волн р (х) то а ниачв у (х, Г (а (х))); 2) Юе.т: А (Ь, е), А (х, у) = если Р (х) то 1 (у) иначе В (х, у), В (х, у) = волк р (у) то А (у (х), а) иначе С (х, у), С(х, у) = А (у(х), А (х, у(у))); 3) 8в.е Р (х), г''(х) = если р (х) то х иначе ) (Р(у(х)), Г(я(х))) 1.3.
Рекурсивная программа. Понятие иытерпретации базиса, введенное в гл. 4, полностью переносится на бааксы рекурсивных схем с одним лишь замечанием — определяемые функцноналъные символы не интерпретируются. Определение свободной интерпре- тации также остается в сыле. Пара (Ю, 1), где 8 — рекурсивная схема в базисе бе, а 1— интерпретация этого базиса, взвивается рекурсивной Поераммой. Понятие въшолывння рекурсивной программы определим с по-- мощью протокола выполнения, который представляет собой ко- нечную илн бесконечную последовательность коифиеураиий.
Кон- фигурации определены с помощью понятия значения терма. Так каы мы сейчас рассматриваем термы, допускающие неинтвр- претнруемыв определяемые функциоыалъннв символы, необхо- димо обобщить понятие значения (базового) герма, введенное в п. 2.4 гл. 4. Пусть и — терм, 1 — некоторая интерпретация, ер — неко- торое состояние памяти, т. в.
совокупность значений всех пере- менных, входящих в терм (или в схему, содержащую этот терм). Значение тт (И') тврма т прн иытерпретацин Х и состоянии памяти еУ определяется следующим образом: $] если т — базовый терм, то тт (٠— значение этого герма, определенное точно так, как это было сделано в п. 2.4 гл.
4; 2) если т — терм вида г"<"> (т„..., т„), то тт ()Ф') = = рт"> (ты (еу),..., т„т (щ); 3) если т — терм вида 1<"> (тп..., т„) и хотя бн одни из тер- зщв тп..., т„содерншт определяемый функциональный символ, то те (Й') = Ф<ю (ты (щ,..., т„т (И')), где Ф~"> — символ функции 1 Ц~">), за которым в скобках следует список значений термов тгг(Щ, ..., т„г (1Р); 4) если т — условный терм вида если р("> (т1,..., т„) то тг иначе туф то т я (Уг), если 1(р<">) (ти (ТФ),..., т,ц (гр)) = 1, ты(гг') в противном случае. Значение гнерма Порлдноеий неяср 1 2 3 4 5 6 Г (4) 4 х Р (3) 4 Х (3 Х (Р (2))) 4 Х (3 Х (2 Х Г (1))) 4 Х (3 Х (2 Х (1 Х Г (0)))) 4Х(ЗХ(2Х(1 Х1)))=24 Протокол выполнения программы (Яьм 1 ), где 1э — интерпретация из п. 2.5 гл.
4: 1тб Таким образом, в общем случае аначения термов — это выражения, содержащие элементы из области интерпретации, определяемые функциональные символы и символы конкретных функций. Протокол емнслнения рсяурсианой яразраммм (8, 1) — это последовательность конфигураций Фп $м $м... такая, что: 1) 8, = т,г (И*с), где тг — главный терм схемы Я, начальное значеняе памяти, т. е.
всех переменных схемы Ю; 2) Ф;+ получается из 8; заменой в Ф~ самого левого, самого внутренйего вхождения вызова Ров (д„д,..., д„) (где Г~"1— кекоторын определяемыи символ, сЦ, сЦ, ..., И„Е= Вг) на значение терна в правой части уравнения Р~"> (я„..., х„) = = т(х„..., я„) при интерпретации 1 и значениях переменных: И~(лг) = д„й~(хэ) = Из,..., И'(х„) = Н„; 3) если 8» не содержит определяемых функциональных символов, то Ф~ — последняя конфигурация протокола. Если протокол конечен, то программа ф, 1) астанаэлиеосжсн я последняя конфигурация в протоколе считается рсеульлнвне.» программы, если она представляет собой элемент из области интерпретации.
Если же последняя конфигурация — выражение, составленное из символов функций и значений переменных, то осуществляется вычисленяе этого выражения, я результат вычисления (элемент из области интерпретации) объявляется результатом программы. Программа (Я, 1) заниялиеасгнсл, если протокол бесконечен. П р и м е р. Протокол выполнения программы (Ю „1,), где 1 — интерпретация из п.
2.5 гл. 4, выглядит следующим образом: Порлдвоеый колер $ 2 3 4 Значение терл«а Р (аЬс) СОКЯСАВ (аЬс, Р (Ьс)) СОМБСАВ (аЬс, СО1т'ЗСАВ (Ьс, Р (с))) СО(УЗСА В (аЬс, СО(УПСА В (Ьс, СО)т'ЮСАВ (с, Р (е)))) СОКЯСАВ (аЬс, СОКЮСАВ (Ьс, СО)«ИСАВ (с, е))) = аЬс. Протокол выполнения программы (Юе.ы 1ъ), где 1„— свободная интерпретация на п.
3.2 гл. 4. Порлдлоеый Значение терла нол«ер ( 2 3 4 5 Рх лхрйх пхпйхЛйх лхбйхфйхЛййх лхяйхяlйха Отметим, что та( (Зе.ы 1«) = та) (Я«.е, 1,), та) (Ю«.ы 1«) чь чь та((З«.«,1«) н таЦ8«.с 1ъ) чы"а) (З«.т, 1а), где 8«.е — стан- дартная схема на гл. 4. После того как введено понятие выполнения рекурсивных программ, можно дать определения пустоты, тотальности н функ- циональной эквивалентности рекурсивных схем. Этн определе- ния ничем не отличаются от соответствутоп(нх определений в п. ЗА гл.
4, если в ннх ааменвть слово «стандартная схема» на «рекур- сивная схемаа. ЗадавиеОА. А. Постройте протокол выполнения репурсиеиой схемы Яа.а К (о), Р (л) = сели р (л) то 1 (л) вваче е" (Р (е (л))) при интерпретации 1: 1 (а) = 7, (т, если И>(0, 1()) (8) = о — $; (О, если И((0, 1 (Е) (о) = о + 2. Б. Постройте протокол выполнении рекурсивной схемы лаа: е (а), )с (л) = ееаи р (л) те л вваче 6 (л), ы (л) = если д (л) те 1(Р (7(л))) вваче е (Г (е (л)) ) при свободной интерпретации 1 такой, что 1, если числе символов в бесспобочвом терм«-евачевии а 7(Р) (л) = ве болею« б, О а претиввом случае; $, если число бааовых фуввциоиалъвых символов в а /(т)(о) = ие болыае т, 0 в противном случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
