Войти на сайт

или
Регистрация

Навигация


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-функцій вважаються точним аналогом інтуїтивного поняття алгоритму (взагалі кажучи, часткового).


Информация о работе «Алгоритмічні проблеми»
Раздел: Математика
Количество знаков с пробелами: 54576
Количество таблиц: 5
Количество изображений: 0

Похожие работы

Скачать
33080
5
4

... число эпох функционирования алгоритма, или определение его сходимости, обычно путем сравнивания приспособленности популяции на нескольких эпохах и остановки при стабилизации этого параметра. 3. Непрерывные генетические алгоритмы. Фиксированная длина хромосомы и кодирование строк двоичным алфавитом преобладали в теории генетических алгоритмов с момента начала ее развития, когда были получены ...

Скачать
18213
1
5

... в состояние qj, заменяя содержимое ячеек соответственно символами аb1 - аbк, то после этого ленты соответственно сдвигаются в направлениях k1... kk. До сих пор принималось, что различные алгоритмы осуществляются на различных машинах Тьюринга, отличающихся набором команд, внутренним и внешним алфавитами. Однако, можно построить универсальную машину Тьюринга, способную выполнять любой алгоритм ...

Скачать
26020
3
4

... M2(n) = O(l n), C2(n) = O(l n). Оскільки l = log2n, M2(n)=O(n log2 n)), C2(n)=O(n log2 n), Але З(n) = C1(n) + C2(n), M(n) = M1(n) + M2(n). Тому що C1(n) < C2(n), M1(n) < M2(n), остаточно одержуємо оцінки складності алгоритму TreeSort за часом: M(n) = O(n log2 n), C(n) = O(n log2 n), У загальному випадку, коли n не є ступенем 2, сортуюче дерево будується трохи інакше. “Зайвий” елемент ...

Скачать
10075
2
1

... U4 сравнения двух целых чисел оставляем читателю в качестве упражнения. Замечание: исходное слово надо задать в форме  * Для нормальных алгоритмов Маркова справедлив тезис, аналогичный тезису Тьюринга. Тезис Маркова: Для любой интуитивно вычислимой функции существует алгоритм, ее вычисляющий. Построение алгоритмов из алгоритмов. До сих пор, строя ту или иную МТ, или НАМ мы каждый раз ...

0 комментариев


Наверх