Алгоритмічні проблеми — страница 10

  • Просмотров 6798
  • Скачиваний 62
  • Размер файла 80
    Кб

на множині слів довільного алфавіту E, або предикат P: E* –> T, F, будемо називати E – рекурсивною функцією (предикатом), або RE-функцією (RE-предикатом), якщо існує програма із класу КП-2 П1g, що обчислює g (P). Як відомо [1], [2], за допомгою кодуючої функції доводиться, що, в певному сенсі, клас R-функцій (R-предикатів) і клас RE-функцій (RE-предикатів) є еквівалентні. Приклади доведення по побудові RE-рекурсивності функцій і предікатьв наведені

далі. Побудуємо алгоритм, що обчислює функцію z:= f1 (x, y) = x + y. x, y! z q10 q11 q12 q13 q14 q15 q16 q17 q18 q19 x1 = x (q11, q11) y1 = y (q12, q12) z1 = 0 (q13, q13) P0 (x1) (q16, q14) z1 = z1 + 1 (q15, q15) x1 = x1 -^ 1 (q13, q13) P0 (y1) (q19, q17) z1 = z1 + 1 (q18, q18) y1 = y1 -^ 1 (q16, q16) z = z1 (Я, Я) Побудуємо алгоритм (не оптимальний), що заносить в z значення функції добутку x i y, тобто z:= f1 (x, y) = x * y. x, y! Z q20 q21 q22 q23 x2 = x (q21, q21) y2 = y (q22, q22) z2 = 0 (q23, q23) P0 (y2) (q25, q10) q10 q11 q12 q13 q14 q15 q16 q17 q18 q19 x1 = z2 (q11, q11) y1 = x (q12, q12) z1 = 0 (q13, q13) P0 (x1) (q16, q14) z1 = z1 + 1 (q15, q15) x1 = x1 -^ 1

(q13, q13) P0 (y1) (q19, q17) z1 = z1 + 1 (q18, q18) y1 = y1 -^ 1 (q16, q16) z2 = z1 (q24, q24) q24 q25 z2 = z1 (q23, q23) z = z2 (Я, Я) Нехай алфавіт Е = a, b. Побудуємо алгоритм, що обчислює предикат Pe(w), де Pe(w) = T тоді і тільки тоді, коли w є пусте слово із E*, тобто w = e. x! q [.t.], q [.f.] q10 x1 = x (q11, q11) q11 ha(x1) (q [.f.], q12) q12 hb(x1) (q [.f.], q [.t.]) Побудуємо алгоритм (не оптимальний), що заносить в z значення функції con (x, y) = xy, тобто z:= g1 (x, y) = con (x, y) = = xy для слів із Е = a, b. x, y! Z q20 q21 q22 x2 = x (q21, q21) y2 = y (q22, q22) z2 = e (q10, q10) q10 q11 q12 x1 = y2 (q11,

q11) ha(x1) (q22, q12) hb(x1) (q22, q28) q22 q23 q24 ha(y2) (q23, q25) x2 = con (x2, a) (q24, q24) y2 = del(y2) (q22, q22) q25 q26 q27 q28 hb(y2) (q26, q10) x2 = con (x2, b) (q27, q27) y2 = del(y2) (q25, q25) z = x2 (Я, Я) 4. Операторні та предикатні алгоритми -ІІ (Рекурсивні функції на областях, що відмінні від N) Оскільки БРМ працює тільки з натуральними числами, наше визначення обчислюваності і можливості розв'язання застосовано тільки до функцій і предикатів від натуральних чисел. Ці поняття легко поширюються на інші види

об'єктів (тобто цілі числа, поліноми, матриці і т.д.) за допомогою кодування. Кодуванням області D об'єктів називається явне й ефективне відображення α: D →N. Ми будемо говорити, що об'єкт α € D кодується натуральним числом α (d). Припустимо, що f є функцією з D в D; тоді f природно кодується функцією f* з N в N, що відображає код кожного об'єкта d € Dom(f) у код об'єкта f (d). У явному виді це можна записати як f*=α · f ·a-1 Тепер можна поширити визначення

Мнр-обчислюваності на область D, рахуючи функцію f обчислюваною, якщо f*–обчислювана функція натуральних чисел. Приклад. Розглянемо область Z. Явне кодування можна задати функцією α, де 2n, якщо n  0, α-(n) = -2n-1, якщо n < 0. Тоді α-1 задається так: (1/2) m, якщо m парне, α-1 (m) = (-1/2) (m+1), якщо m непарне. Тепер розглянемо функцію х-1 на Z; позначаючи цю функ-ю через f, одержуємо f*:N →N, що задається: 1, якщо x:==0 (тобто х=α(0)), f*(x)= х-2, якщо х> 0 і х парне (тобто