Ноу Інти, лекція, алгоритми частково рекурсивні функції

Анотація: Оператори суперпозиції, примітивної рекурсії і мінімізації. Класи частково рекурсивних і примітивно рекурсивних функцій. Програмна вичіслімость частково рекурсивних функцій. Рекурсивность табличних функцій, функцій, визначених за допомогою підсумовування і твори, кусочно заданих функцій, функцій нумерації n-ок і функцій, визначених спільної рекурсією

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

Клас частково рекурсивних функцій

Визначення рекурсивних функцій

Ми будемо розглядати часткові арифметичні функції f n (x1. Xn): N n -> N. Тут верхній індекс n у імені функції f позначає число її аргументів ( "арность"). Якщо арность зрозуміла з контексту або несуттєва, то цей індекс будемо опускати. Визначимо спочатку три оператора, що дозволяють за одними функцій отримувати інші.

Визначення 8.1. Суперпозиція. Нехай F m і f1 n. fm n - арифметичні функції. Скажімо, що функція G n отримана з F m. f1 n. fm n за допомогою оператора суперпозиції (позначення: G n = [F m; f1 n. fm n]), якщо для всіх наборів аргументів (x1. xn)

При цьому для кожного набору аргументів (a1. An) функція (тобто визначена), якщо визначені всі значення f1 n (a1. An) = b1. fm n (a1. an) = bm і.

Визначення 8.2. Примітивна рекурсія. Скажімо, що функція F n + 1 (x1. Xn, y) отримана за допомогою оператора рекурсії з функцій g n (x1. Xn) і h n + 2 (x1. Xn. Y, z). якщо вона може бути задана схемою примітивної рекурсії

У цьому випадку будемо писати F n + 1 = R (g n, h n + 2).

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

Визначення 8.3. Мінімізація. Скажімо, що функція F n (x1. Xn) отримана за допомогою оператора мінімізації (-оператора) з функції g n + 1 (x1. Xn, y). якщо F n (x1. xn) визначена і дорівнює y тоді і тільки тоді, коли всі значення g n + 1 (x1. xn, 0). g n + 1 (x1. xn, y-1) визначено і не рівні 0, а g n + 1 (x1. xn, y) = 0. У цьому випадку будемо писати

Визначення 8.4. Найпростіші функції. Функція називається найпростішої, якщо вона є однією з наступних функцій:

• o 1 (x) = 0 - тотожний нуль;
• s 1 (x) = x + 1 - наступне число (плюс один);
• функції вибору аргументу Im n (x1. xn) = xm (1 <= m <= n) .

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

Визначення 8.5. Частково рекурсивні функції. Функція f називається частково рекурсивної функцією (ч.р.ф.), якщо вона є однією з найпростіших функцій або може вийти з них за допомогою кінцевого числа застосувань операторів суперпозиції. примітивної рекурсії і мінімізації. тобто існує послідовність функцій f1, f2. fn = f. кожна з яких є або найпростішої, або отримана з Попереднє за допомогою одного із зазначених операторів. Зазначена послідовність функцій називається частково рекурсивним описом функції f.

Функція f називається общерекурсівной функцією (о.р.ф.), якщо вона частково рекурсивна і всюди визначена.

Функція f називається примітивно рекурсивної функцією (п.р.ф.), якщо вона частково рекурсивна і для неї існує частково рекурсивне опис, що використовує лише оператори суперпозиції і примітивної рекурсії. У такому випадку воно називається примітивно рекурсивним описом функції f.

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

Наведемо деякі приклади частково рекурсивних функцій.

Приклад 8.1. Постійні функції.