обчіслює Значення f [A] ( Функції f [A] в точці , if [A] ()
= bm. Нагадаємо, что bm пріроднім чином можна інтерпретуваті як число, что находится в віхідній змінній y в стані c [t] алгоритму A, так як, по припущені, zm = y.
Если в Траєкторії (9) ВСІ стани проміжкові, тоб Траєкторія T (A) є нескінченною послідовністю станів A, будемо вважаті, что A ціклює в точці , тому значенням f [A] ( Функції f [A] в точці НЕ Визначи, тоб f [A] () = @. Іншімі словами,
bm, коли T (A) - скінченна f [A] () = * p> @, коли T (A) - Нескінченна (8)
Аналогічно візначається Траєкторія и функція переходів для предикатного алгорітму Aq, и вважається что Aq реалізує предикат;
В
и q * = q [. t.];. t., коли T (A) - Скінченна,
P [Aq] () = *. 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). p> У Теорії алгорітмів вважається, что операторні 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. p> Нехай E = a1., an - Деяк алфавіт. Через E * позначімо множини всех слів в алфавібі E, включаючі однолітерні слова увазі 'ai' и пусте слово e = ''.
Введемо на E * деякі Стандартні Функції и Предикатом. Если w = x1x2 .. xm и v = y1y2 .. yk - слова iз E *, то
а) con (w, v) = wv = x1x2 .. xmy1y2 .. yk, con (E, v) = con (v, e) = v;
б) del (w) = d (w) = x2x3 .. xm, del (e) = e;
в) для всіх літер ai Із E предикат hai (w) = T (Істіно), коли x1 = ai, и hai (w) = F (Хибне), коли перша літера x1 у Слові w НЕ дорівнює ai (1 < = i < = m), Причому для всіх i
hai (e) = F.
Если а - довільна літера Із E *, то через (a ^ n) позначається слово, что склдається Із n літер a.
Клас схем програм KS-2 містіть (n + 1) Унарні функціональніх сімволів fa1, fa2., fan, g, один константност...
