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

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

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

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

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

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

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

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

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

if p then t₁ else t₂,

где 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)) - вызовы;

§ if p (x, y) then h (h (a)) else F (x) - условный терм.

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

if pxy then hha else Fx - условный терм.

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

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

F ^{( n )}(x₁,x₂,…x_n) = t(x₁,x₂,…x_n),

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

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

Примеры РС:

R_S1: F (x); F (x) = if p (x) then a else g (x, F (h (x))).

R_S2: A (b, c); A (x, y) = if p (x) then f (x) else B (x, y);

B (x, y) = if p (y) then A (g (x), a) else C (x, y);

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

R_S3:F (x); F (x) = if p (x) then x else f (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, б, в), выглядят следующим образом:

№п/п	Значение терма для (RS1, I1)	Значение терма для (RS1, I2)
	F (4)	F (a,b,c)
	4* F (3)	CONSCAR (abc, F (b,c))
	4*(3* F (2))	CONSCAR (abc, CONSCAR (bc, F (c)))
	4*(3*(2* F (1)))	CONSCAR (abc, CONSCAR (bc, CONSCAR (c, F (е))))
	4*(3*(2*(1* F (0))))	CONSCAR (abc,CONSCAR (bc,CONSCAR (c, е))) = abc
	4*(3*(2*(1*1)))=24

 

 

---

Дата добавления: 2015-12-20; просмотров: 22; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!