множества символов: перемен-
ные, функциональные символы, предикатные символы., специаль-
ные символы.
Множества переменных и предикатных символов ничем не
отличаются от соответствующих множеств в базисе стандартных
схем. Множество специальных символов — другое, а именно:
{если, то, иначе, ( , ) , }. Что касается множества функциональ-
ных символов, то оно ииеет единственное, но существенное отли-
чие от множества функциональных символов базиса стандартных
схем. Отличие состоит в том, что это множество разбито на два
непересекающихся подмножества: множество базовых функцио-
нальных символов и множество определяемых функциональных
символов. Чтобы отличать их, будем определяемые функциональ-
иые символы обозначать прописными буквами, например, F(1),
G(2), Н(1), . . . (Такие буквы уже использовались для обозначения
функций. В рекурсивных схемах важно наглядно отделать базо-
вые и определяемые символы, поэтому мы пошли на двусмыслен-
ное использование прописных букв F, G, Н, . . ., надеясь, что
контекст поможет восстановить смысл обозначения.)
В базисе рекурсивных схем нет множества операторов, вместо
него — множество логических выражений и множество термов.
Простые термы определяются точно так же, как определялись
термы-выражения в стандартных схемах. Среди простых термов
выделим базовые термы, которые не содержат определяемых функ-
циональных символов, а также вызовы — термы вида F(n) (т1, . . .
. . ., тn) где т1 , . . . , тn — простые термы, а F(n) — определяемый
функциональный символ. Логическое выражение — слово вида
p(n) (т1, . . . ,тn), где p(n) — предикатный символ, т1, . . . ,тn —
базовые термы. Терм — это 1) простой терм, или 2) условный терм,
т. е. слово вида
если p то т1 иначе тn,
где p — логическое выражение, т1 , тn — простые термы, назы-
ваемые левой и соответственно правой альтернативой.
если р(х, у) то h (h (а)) uначе F (х) — условный терм.
Наряду с обычным представлением термов будем использо-
вать бесскобочную форму;
если рху то hha иначе Fx.
Пусть B — некоторый базис. Расширим множество специаль-
ных символов дополнительным символом = .
Рекурсивным уравнением, или определением функции F назо-
вем слово вида
F(n)(x1 ,. . ., xn) = т (x1 ,. . ., xn).
где F(n) — n-мeстный определяемый функциональный символ;
т (x1 ,. . ., xn) — терм, содержащий переменные из множества
переменных {x1 ,. . ., xn}, называемых формальными парамет-
рами (ФРП) функции F, и никаких других переменных.
Рекурсивной схемой называется пара (т, М), где т — терм,
называемый главным-термом схемы (или ее входом), а М — такое
множество рекурсивных уравиенвй, что все определяемые функ-
циональные символы в левых частях уравнений различны ц вся-
кий определяемый символ, встречающийся в правой части неко-
торого уравнения или в главном терме схемы, входит в левую
часть некоторого уравнения. Другими словами, в рекурсивной
схеме имеется определение всякой вызываемой в ней функции,
причем ровно одно.
1.3. Рекурсивная программа. Понятие интерпретации базиса, полностью переносится на базисы рекурсивных схем с одним лишь замечанием — определяемые функциональные символы не интерпретируются. Определение свободной интерпретации также остается в силе.
Пара (S, I), где S — рекурсивная схема в базисе В, а I —
интерпретация этого базиса, называется рекурсивной программой,
Понятие выполнения рекурсивной программы определим с по-
мощью протокола выполнения, который представляет собой ко-
нечную или бесконечную последовательность конфигураций. Кон-
фигурации определены с помощью понятия значения терма.
Так как мы сейчас рассматриваем термы, допускающие неинтер-
претируемые определяемые функциональные символы, необхо-
димо обобщить понятие значения (базового) терма.
Пусть т — терм, I — некоторая интерпретация, W — неко-
торое состояние памяти, т. е. совокупность значений всех пере-
менных, входящих а терм (или в схему, содержащую этот терм).
Значение тI (W) терма т при интерпретации I и состоянии памяти
W определяется следующим образом:
1) если т, — базовый терм, то тI (W) — значение этого терма,
определенное точно так, как это было сделано в п. 2.4;
2) если т — терм вида F(n)(т1,. . ., тn), то т1 (W) = F(n)(т1I(W),. . ., тnI(W));
3) если т — терм вида f(n) (т1,. . ., тn) и хотя бы один из тер-
мов т1,. . ., тn содержит определяемый функциональный символ, то
тI(W) = Ф(n)(т1I(W),. . ., тnI(W))
где Ф(n) — символ функции I(f(n)), за которым в скобках сле-
дует список значений термов т1I(W),. . ., тnI(W);
4) если т — условный терм вида
если p(n)(т1,. . ., тn) то тl иначе тr, то
Таким образом, в общем случае значения термов — это выра-
жения, содержащие элементы из области интерпретации, опре-
деляемые функциональные символы и символы конкретных функ-
ций.
Если протокол конечен, то программа (S, I) останавливается
и последняя конфигурация в протоколе считается результатом
программы, если она представляет собой элемент из области ин-
терпретации. Если же последняя конфигурация — выражение,
составленное из символов функций и значений переменных, то
осуществляется вычисление этого выражения, в результат вы-
числения (элемент из области интерпретации) объявляется резуль-
татом программы. Программа (S, I) зацикливается, если протокол
бесконечен.
П р и м е р. Протокол выполнения программы (S,I), где
I — интерпретация, выглядит следующим образом:
Порядковый Значение терма
номер
1 F(4)
2 4 x F (3)
3 4 x (3 x (F (2)))
4 4 х (3 х (2 x F (1)))
5 4 x (3 x (2 x (1 x F (0))))
6 4 x (3 x (2 x (1 x 1))) = 24
Протокол выполнения программы (S,Ih), где Ih — свободная
интерпретация из п. 3.2:
Порядковый Значение терма
номер
1 Fx
2 gxFhx
3 gxghxFhhx
4 gxghxghhxFhhhx
5 gxghxghhxa
После того как введено понятие выполнения рекурсивных
|
|