• Задачі для самостійного розв’язування

Задачі для самостійного розв’язування

1. Знайти за допомогою оператора регулярної суперпозиції функцію h(x,y), якщо

F(x,y.z) = 2x+y+3z -1;

f₁(x,y) = x+y;  f₂(x,y)  = xy; f₃(x,y) = 3x+2y+1.

2. Показати, що функцію

можна одержати з базисних функцій за допомогою оператора примітивної рекурсії.

3. За допомогою оператора мінімізації  знайти функцію h(x,y), якщо f(x,y,z)=x+y+z.

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

5. За означенням примітивно-рекурсивної функції  та процедурою породження примітивно-рекурсивних функцій  покажіть, що симетрична різниця двох натуральних чисел Sub(a,b) =  ∣a-b∣ можна розглядати  як примітивно-рекурсивну функцію.

Коментарі. Основні відомості цього розділу містяться в [5,6,11,17,21,22]. У  розділі не представлена відома формалізація, що використовується в теорії  обчислювальності і яка має назву  лямбда - числення. Це числення було запропоноване А. Черчем та С. Кліні в 1930-ті роки як спроба розробити базис математики на основі функцій. Однак через знайдені парадокси ця система функцій виявилася суперечливою. З лямбда - численням можна ознайомитися, наприклад, у [8,9,12].