Теория алгоритмов и математическая логика

Тема 11

Елементи теорії алгоритмів

Алгоритми та обчислювальні функції

11.1. Основні означення

Період до початку XX століття можна вважати етапом накопичування інформації про алгоритми. Інтуїтивне розуміння алгоритму було достатнім, щоб вважати ту чи іншу процедуру розв’язання задач алгоритмом. Проте одночасно нагромаджувались проблеми, пошук алгоритму вирішення яких ні до чого не приводив. Та для того щоб довести, що алгоритм існує, достатньо його пред’явити, а ось для доведення його відсутності необхідне вже строге визначення шуканого об’єкта. Цим питанням і потрібно було зайнятися.

Оскільки в математиці поняття алгоритму тісно пов’язане з поняттям функції, то історично першою формалізацією алгоритму став клас обчислювальних функцій (К. Гьодель, А.Черч, 1935-1936 рр.). Основна ідея в тому, що довільний алгоритм можна звести до обчислення значення деякої числової функції, тобто з кожним алгоритмом можна зв’язати функцію, яку він обчислює. При цьому виникає ряд запитань: чи для будь-якої функції існує обчислювальний її алгоритм; для яких функцій алгоритми існують і як описати такі алгоритмічні функції? Пошук відповіді на ці питання й привів до створення теорії рекурсивних функцій.

При цьому необхідно зазначити, що в теорії обчислювальних функцій

визначають множину натуральних чисел N={0,1,2,3,…} і розглядають тільки числові функції, розуміючи під ними функції k змінних (k - місні функції), аргументи і значення яких належать N. Тобто, об’єкти з областю визначення Df [TEX]\subseteq [/TEX] Nk (k – ціле додатне) та з областю значень Rf[TEX]\subseteq [/TEX] N будемо називати к - місними частковими функціями. Термін “часткова“ нагадує, що функція визначена на підмножині Nk( звичайно, може статися, що Df = Nk, в такому разі функція стає всюди визначеною). Виходячи з вищезазначене, дамо означення обчислювальної функції.

Означення 11.1.1. Числову функцію f: Nk →N називають обчислювальною, якщо існує алгоритм, за допомогою якого можна обчислити значення функції для будь-якого набору значень аргументів із області визначення функції.

Надалі використовуватиме ідею К. Гьоделя та С. Кліні (1936 р.), за якою всі обчислювальні функції можна одержати із множини базисних функцій та алгебраїчних операцій. Самі операції прийнято називати операторами.

Розглянемо клас числових функцій, що використовуються як базис для побудови обчислювальних функцій:

  1. O(x)=0 - нуль-функція (можна задати і n - місну нуль - функцію On(x1, x2, …, xn) = 0).

  2. S(x)=х+1 - функція слідування або наступності (але не додавання одиниці).

  3. Inm (x1, x2, x3,.., xm, ... xn) = xm - функція проекції або введення фіктивних змінних або вибору аргументу.

Як операторів, застосування яких до базисних функцій призводить до утворення нових функцій оберемо такі три оператори:

  1. оператор суперпозиції ;
  2. оператор примітивної рекурсії ;
  3. оператор мінімізації або найменшого кореня.

У цьому розділі застосуємо алгебраїчний підхід до визначення класу обчислюваних функцій. Кожну обчислювальну функцію будемо одержувати з деяких найпростіших обчислювальних базисних функцій за допомогою операцій, обчислювальність яких також не викликає сумніву. Загальна схема знаходження, яка дала назву цьому підходу,  - рекурсія, спосіб задання функції шляхом визначення кожного її значення в термінах раніше визначених її значень та інших уже визначених функцій.

Таким чином, нетривіальні обчислювальні функції можна одержати за допомогою композиції (суперпозиції) вже відомих обчислювальних функцій. Цей спосіб є явно алгоритмічним.

 

11.2. Оператор суперпозиції

Операція суперпозиції полягає у підстановці одних арифметичних функцій замість аргументів інших функцій.

Нехай задана m-місна функція F(x1, x2, x3,.., xm) та m-на кількість n-місних функцій f1(x1, x2, x3,.., xn) , f2(x1, x2, x3,.., xn), f3(x1, x2, x3,.., xn),...,fm(x1, x2, x3,.., xn). Тоді говорять, що n-місна функція φ(x1, x2, x3,.., xn) утворилася в результаті підстановки у функцію F замість її аргументів m функцій f1, f2, f3,..., fm. Така підстановка називається суперпозицією Snm. Тоді

Snm(F, f1, f2, ..., fm) = F (f1(x1, x2, .., xn) , f2(x1, x2, .., xn),...,fm(x1, x2, .., xn)) = φ (x1, x2, .., xn).                                                                       (11.2.1)

Приклад 11.2.1.. Здійснити суперпозицію нуль-функції та функції слідування, тобто знайти S2(S(x); O(x)).

