осліджуємо сам клас частково рекурсивних функцій [7]. Даний клас визначається шляхом вказівки конкретних вихідних функцій і фіксованого безлічі операцій отримання нових функцій із заданих.
В якості базисних функцій зазвичай беруться наступні:
1. Нуль-функція:;
2. Функція прямування:;
3. Функція вибору аргументів:. p> Допустимими операціями над функціями є операції суперпозиції (підстановки), рекурсії та мінімізації.
Операція суперпозиції . Нехай дано-місна функція і функцій. Вважаємо, що функції залежать від одних і тих же змінних. Це можна зробити шляхом введення фіктивних змінних. Суперпозицією (підстановкою) функцій і називається функція
.
Функція на наборі змінних визначена тоді і тільки тоді, коли визначені всі функції і функція визначена на наборі. Операцію суперпозиції позначають:.
Операція рекурсії (точніше: примітивної рекурсії). Нехай задані-місна функція і-місна функція. Визначимо-місцеву функцію індуктивним чином з допомогою співвідношень:
;
.
Ясно, що дані співвідношення однозначно визначають функцію. вважається визначеною у тому і тільки в тому випадку, коли визначені і при. Значить, якщо не визначено, то й неопределено прі. Про функцію говорять, що вона отримана рекурсією з функцій і, і позначають:.
Операція мінімізації . Нехай задана-місна функція. Зафіксуємо набір і розглянемо рівняння щодо:
.
Будемо вирішувати дане рівняння, обчислюючи послідовно,, і т.д. і порівнюючи с. Найменше, для якого виконано рівняння позначимо. При цьому вважаємо, що визначено, якщо визначено при всіх. В іншому випадку вважаємо, що неопределено. Значення є функція від змінних, про яку говорять, що вона отримана з мінімізацією і позначають:.
Функція називається частково-рекурсивної, якщо вона може бути отримана з базисних функцій,, застосуванням кінцевого числа раз операцій суперпозиції, рекурсії та мінімізації.
Який же зв'язок між частково рекурсивними функціями і теорією алгоритмів? Цю зв'язок встановлює В«теза ЧерчаВ» [8], для формулювання якого введемо поняття обчислюваної функції.
Визначення [9]. Функція називається алгоритмічно обчислюваною, якщо існує алгоритм знаходження значення функції при будь-якому допустимому значенні аргументу.
Очевидно, що функції, і алгоритмічно обчислюваних. Можна довести, що операції суперпозиції, рекурсії та мінімізації зберігають властивість вичіслімості [10]. Значить, все частково рекурсивні функції вичіслімих. Теза Черча стверджує, що клас алгоритмічно обчислюваних функцій збігається з класом всіх частково рекурсивних функцій. Тобто виконується і зворотне включення: всі обчислюваної функції частково рекурсивні. Прийняття даної тези дозволяє тлумачити доказ, що деяка функція не є частково рекурсивної, як доказ відсутності алгоритму обчислення її значень.
Апарат частково рекурсивних функцій дозволяє д...
