Главные свойства стандартных схем Тотальная схема; Пустая схема; Функционально- эквивалентные схемы (S 1 ~S 2 ) Цепочка стандартной схемы (ЦСС) (0, 1, 2 1, 5), (0, 1, 2 0, 3, 4, 2 0, 3, 4, 2 1, 5) Цепочка операторов (ЦО) (старт(х), y:=5, p 1 (x), стоп(y)) Допустимая ЦСС; Свободная ССП.

Свободные интерпретации СИ переменным и функциональным символам сопоставляют: 1) х, I h => I h (x)=x; 2) а => I h (а)=a; 3) f (n) (n>=1) => I h (f (n) )=F (n), F (n) (t 1, t 2, …,t n )=f (n) (t 1, t 2, …, t n ). Пример: I h – СИ,

Протокол выполнения программы: XY U0U0 0xy U1U1 1xa U2U2 2xa U3U3 3xg(x, a) U4U4 4h(x)g(x, a) U5U5 2h(x)g(x,a) U6U6 3h(x)g(h(x),g(x,a)) U7U7 4h(h(x))g(h(x),g(x,a)) U8U8 2h(h(x))g(h(x),g(x,a)) U9U9 3h(h(x))g(h(h(x)),g(h(x),g(x,a))) U 10 4h(h(h(x)))g(h(h(x)),g(h(x),g(x,a))) U 11 2h(h(h(x)))g(h(h(x)),g(h(x),g(x,a))) U 12 5h(h(h(x)))g(h(h(x)),g(h(x),g(x,a)))

Согласованные свободные интерпретации Iи I h – согласованы, если для π I h (π)=I(π) Пример: t=g(h(h(x)),g(h(x),g(x,a))) I 1 (x)=3, I 1 (a)=1, I 1 (g)=G, где G(d1,d2)= d1*d2; I 1 (h)=H, где H(d)= d-1; I 1 (p)=P, где P (d)=1, если d=0, иначе P (d)=0. I 1 (t)=((3-1)-1)*((3-1)*(3*1))=6

Рекурсивные схемы FACT(x), FACT(x)=если х=0 то 1 иначе x*FACT(x-1). FACT(4)=если 4=0 то 1 иначе 4*FACT(4-1)= =4*FACT(3)=4*(если 3=0 то 1 иначе 3*FACT(3-1))= =4*3*FACT(2)=12*(если 2=0 то 1 иначе 2*FACT(2-1))= =12*2*FACT(1)=24*(если 1=0 то 1 иначе 1*FACT(1-1))= =24*1*FACT(0)=24*(если 0=0 то 1 иначе 0*FACT(0-1))=24

Базис РС включает: -4 счетных множества символов: -Переменные; -Функциональные символы; -Предикатные символы; -Специальные символы. -Множество логических выражений. -Множество термов. Множество функциональных символов: 1.Множество базовых функциональных символов (f (1), g (2) ); 2.Множество определяемых функциональных символов (F (1), G (2) ).

Термы: 1. Простые термы Базовые термы; Вызовы (F (n) (t 1, t 2, …, t n )). 2. Условные термы: если π то t 1 иначе t 2. Пример: базовые термы - f(x, g(x, y)); h(h(a)); вызовы - F(x); H(H(a)); F(H(x), f(x,y)); условный терм если p(x, y) то h(h(a)) иначе F(x).

Рекурсивное уравнение: F (n) (x 1, x 2, …, x n )=t(x 1, x 2, …, x n ) Рекурсивная схема:(t, M) Рекурсивная программа:(R S, I ) Примеры РС: 1) R S1 : F(x), F(x)=если p(x) то a иначе g(x, F(h(x))). 2) R S2 : A(x, y), A(x, y)=если p(x) то f(x) иначе B(x, y), B(x, y)=если p(y) то A(g(x), a) иначе C(x, y); C(x, y)=A(g(x), A(x, g(y))). 3) R S3 : F(x), F(x)=если p(x) то x иначе f(F(g(x)), F(h(x))).

Протокол выполнения рекурсивной программы R S1 : F(x), F(x)=если p(x) то a иначе g(x, F(h(x))). I(x)=4; I(a)=1; I(g)=G, где G(d1,d2)= d1*d2; I(h)=H, где H(d)= d-1; I(p)=P, где P (d)=1, если d=0, иначе P (d)=0. п/пЗначение терма для (R S, I ) F(4) 4*F(3) 4*(3*F(2)) 4*(3*(2*F(1))) 4*(3*(2*(1*F(0)))) 4*(3*(2*(1*1)))=24

Трансляция схем программ Теорема Маккарти: Класс стандартных схем транслируем в класс рекурсивных схем. Алгоритм трансляции: 1.Точки сечения i F i (x, y, …, z); старт F 1 (x, y, …, z); стоп(х) x; 2.Граф рассекается по точкам сечения; 3.Для каждого фрагмента строится рекурсивное уравнение: F i (x, y, …, z)=…

F i (x, y, …, z) = t(x, y, …, z);

Пример 1: F 1 (x, y) F 2 (x, y) y

F 2 (x, a) =F 2 (x, a) y F 2 (h(x), y) F 2 (h(x), g(x, y)) F 1 (x, y) = F 2 (x, a), F 2 (x, y) = если P(x) то y иначе F 2 (h(x), g(x,y))

Пример 2: F 1 (x, y) F 2 (x, y) F 3 (x, y) y F 2 (x, f(x)) F 1 (x, y) = F 2 (x, f(x)), y h(x) h(f(y)) F 3 (f(x), y) F 2 (x, y) = если p(y) то h(f(y)) иначе F 3 (f(x), y), h(x) F 2 (x, f(x)) F 3 (x, y) = если p(x) то h(x) иначе F 2 (x, f(x)).

Линейные унарные рекурсивные схемы F(x), F(x) = если p(x) то f(x) иначе F(F(g(x))). F(a), F(x) = если p(x) то x иначе G(x), G(x) = если q(x) то f(F(f(x))) иначе g(F(g(x))). Теорема (Патерсон-Хьюит). Класс линейных унарных рекурсивных схем транслируем в класс стандартных схем.