ей символ b и n Унарні предикатних сімволів pa1, pa2., pan,
У класі інтерпретацій KI-2 схем Із KS-1 множини D всегда співпадає з множини E * всех слів в алфавіті E, а Кожне відображення I Із KI-2 задовільняє Наступний Вимоги:
1) I (b) = е;
2) I (fai (x)) = con (I (x), 'ai') = I (x) ai для всіх літер ai Із E;
3) I (g (x)) = del (I (x));
4) I (pai (x)) = hai (I (x)) для всіх літер ai Із E;
5) I (xi) є E * для всіх вхідніх змінніх СОА и СПА увазі (6), (7), і I (y) = e для всіх других змінніх Із пам'яті віщезгаданіх схем алгорітмів.
Замінівші у (5) сімволі fai, g, b и hai згідно з інтерпретацією I Із класу KI-2 мі отрімаємо програмноподібну структуру, рядки Якої будемо назіваті командами. Тому схеми алгорітмів (6) і (7) iз класу KS-2 далі інтерпретуються, як відповідні алгоритми (програми) iз класу прграм kП-2, Функціонування якіх подібно до Функціонування програм, что напісані на мовах програмування типом Паскаль, коли ці програми Працюють на даніх типом string. Ясно, что функціонуваня команд програм Із класу КП-2 аналгічно, з точністю до інтерпретації сімволів ее схеми, до функціонуваня команд програм Із класу КП-1, Яке Було описано Вище.
Зауважімо такоже, что по аналогії з N-БРМ Бn можна ввести E-БРМ бe, что реалізує програму Із КП-2, а такоже NE-БРМ БNE. БNE можна розглядаті як В«об'єднанняВ» програм Пn i ПE для Бn i бe в тому СЕНСІ, что множини регістрів Бn i бe НЕ перетінаються, альо смороду мают загальний блок управління (i Спільні Мітки), в якій поміщена Спільна програма ПNE, в якові входять ВСІ відряд, як Із Пn так и Із ПE.
Часткові або всюдіозначенні функцію g: E * вх -> E * вх, яка задана на множіні слів довільного алфавіту E, або предикат P: E * -> T, F, будемо назіваті E - рекурсивні функцією (предикатом), або RE-функцією (RE-предикатом), ЯКЩО існує программа Із класу КП-2 П1g, что обчіслює g (P).
Як відомо [1], [2], за допомгою кодуючої Функції доводитися, что, в ПЄВНЄВ СЕНСІ, клас R-функцій (R-предікатів) i кла RE-функцій (RE-предікатів) є еквівалентні. p> Приклади доведення по побудові RE-рекурсівності функцій и предікатьв наведені далі.
Побудуємо алгоритм, что обчіслює функцію
z: = f1 (x, y) = x + y.
x, y! z
q10
q11
q12
q13
q14
q15
q16
q17
q18
q19
x1 = x (q11, q11)
y1 = y (q12, q12)
z1 = 0 (q13, q13)
P0 (x1) (q16, q14)
z1 = z1 + 1 (q15, q15)
x1 = x1 - ^ 1 (q13, q13)
P0 (y1) (q19, q17)
z1 = z1 + 1 (q18, q18)
y1 = y1 - ^ 1 (q16, q16)
z = z1 (Я, Я)
Побудуємо алгоритм (не оптимальні), что заносити в z Значення Функції добутку xiy, тоб z: = f1 (x, y) = x * y.
x, y! Z
q20
q21
q22
q23
x2 = x (q21, q21)
y2 = y (q22, q22)
z2 = 0 (q23, q23)
P0 (y2) (q25, q10)
q10
q11
q12
q13
q14
q15
q16
q17
q18
q19
x1 = z2 (q11, q11)
y1 = x (q12, q12)
z1 = 0 (q13, q13)
P0 (x1) (q16, q14)
z1 = z1 + 1 (q15, q15)
x1 = x1 - ^ 1 (q13, q13)
P0 (y1) (q19, q17)
z1 = z1 + 1 (q18, q18)
y1 = y1 - ^ 1 (q16, q16)
z2 = z1 (q24, q24)
q24
q25
z2 = z1 (q23, q23)
z = z2 (Я, Я)
Нехай алфавіт Е = a, b. Побудуємо алгоритм, что обчіслює предикат Pe (w), де Pe (w) = T тоді и Тільки тоді, коли w є пусте слово Із E *, тоб w = e.
В
x! q [. t.], q [. f.]
q10 x1 = x (q11, q11)
q11 ha (x1) (q [. f.], q12)
q12 hb (x1) (q [. f.], q [. t.])
Побудуємо алгоритм (не оптимальні), что заносити в z Значення Функції con (x, y) = xy, тоб z: = g1 (x, y) = con (X, y) == xy для слів Із Е = a, b. br/>
x, y! Z
q20
q21
q22
x2 = x (q21, q21)
y2 = y (q22, q22)
z2 = e (q10, q10)
...
