Учебное пособие: Алгоритмічні проблеми

q21

q22

x2 = x (q21, q21)

y2 = y (q22, q22)

z2 = e (q10, q10)

q10

q11

q12

x1 = y2 (q11, q11)

ha(x1) (q22, q12)

hb(x1) (q22, q28)

q22

q23

q24

ha(y2) (q23, q25)

x2 = con (x2, a) (q24, q24)

y2 = del(y2) (q22, q22)

q25

q26

q27

q28

hb(y2) (q26, q10)

x2 = con (x2, b) (q27, q27)

y2 = del(y2) (q25, q25)

z = x2 (Я, Я)

4. Операторні та предикатні алгоритми -ІІ

(Рекурсивні функції на областях, що відмінні від N)

Оскільки БРМ працює тільки з натуральними числами, наше визначення обчислюваності і можливості розв'язання застосовано тільки до функцій і предикатів від натуральних чисел. Ці поняття легко поширюються на інші види об'єктів (тобто цілі числа, поліноми, матриці і т.д.) за допомогою кодування.

Кодуванням області D об'єктів називається явне й ефективне відображення α: D →N. Ми будемо говорити, що об'єкт α € D кодується натуральним числом α (d). Припустимо, що f є функцією з D в D; тоді f природно кодується функцією f* з N в N, що відображає код кожного об'єкта d € Dom(f) у код об'єкта f (d). У явному виді це можна записати як