ні,
S - СП вигляд (5), а q [. T.], Q [. F.]) - Кінцеві Мітки СП
S . p> Зауважімо, что пам "яттю алгорітмів (6), (7) назівається об "єднання пам" ятті
S и змінніх x1., xn, y, и x1., xn назіваються вхіднімі зміннімі, а y - віхідною змінною.
Мі визначили СП, СОА и СОП як деякі формальні, синтаксичні конструкції. Яка ж семантика (Сенс) ціх конструкцій? Як Із них отріматі справжні алгоритми (програми)?
Семантика схем задається за помощью інтерпретацій. Інтерпретація схема алгоритму W задається парою (D, I), де D - множини довільної природи, а I - це певне на відображення, Яку: а) шкірному символу змінної z Із пам "яті W ставити у відповідність елемент I (z) Із множини D, б) шкірному символу Константі b Із сигнатури W ставити у відповідність елемент I (b) Із D; в) шкірному m-арному функціональному f (m) (предикатні P (m)) символу співставляє, відповідно, всюдіозначені функцію I (f (m)): Dm -> D, або предикат I (P (m)) ->. t .. f.
2. Нижчих в даному розділі будемо розглядаті тількі підклас схем алгорітмів KS - 1 , Які містять Тільки два функціональні унарні символи f, g, одна константностей символ b и один Унарні предикатний символ p. Такоже обмежімо клас інтерпретацій, поклал, что в цьом класі KI-1 D всегда співпадає з множини натуральних чисел N (D = N), а відображення I задовольняє Наступний Вимоги:
1) I (b) = 0,
2) I (f (x)) = I (x) + 1;
I (x) - 1, колі x> 0
3) I (g (x)) = I (x) - ^ 1 = 0, коли x = 0 (8 )
t., колі I (x) = 0;
4) I (p (x)) = P0 (x)) = *
f., колі I (x)> 0.
5) I (xi) є N для всіх вхідніх змінніх СОА и СПА виду (6), (7), і I (y) = 0 для всіх других змінніх Із пам'яті віщезгаданіх схем алгорітмів.
Опішемо формально Функціонування алгоритмом A увазі (6).
Нехай M (A) = z1, z2 .. zn .. zm - пам'ять алгоріму A, де zi = xi при 1 < = i < = n, и zm = y. Через Q (A) позначімо ВСІ Мітки A. Станом пам'яті A будемо назіваті послідовність (a1.. Am) натуральних чисел, тоб елемент Nm. Станом (конфігурацією) алгоритму A будемо назіваті елемент Із D (A) = Q & Nm.
Стан назівається: а) проміжковім, ЯКЩО q - мітка передачі управління, б) кінцевім (заключний), ЯКЩО q - кінцева мітка алгоритму A.
Візначемо функцію переходів F: D (A) -> D (A) алгоритмом A.
1. Колі - кінцевій стан, то
F () = .
2. Колі - проміжковій стан, то Значення F поклади від вигляду команди qk Ф [k] (ik, jk) в (5).
Если Ф [k] має вигляд:
a) zr = zt + 1, то F () = , де q * = ik, br = at + 1, а bu = au для всіх таких u, что u НЕ рівне r;
b) zr = zt - ^ 1, то F () = , де q * = ik, br = at - ^ 1, а bu = au для всіх таких u, что u НЕ рівне r;
c) zr = 0, то F () = , де q * = ik, br = 0, а bu = au для всіх таких u, что u НЕ рівне r;
d) zr = zt, то F () = , де q * = ik, br = at, а bu = au для всіх таких u, что u НЕ рівне r;
e) P0 (zr), то F () = , де bu = au для всіх u (1 < = u < = m), а q * = ir, ЯКЩО ar = 0, и q * = jr, ЯКЩО ar> 0.
Перейдемо до визначення Функції f [A]: Nn -> N, якові
обчіслює алгоритм A при інтерпретації I.
по означених інтерпретації маємо, что початковий стан пам'яті є I (M (A)) = . Стан c [0] = назівається початкова таборували алгоритмом A при інтерпретації I. Скінченна або Нескінченна послідовність
T (A) = c [0], c [1]., c [k], c [k +1], ... (9)
назівається траєкторією (Шляхом) алгоритмом A при інтерпретації I (на вході ), ЯКЩО
F (c [k]) = c [k +1] для всіх k Із N.
Зрозуміло, что Траєкторія (9) для A будується конструктивно по Програмі цього алгоритму и початкових значень вхідніх змінніх, что задає Інтерпретація I.
При послідовному обчісленні станів c [k] помощью Функції переходів F Можливі два випадка:
1) у Траєкторії (9) знайдеться стан з [t] = такий, что c [t] - кінцевій стан, а c [0], c [1]., c [t-1] - проміжкові стани;
2) у Траєкторії (9) ВСІ стани проміжкові, тоб Траєкторія T (A) є нескінченною послідовністю станів A.
У первом випадка будемо вважаті, что A...