Розв’язання. Для визначення результату операції суперпозиції потрібно функцію O(x)=0 підставити в S(x) = x+1 замість значення аргументу. Отримаємо S2(S(x);O(x)) = S(O(x)) = O(x) + 1 = 0+1 = 1.

 

11.3. Оператор примітивної рекурсії

Оператор примітивної рекурсії (Rn) дозволяє будувати n+1-місну

арифметичну функцію f(x1, x2, x3,.., xn, у) з двох заданих функцій, одна з яких є n-місна φ(x1,x2,..,xn), а інша - n+2-місна функція ψ(x1,x2,..,xn,у,z) за такою схемою: f(x1, x2, x3,.., xn,0) = φ (x1,x2,..,xn);

f(x1, x2, x3,.., xn,у+1)= ψ(x1,x2,..,xn,у, f(x1, x2, x3,.., xn, у)).                                                                                                                                ( 11.3.1)

Таким чином, f(x1, x2, x3,.., xn, у) = Rn(φ,ψ).

Для розуміння операції примітивної рекурсії необхідно зазначити, що будь-яку функцію від меншої кількості аргументів можна розглядати як функцію від більшої кількості аргументів. Зокрема, функції - константи (n=0) є одномісними і відповідно: f(x)=a; f(x, y +1) = ψ(x,y, f(y)), де а – константа.

Схеми примітивної рекурсії визначають функцію f тільки через інші функції φ та ψ, а й через значення f у попередніх точках – значення f у точці (у+1) залежить від значення f у точці (у).

Приклад 11.3.1. Знайти значення функції f(3,2), якщо вона задана співвідношеннями

f(x, 0) = 0; f(x, y+1) = f(x, y) + x.

Розв’язання. У даному разі за схемою (11.3.1) маємо : f(x, 0) = φ(x) = 0,

ψ(x,y,z) = y + z. Виходячи з того, що f(x, 0) = φ(x) = 0 при будь-якому x, тоді й f(2, 0) = 0. Обчислюючи послідовно, одержимо:

f(2, 1) = f(2 ,0) + 2 = 0+ 2 = 2;

f(2, 2) = f(2, 1) + 2 = 2+ 2 = 4;

f(3, 2) = f(2, 2) + 2 = 4+ 2 = 6, що є остаточною відповіддю.

Нескладно довести, що в даному прикладі f(x,y)=x • y.

 

11.4. Оператор мінімізації

Розглянемо обчислювальну n+1 -місну функцію f(x1, x2, x3,.., xn, xn+1). Зафіксуємо значення x1, x2, x3,.., xn її перших n аргументів та розглянемо рівняння f(x1, x2, x3,.., xn, у) = 0, тобто знайдемо значення, у при якому функція дорівнює нулю. Більш складною буде задача відшукати найменше з усіх значень у, при якому f(x1, x2, x3,.., xn, у) = 0. Оскільки результат знаходження залежить від х1, х2, …,хn , то й найменше значення у є також їх функцією. Введемо позначення

φ (х1, х2, …,хn) = µу [ f(х1, х2, …,хn, y) = 0],                                                                                                                                   (11.4.1)

де у таке, що f(х1, х2, …,хn, y) = 0, а µу – оператор мінімізації.

Для знаходження функції φ(х1, х2, …,хn) можна запропонувати таку процедуру.

1. Обчислюємо f(x1,…xn,0); якщо її значення буде нуль, то φ(x1,…xn)=0. Якщо f(x1, …xn,0) [TEX]\neq [/TEX] 0, то переходимо до наступного кроку.

2. Обчислюємо f(x1,…xn, 1); якщо її значення буде нуль, то φ(x1,…xn)= 1. Якщо f(x1, …xn,0)  [TEX]\neq [/TEX]  0, то переходимо до наступного кроку.

І так далі, поки не знайдемо перше значення у, при якому f(x1, …xn, у) = 0.

Якщо визначиться, що для всіх у f(x1, …xn, у)  [TEX]\neq [/TEX]  0, то функція φ(x1,…xn) вважається невизначеною.

