Алгоритмічні проблеми (стр. 3 из 7)

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)

із (5) називається схемою команди.

Схемою операторного алгоритму (СОА), або схемою операторної процедури, називається об"єкт виду:

SA= (x1, x2., xn; S; y), (6)

де x1., xn, y – змінні, S – СП вигляду (5).

Схемою предикатногоо алгоритму (СПА), або схемою предикатної процедури, називається об"єкт виду:

SP= (x1, x2., xn; S; q [.t.], q [.f.]), (7)

де x1., xn, – змінні, S – СП вигляду (5), а q [.t.], q [.f.]) – кінцеві мітки СП S.

Зауважимо, що пам "яттю алгоритмів (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 будемо називати елемент <q; a1., am> із D(A) = Q & Nm.

Стан <q; a1., am> називається: а) проміжковим, якщо q – мітка передачи управління; б) кінцевим (заключним), якщо q – кінцева мітка алгоритму A.

Визначемо функцію переходів F: D(A) –> D(A) алгоритму A.

1. Коли <q; a1., am> – кінцевий стан, то

F (<q; a1., am>) = <q; a1., am>.

2. Коли <q; a1., am> – проміжковий стан, то значення F залежить від виду команди qk Ф[k] (ik, jk) в (5).

Якщо Ф[k] має вигляд:

a) zr = zt + 1, то F (<q; a1., am>) = <q*; b1., bm>, де q* = ik, br = at + 1, а bu = au для всіх таких u, що u не рівне r;

b) zr = zt -^ 1, то F (<q; a1., am>) = <q*; b1., bm>, де q* = ik, br = at -^ 1, а bu = au для всіх таких u, що u не рівне r;

c) zr = 0, то F (<q; a1., am>) = <q*; b1., bm>, де q* = ik, br = 0, а bu = au для всіх таких u, що u не рівне r;

d) zr = zt, то F (<q; a1., am>) = <q*; b1., bm>, де q* = ik, br = at, а bu = au для всіх таких u, що u не рівне r;

e) P0 (zr), то F (<q; a1., am>) = <q*; b1., bm>, де bu = au для всіх u (1<= u <= m), а q* = ir, якщо ar = 0, і q* = jr, якщо ar > 0.

Перейдемо до визначення функції f[A]: Nn –> N, яку

обчислює алгоритм A при інтерпретації I.

По означенню інтерпретації маємо, що початковий стан пам'яті є I (M(A)) = <a1., an, 0., 0>. Стан c[0] =<q0; a1., an, 0., 0> називається початковим станом алгоритму A при інтерпретації I. Скінченна або нескінченна послідовність

T(A) = c[0], c[1]., c[k], c [k+1],… (9)

називається траєкторією (шляхом) алгоритму A при інтерпретації I (на вході <a1., an>), якщо

F (c[k]) = c [k+1] для всіх k із N.

Зрозуміло, що траєкторія (9) для A будується конструктивно по програмі цього алгоритму і початковому значенню вхідних змінних, що задає інтерпретація I.

При послідовному обчисленні станів c[k] за допомогою функції переходів F можливі два випадки:

1) в траєкторії (9) знайдеться стан с[t] = <q*; b1., bm> такий, що c[t] – кінцевий стан, а c[0], c[1]., c [t-1] – проміжкові стани;

2) в траєкторії (9) всі стани проміжкові, тобто траєкторія T(A) є нескінченною послідовністю станів A.

У першому випадку будемо вважати, що A обчислює значення f[A] (<a1., an> функції f[A] в точці <a1., an>, i f[A] (<a1., an>) = bm. Нагадаємо, що bm природнім чином можна інтерпретувати як число, що знаходиться в вихідній змінній y в стані c[t] алгоритму A, так як, по припущенню, zm = y.

Якщо в траєкторії (9) всі стани проміжкові, тобто траєкторія T(A) є нескінченною послідовністю станів A, будемо вважати, що A циклює в точці <a1., an>, тому значення f[A] (<a1., an> функції f[A] в точці <a1., an> не визначено, тобто f[A] (<a1., an>) = @. Іншими словами,

bm, коли T(A) – скінченна f[A] (<a1., an>) = *

@, коли T(A) – нескінченна (8)

Аналогічно визначається траєкторія і функція переходів для предикатного алгорітму Aq, і вважається що Aq реалізує предикат;

і q* = q [.t.]; .t., коли T(A) – скінченна,

P[Aq] (<a1., an>) = * .f., коли T(A) – скінченна, i

і q* = q [.f.];

@, коли T(A) – нескінченна.

Замінивши у (5) сімволи f, g, b, і p згідно з інтерпретацією I ми отримаємо програмноподібну структуру, рядки якої будемо називаті командами. Тому схеми алгоритмів (6) і (7) iз класу KS-1 далі інтерпретуються, як відповідні алгоритми (програми) iз класу прграм KП-1, функціонування яких подібно до функціонування програм, що написані на мовах програмування типу Паскаль, Бейсік і т. п.

А саме:

1) символ «=» у схемах (1) – (3) інтерпретується як оператор присвоєння;

2) елементи із Qs інтерпретуються аналогічно міткам в мовах програмування;

3) виконання команди qr x = y + 1 (ir, jr) інтерпретується як послідовність команд qr: x = y+1; go to ir;

4) виконання команди qr x = y -^1 (ir, jr) інтерпретується як послідовність команд qr: x = y-^1; go to ir;

5) виконання команди qr x = y (ir, jr) інтерпретується як послідовність команд qr: x = y; go to ir;

6) виконання команди qr x = 0 (ir, jr) інтерпретується як послідовність команд qr: x = 0; go to ir;

7) виконання команди qr P0 (x) (ir, jr) інтерпретується як умова qr: IF P0 (x) THEN go to ir ELSE go to jr.

Як і у більшості мов програмування, оператор «go to ir» при функціонуванні програми передає управління на команду з міткою ir, а оператор «IF P0 (x) THEN go to ir ELSE go to jr» передає управлыння

на команду з міткою ir, якщо предикат P0 (x) =.t. (x = 0), і передає управління на команду з міткою jr, якщо предикат P0 (x) =.f. (x > 0).

В теорії алгоритмів вважається, що операторні SA та предикатні SP алгоритми із KS-1 виконуються на вхідних даних із N абстрактними автоматамиом – багаторегістровими обчислювальними машинами (N-БРМ). Для кожного алгоритму А ця машіна Ба складається з блоку управління і m регістрів, де кожний регістр (комірка) Rk може зберігати довілне натуральне число. Блок управління містить програму Па і забезпечує її виконання по вищенаведеній схемі. Система команд N-БРМ складається з множини 0, x+1, x-^1, P0 (0), які можуть виконуватися над вмістом кожного Rk, а також команд присвоювання, безумовного і умовного переходу, пересилки і запису в регістр.

Часткові або всюдиозначенні k-арні функцію g: Nk –> N, яка задана на натуральних числах, або предикат P: E* –> T, F, будемо називати рекурсивною функцією (предикатом), або R-функцією (R-предикатом), якщо існує програма із класу КП-1 П1g, що обчислює g (P).

Приклади доведення по побудові рекурсивності функцій наведені у розділі VI данної інструкції.

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

3. Аналгічно до класів KS-1 схем алгоритміві ¶нтерпретацій KI-1 введемо, відпвидно, класи KS-2 і KI-2.

Нехай E = a1., an – деякий алфавит. Через E* позначимо множину всіх слів в алфавібі E, включаючи однолітерні слова виду 'ai' і пусте слово e =''.