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

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.