Приклад 11.4.1. Розглянемо функцію φ(x,y)=x – y, яку можна отримати за допомогою µ-оператора d(x,y)=µz[y+z=x]=µz[S((I32 (x,y,z), I33 (x,y,z),)]= I31 (x,y,z) та обчислимо f(7,2).

Розв’язання. Задамо у значення 2 та встановимо змінній z послідовно значення 0,1,2.., кожного разу обчислюючи суму у+z. Як тільки при якомусь першому в заданому порядку z сума дорівнюватиме 7, то відповідне значення візьмемо за значення d(7,2). Проведемо обчислення:

z=0 2+0=2 < > 7

z=1 2+1=3 < > 7

z=2 2+2=4 < > 7

z=3 2+3=5 < > 7

z=4 2+4=6 < > 7

z=5 2+5=7=7

Таким чином, d(7,2)=5.

11.5. Гіпотеза Черча та примітивно-рекурсивні функції

Означення 11.5.1. Функцію називають примітивно-рекурсивною, якщо вона утворена з найпростіших функцій за допомогою скінченного числа застосувань операторів суперпозиції Snm та примітивної рекурсії Rn .

Означення 11.5.2. Функцію називають частково-рекурсивною, якщо вона утворена з найпростіших функцій за допомогою скінченного числа застосувань операторів суперпозиції Snm , примітивної рекурсії Rn та мінімізації µу.

З цих означень та зауваження щодо зберігання операторами властивості обчислювальності функцій випливає, що кожна стандартно задана частково-рекурсивна функція є обчислювальною за певною процедурою, яка відповідає інтуїтивному уявленню алгоритму, а з іншого боку  які б досі не будувалися класи точно визначених алгоритмів, завжди з‘ясовувалося, що числові функції, які обчислювалися за алгоритмами цих класів, були частково-рекурсивними. Тому загальноприйнятою є така наукова гіпотеза (теза Черча).

Гіпотеза (теза) Черча. Клас алгоритмічно обчислювальних часткових числових функцій збігається з класом усіх частково-рекурсивних функцій.

До формулювання цієї тези входить інтуїтивне поняття обчислювальності, тому його не можна ні спростувати, ні довести. Це факт, на користь якого свідчить багаторічна математична практика.

Історично це була перша гіпотеза щодо зв’язків між класами інтуїтивних і точних алгоритмів.

Зрозуміло, що будь-яка примітивно рекурсивна функція є частково рекурсивною, оскільки за визначенням оператори для побудови частково рекурсивних функцій містять у собі оператори для побудови примітивно рекурсивних функцій. Також зрозуміло, що примітивно рекурсивна функція визначена скрізь і тому є загальнорекурсивною функцією (у примітивно рекурсивної функції немає приводу «зависати», тому що при її побудові використовуються оператори, що визначають скрізь визначені функції).

Досить складно довести існування і навести приклад загальнорекурсивної функції, що не є примітивно рекурсивною.

Функція Аккермана — приклад такої обчислювальної функції, яка не є примітивно рекурсивною. Вона набуває два невід'ємних цілих числа як параметри і повертає натуральне число, позначається A(m;n). Ця функція зростає дуже швидко, наприклад, число A (4;4) настільки велике, що кількість цифр у порядку цього числа у багато разів перевершує кількість атомів в спостережуваної частини Всесвіту. Функція Аккермана визначається рекурсивно для невід’ємних цілих чисел та таким чином:

[TEX]A(m,n)=\begin{cases}n+1, & m = 0\\
A(m-1,1)&m>0,n=0;\\
A(m-1),A(m,n-1)), & m > 0,n>0\end{cases} [/TEX]                                                                                                                                                      (11.5.1)

За означенням примітивно-рекурсивної функції, наведеним вище, неважко знайти процедуру, що породжує всі примітивно-рекурсивні функції.

Надамо цьому означенню більш формального індуктивного вигляду.

  1. Функції О(x) =0, S(x)=x+1, Inm (x1, x2, …, xm,…,xn) = x для всіх натуральних n, m є примітивно-рекурсивними.

  2. Якщо g1(x1,…,xn), …, gm(x1,…,xn), h(x1,…,xm) – примітивно-рекурсивні функції, то Snm(h,g1,…,gm) – примітивно-рекурсивні функції для будь-яких натуральних n,m.

  3. Якщо g(x1,…,xn), та h(x1,…,xn,y,z) — примітивно-рекурсивні функції, то Rn (g,h) — примітивно-рекурсивна функція.

  4. Інших примітивно-рекурсивних функцій немає.

Приклад 11.5.1. Навести приклади арифметичних функцій, що є примітивно-рекурсивними.

Розв’язання . Функція додавання двох натуральних чисел Sum(a,b) = =a+b. Ця функція може бути розглянута як примітивно-рекурсивна функція двох змінних, одержувана внаслідок застосування оператора примітивної рекурсії до функцій I11 та F, другу з яких одержимо підстановкою функції проекції I33 у функцію слідування S. Покажемо це математично:

Sum (x,0) = I11(x),

Sum(x,y+1) = x+y+1=Sum(x,y)+1 = S(Sum(x,y)),

Sum(x, y) = R1(I11(x), F(x, y, z)), де F(x, y, z) = S(I33(x, y, z))=z+1.

Функція множення двох натуральних чисел Mul(a,b) = a•b.

Ця функція може бути розглянута як примітивно-рекурсивна функція двох змінних, одержувана внаслідок застосування оператора примітивної рекурсії до функцій O та G, другу з яких одержимо підстановкою функції проекції I13та I33 у функцію додавання Sum. Покажемо це математично.

Mul(x, 0) = O(x),

Mul(x,y+1) = x [TEX]\times [/TEX] y+x = G(x, y, Mul(x, y)),

G(x, y, z) = Sum( I13(x, y, z), I33(x, y, z)),

Mul(x, y) = R1(O(x), G(x, y, z).

 

 

Тема 11 Запитання для самоперевірки
© 2014 СумГУ
created with Lectur'EDbeta