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

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

(Рекурсивні функції на області натуральних чисел N)

Розглянемо математичне визначення [1,2] класів функцій та предикатів, що вважаються точним аналогом інтуїтивного поняття алгоритму (взагалі кажучи, часткового).

1. Введемо зчисленні множини символів або послідовностей символів (слів, ідентифікаторів і т. п.) із довільної конструктивної множини:

а) індивідні: x, y, z, x0, y0, z0, x1, y1, z1,… xj, yj, zj,…;

б) функціональні: f, g, h, f0, g0, h0, f1, g1, h1,… fj, gj, hj,…;

в) предикатні: P, Q, R, P0, Q0, R0, P1, Q1, R1,… Pj, Qj, Rj,…;

г) константи: a, b, c, a0, b0, c0, a1, b1, c1,… aj, bj, cj,…;

д) мітки: q, i, j, q0, i0, j0, q1, i1, j1,… qk, ik, jk,…

Кожній функціональному та предикатному символу U однозначно ставиться у відповідність натуральне число n, яке називається арністю даного символа. Цей символ позначається через U(n), або U (x1, x2., xn) та т. п., і називається n-арним символом. Вважається, що ідеалізований об'єкт – 0-арний функціональний символ U(0) співпадає з символом константи.

Схемою оператора пр исвоювання називається вираз виду:

z(i) = f(m) (x(1)., x(m)). (1)

Схемою оператора пересилки називається вираз виду:

z(k) = y(j) (2)

Схемою прісвоювання константи називається вираз виду:

z(k) = a, або z(k) = fj(0) (3)

Схемою умови називається вираз виду:

P(s) (x(1)..x(s)) (4)

Схемою програми (СП)S називатимемо об'єкт виду

q0 Ф[0] (i0, j0)

q1 Ф[1] (i1, j1)

……………. (5)

qs Ф[s] (is, js)

В (1) Qs = Qs1 u Qs2, де Qs1 = q0, q1..qs, і

Qs2= i0, j0., is, js – підмножини множин міток. Як правило, якщо не вказане уточнення, будемо вважати, що qi – qj, якщо i – j, (qi, qj належать Q1). Мітки із Q1 називаються мітками передачі управління, а мітки із (Qs – Qs1) – кінцевими мітками.

Для всіх k є [0_s], Ф[k] – це одна із схем (1) – (4).

Сукупність всіх індивідних змінних СП (5) називається пам "яттю схеми S. Сукупність константанктних, функціональних, предикатних символів і пам" яті S називається сигнатурою, або базисом, схеми S .

Конструкція вигляду

qr Ф[r] (ir, jr)