Пример: Глобальная сеть INTERNET
Я ищу:
На главную  |  Добавить в избранное  

Главная/

Программирование, базы данных. /

Рекурсивные схемы

←предыдущая следующая→
1 2 3 4 

множества символов: перемен-

ные, функциональные символы, предикатные символы., специаль-

ные символы.

Множества переменных и предикатных символов ничем не

отличаются от соответствующих множеств в базисе стандартных

схем. Множество специальных символов — другое, а именно:

{если, то, иначе, ( , ) ,  }. Что касается множества функциональ-

ных символов, то оно ииеет единственное, но существенное отли-

чие от множества функциональных символов базиса стандартных

схем. Отличие состоит в том, что это множество разбито на два

непересекающихся подмножества: множество базовых функцио-

нальных символов и множество определяемых функциональных

символов. Чтобы отличать их, будем определяемые функциональ-

иые символы обозначать прописными буквами, например, 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

После того как введено понятие выполнения рекурсивных

←предыдущая следующая→
1 2 3 4 


Copyright © 2005—2007 «RefStore.Ru»