justify">. кожної логічної константі р (0) - один символ безлічі { 0,1 } ;
. кожному предикатні символу р (n) - усюди певний предикат P (n) = I (p (n)).
Пара (S, I) називається інтерпретованої стандартною схемою (ІСС), або стандартною програмою (СП).
Визначимо поняття виконання програми
Станом пам'яті програми (S, I) називають функцію W: XS В® D, яка кожної змінної x з пам'яті схеми S зіставляє елемент W (x) з області інтерпретації D.
Значення терма ? при інтерпретації I і стан пам'яті W (позначимо ? I (W)) визначається наступним чином:
) якщо ? = х, x - змінна, то ? I (W) = W (x);
2) якщо ? = a, a - константа, то ? I (W) = I (a);
3) якщо ? = f (n) (? 1,? 2 ...,? n), то ? I (W) = I (f (n)) (? 1I (W),? 2I (W), ...,? nI (W)) .
Аналогічно визначається значення тесту p при інтерпретації I і стан пам'яті W або p I (W):
якщо p = р (n) ( ? 1, ? 2 ..., ? n), то p I (W ) = I (p (n)) ( ? 1I (W), ? 2I (W), ... ? nI ( W)), n? 0.
Конфігурацією програми називають пару U = (L, W), де L - мітка вершини схеми S, а W - стан її пам'яті. Виконання програми описується кінцевої або нескінченної послідовностей конфігурацій, яку називають протоколом виконання програми (ПВП). p align="justify"> Протокол (U0, U1, ..., Ui, Ui +1, ...) виконання програми (S, I) визначаємо наступним чином (нижче ki означає мітку вершини, а Wi - стан пам'яті в i-й конфігурації протоколу, Ui = (ki, Wi)): = (0, W0), W0 - початковий стан пам...
