Определение рекурсивной схемы

Рекурсивная схема (РС) так же, как СПП определяется в некотором базисе. Полный базис РС, как и базис ССП, включает четыре счетных множества символов: переменные, функциональные символы, предикатные символы, специальные символы.

Множества переменных и предикатных символов ничем не отличаются от ССП. Множество специальных символов - другое, а именно: {if, то, else,(,),,}. Отличие множества функциональных символов состоит в том, что оно разбито на два непересекающиеся подмножества: множество базовых функциональных символов и множество определяемых функциональных символов (обозначаются для отличия прописными буквами, например, F⁽¹⁾, G⁽²⁾, и т.д.).

В базисе РС нет множества операторов, вместо него – множество логических выражений и множество термов.

Простые термы определяются так же, как термы–выражения в СПП. Среди простых термов выделим базовые термы, которые не содержат определяемых функциональных символов, а также вызовы-термы вида F⁽ⁿ⁾(t₁,t₂,…t_n), где t₁,t₂,…t _n - простые термы, F⁽ⁿ⁾ - определяемый функциональный символ.

Логическое выражение- слово вида

p⁽ⁿ⁾(t₁,t₂,…t_n),

где p⁽ⁿ⁾ - предикатный символ, а t₁,t₂,…t_n - базовые термы.

Терм - это простой терм, или условный терм, т.е. слово вида

ifpthent₁elset₂,

где p - логическое выражение, t₁, t₂ - простые термы, называемые левой и соответственно правой альтернативой.

Примеры термов:

§f(x, g(x, y)); h(h(a)) - базовые термы;

§f(F(x), g(x, F(y))); H(H(a)) - простые термы;

§F(x); H(H(a)) - вызовы;

§ifp(x, y) then h(h(a))elseF(x) - условный терм.

Используется бесскобочная форма представления:

ifpxy thenhhaelseFx - условный терм.

Расширим в базисе В множество специальных символов символом "=".

Рекурсивным уравнением, или определением функции F назовем слово вида

F⁽ⁿ⁾(x₁,x₂,…x_n) = t(x₁,x₂,…x_n),

где t(x₁,x₂,…x_n) - терм, содержащий переменные, называемые формальными параметрами функции F.

Рекурсивной схемойназывается пара (t, М), где t - терм, называемый главным термом схемы (или ее входом). М - такое множество рекурсивных уравнений, что все определяемые функциональные символы в левых частях уравнений различны и всякий определяемый символ, встречающийся в правой части некоторого уравнения или в главном терме схемы, входит в левую часть некоторого уравнения. Другими словами, в РС имеется определение всякой вызываемой в ней функции, причем ровно одно.

Примеры РС:

R_S1: F(x); F(x) = ifp(x) thenaelseg(x, F(h(x))).

R_S2: A(b, c); A(x, y) = ifp(x) thenf(x)elseB(x, y);

B(x, y) = ifp(y) thenA(g(x), a) elseC(x, y);

C(x, y) = A(g(x), A(x, g(y))).

R_S3:F(x); F(x) = ifp(x) thenxelsef(F(g(x)), F(h(x))).

Пара (R_S, I), где R_S - PC в базисе В, а I - интерпретация этого базиса, называется рекурсивной программой. При этом заметим, что определяемые функциональные символы не интерпретируются.

Протоколы выполнения программы (R_S1, I₁) и (R_S1, I₂), где I₁ и I₂ - интерпретации из п. 1.2.3 (рисунок 1.3, б, в), выглядят следующим образом: