Логика. логіка. Математична логіка та теорія алгоритмів
 Скачать 1.6 Mb.
|
|
Приклад 3. Нехай задана константа (константна функція ) (x g k )і функція двох аргументів ) , ( y x h . Схема примітивної рекурсії: )). ( , ( ) 1 ( , ) 0 ( x f x h x f k f визначає функцію одного аргументу ) (x f , значення якої можна послідовно обчислити, якщо відомі значення ) , ( y x h , дійсно: ))), , 0 ( , 1 ( , 2 ( )) 2 ( , 2 ( ) 3 ( )), , 0 ( , 1 ( )) 1 ( , 1 ( ) 2 ( ), , 0 ( )) 0 ( , 0 ( ) 1 ( k h h h f h f k h h f h f k h f h f …. 107 Очевидно, що за допомогою операції примітивної рекурсії при заданих функціях g i h функція f визначається однозначно. Приклад 4. Покажемо, що функція додавання двох натуральних чисел визначається схемою примітивної рекурсії за допомогою функцій x x I ) ( 1 1 та функції слідування 1 ) , , ( z z y x S , в якої аргументи х і у є фіктивними. Дійсно, маємо: )). , ( , , ( 1 ) ( ) 1 ( ) 1 , ( ), ( 0 ) 0 , ( 1 1 y x f y x S y x y x y x f x I x x f Функції, які будуються з базових арифметичних функцій за допомогою операцій суперпозиції і примітивної рекурсії, застосованих скінченне число разів у довільній послідовності, називаються примітивно-рекурсивними функціями. Оскільки базові функції всюди визначені, а операції підстановки і примітивної рекурсії зберігають всюди визначеність побудованих функцій, то всі примітивно-рекурсивні функції всюди визначені. Більшість відомих арифметичних функцій належать до класу примітивно- рекурсивних функцій. Ми вже мали нагоду переконатися (див. приклад 4) що функція y x y x f ) , ( є примітивно рекурсивною, оскільки вона одержується за схемою примітивної рекурсії із базових арифметичних функцій ) ( 1 1 x I і 1 ) , , ( z z y x S , які є примітивно рекурсивними. Приклад 5. Довести, що наступні функції є примітивно рекурсивними: а) y x y x f ) , ( Ця функція задається такою схемою примітивної рекурсії: )). , ( , , ( ) 1 ( ) 1 , ( ), ( 0 ) 0 , ( y x f y x h y x x y x y x f x O x x f де функції ) (x O і z x z y x h ) , , ( (сума з фіктивним аргументом у) - примітивно рекурсивні, а значить і y x y x f ) , ( є примітивно рекурсивною функцією. б) 0 , 0 ; 1 , 1 ) ( x якщо x якщо x x f Цю функцію позначають символом 1 x . Для неї маємо: ). , ( 1 ) 1 ( ), ( 0 1 0 2 1 y x I x x x O 108 Таким чином, функція 1 ) ( x x f визначається примітивною рекурсією за допомогою примітивно рекурсивних функцій ) (x O та ) , ( ) , ( 2 1 y x I y x h , а тому функція 1 ) ( x x f є примітивно рекурсивною. в) , 0 ; , ) , ( y x y x y x y x y x f Ця функція задається такою схемою примітивної рекурсії: )), , ( , , ( 1 ) ( ) 1 ( ), ( 0 1 1 y x f y x h y x y x x I x x де одномісна функція ) ( 1 1 x I та трьохмісна функція 1 ) , , ( z z y x h (в якої аргументи х і у є фіктивними) є примітивно рекурсивними. г) 0 , 0 ; 0 , 1 ) ( x x x sg Досить переконатися, що: ), , ( 1 ) 1 ( ), 0 ( 0 ) 0 ( y x h x sg O sg де ) , ( ) , ( 2 1 y x c y x h – константна функція 1 від 2-ох змінних. Отже, ) (x sg одержується схемою примітивної рекурсії з констант 0 та І, які є примітивно рекурсивними функціями. д) ! ) ( x x Вважаючи, що 1 ! 0 ) 0 ( , маємо: (0) 1, ( 1) ! ( 1) ( , ( )), x x x h x x де ( , ) ( ( ), ( )) h x y f s x x - добуток, звідки слідує, що функція ! ) ( x x є примітивно рекурсивною. Приклад 6. Нехай ) , max( y x - двомісна функція, значення якої дорівнює більшому з пари чисел } , { y x . Довести, що ) , max( y x є примітивно рекурсивною функцією. Доведення, що функція ) , max( y x є примітивно рекурсивною слідує з того, що вона задається наступною формулою: ) ( ) ( ) , max( y x sg y y x sg x y x 109 Приклад 7. Розглянемо функцію y x y x ent - частка від ділення числа х на число у, причому домовимось, що x x 0 . Довести, що функція y x – примітивно рекурсивна. За означенням y x дорівнює найбільшому числу n такому, що x ny , а y n x ) 1 ( . Всі різниці x iy дорівнюють нулю при n i і відмінні від нуля тоді, коли x i n 1 . Таким чином, якщо і змінюється від 1 до х, то вираз x iy дорівнює нулю точно n разів. Отже, x i x iy sg y x 1 ) ( . Враховуючи рівність 0 0 x і одержану формулу, легко вказати схему примітивної рекурсії, якою визначається функція y x Приклад 8. Позначимо остачу від ділення числа х на число у через ) , ( y x rest , причому за її означенням x x rest ) 0 , ( . Чи буде функція ) , ( y x rest примітивно рекурсивною? Позитивна відповідь на поставлене питання слідує з того, що функція ) , ( y x rest задається через відомі примітивно рекурсивні функції формулою: y x y x y x rest ) , ( Приклад 9. Визначимо двомісний предикат ) , ( y x div у такий спосіб: , 0 , , 1 ) , ( y x y x y x div Чи можна вважати цей предикат примітивно рекурсивною функцією? Так, тому що )) , ( ( ) , ( y x rest sg y x div Приклад 10. Нехай ) (x d - число всіх різних дільників числа х. Довести, що функція ) (x d є примітивно рекурсивною. Виходячи з означення функції ) , ( y x div , можемо записати, що 1 ) , ( x x div і 0 ) , ( y x div , якщо y x . Кожного разу, коли х ділиться на і, 1 ) , ( i x div . Тому x i i x div x d 0 ) , ( ) ( 110 Остання формула дає можливість легко записати схему примітивної рекурсії, якою І підтверджується примітивна рекурсивність функції ) ( x d Приклад 11. Характеристичну функцію ) ( x множини М визначимо таким способом: , 0 , , 1 ) ( M x M x x Довести, що характеристична функція множини всіх простих чисел є примітивно рекурсивною. Для цього досить показати, що ця функція є суперпозицією відомих примітивно рекурсивних функцій, а саме: 2 ) ( ) ( x d sg x Як показують приклади 1-11 багато відомих арифметичних функцій належить до класу примітивно рекурсивних функцій. Але цей клас функцій не охоплює всіх обчислювальних арифметичних функцій, що можна довести такими теоретико-множинними міркуваннями. Як легко бачити, множина примітивно рекурсивних функцій зліченна. Множина ж обчислювальних теоретико-числових функцій виду tn , де n - фіксоване натуральне число, а t приймає всі дійсні невід'ємні значення, утворює множину потужності континуум. Отже, існують. такі обчислювальні функції, які не є примітивно рекурсивними. Досить просто навести приклад такої обчислювальної функції, яка не є примітивно рекурсивною. Справа в тому, що всі примітивно рекурсивні функції всюди визначені, а, наприклад, функція однієї натуральної змінної ) (x f , значенням якої є найменше z, яке задовольняє рівнянню x+1+z=0, ніде невизначена. Для розширення класу примітивно рекурсивних функцій введемо нову операцію, так звану операцію найменшого кореня або операцію мінімізації. Операція найменшого кореня (мінімізації) дає можливість визначити функцію ) ,..., , ( 2 1 n x x x f від n змінних за допомогою відомої арифметичної функції ) , ,..., , ( 2 1 y x x x g n від (n+1)-ї змінної. Для будь-якого набору значень змінних n n a x a x ,..., 1 1 в ролі відповідного значення функції ) ,..., , ( 2 1 n a a a f приймається найменше натуральне число у, для якого 0 ) , ,..., , ( 2 1 y a a a g n . Позначається ця операція так: 0 ) , ,..., , ( 2 1 y a a a g n y , де y символ операції найменшого кореня, а в 111 квадратних дужках стоїть предикат, який набуває значення 1 при y Очевидно, що значення є функцією ) ,..., , ( 2 1 n a a a f . Отже, шукана функція ) ,..., , ( 2 1 n x x x f визначається так: 0 ) , ,..., , ( ) ,..., , ( 2 1 2 1 y x x x g x x x f n y n При цьому, якщо не існує таких значень у, при яких 0 ) , ,..., , ( 2 1 y x x x g n , то функція ) ,..., , ( 2 1 n x x x f вважається невизначеною на відповідному наборі значень n x x x ,..., , 2 1 . Крім того вважається, що функція ) ,..., , ( 2 1 n x x x f невизначена на такому наборі значень аргументів n n a x a x ,..., 1 1 , для якого існує корінь рівняння 0 ) , ,..., , ( 2 1 y a a a g n , проте хоча б для одного значення ) 0 ( функція ) , ,..., , ( 2 1 n a a a g невизначена. Функції, які будуються з базових арифметичних функцій за допомогою скінченного числа операцій суперпозиції, примітивної рекурсії та мінімізації, називаються частково рекурсивними функціями (ЧРФ). Всюди визначені частково рекурсивні функції називаються загально рекурсивними функціями (ЗРФ). Очевидно, що кожна ЧРФ є обчислювальною. Обернена твердження складає зміст гіпотези Черча: будь-яка частково обчислювальна функція є ЧРФ. Оскільки інтуїтивне поняття алгоритму було ототожнене з поняттям обчислювальної функції, то гіпотеза Черча може бути сформульована і в такому вигляді: будь який алгоритм може бути реалізований деякою ЧРФ. Обґрунтування гіпотези Черча проводиться аналогічно обґрунтуванню гіпотези Маркова. Після здійснення нумерації вхідних і вихідних слів будь-який нормальний алгоритм може бути реалізований деякою ЧРФ. Навпаки, всякий алгоритм, що реалізується за допомогою ЧРФ, виявляється еквівалентним деякому нормальному алгоритму. Отже, має місце таке твердження: алгоритм нормалізований тоді і тільки тоді, коли його можна реалізувати у вигляді ЧРФ. Таким чином, на основі уточнення поняття обчислювальних функцій як частково рекурсивних функцій будується загальна теорія алгоритмів, яка рівносильна розглянутій раніше теорії нормальних алгоритмів. 112 Приклад 12. Показати, що застосування операції найменшого кореня до функції ) , ,..., , ( 2 1 y x x x g n , коли вона є функцією одного аргументу, тобто ) ( y g породжує константу (константну функцію), тобто 0 ) ( y g y Дійсно, щоб знайти y , таке що 0 ) ( y g y , потрібно знайти корені рівняння 0 ) ( y g і в ролі взяти мінімальний, тобто буде константа. При цьому, якщо не існує кореня рівняння 0 ) ( y g , то буде всюди невизначеною функцією. Приклад 13. За допомогою оператора мінімізації знайти функцію ) , ( y x f , якщо z y x z y x g ) , , ( Найменше значення z, при якому для заданих х, у функція g дорівнює нулю, є сума х+у. Для всіх значень Z , менших х+у, функція g визначена і не дорівнює нулю. Отже ) 0 ( ) , ( z y x y x y x f z |