рекурсивні функції
Будемо розглядати тільки числові функції, т. Е. Функції, аргументи і значення яких належать множині натуральних чисел N (N = 0,1,2, ...).
Якщо область визначення функції збігається з безліччю, то функція називається усюди певної, інакше - частково визначеною.
f (x, y) = x + y - усюди певна функція,
f (x, y) = x-y - частково певна функція, т. к. вона визначена тільки для.
Рекурсивне визначення функції - це таке визначення, при якому значення функції для даних аргументів визначається значеннями тієї ж функції для більш простих аргументів або значеннями простіших функцій.
1. Числа Фібоначчі (1, 1, 2, 3, 5, 8, ...) це послідовність чисел f (n), де f (0) = 1, f (1) = 1, f (n + 2) = f (n) + f (n + 1).
2. Факторіал (n! = 1 * 2 * 3 * ... * n) f (0) = 1, f (n + 1) = f (n) * (n + 1).
Рекурсивні функції будуються на основі трьох примітивних (завідомо однозначно розуміються і реалізуються) функцій. Їх також називають найпростішими.
1. S (x) = x + 1 - функція проходження.
Приклади. S (0) = 1, S (1) = 2, S (-5) - не визначена.
2. О (х) = 0 - нуль-функція;
Приклади: О (0) = 0, О (1) = 0, О (-5) - не визначена.
3. Im (x1, x2, ..., xn) = xm, (m = 1,2, ... n) - функція проектування (вибору аргументу).
З примітивними функціями можна виробляти різні маніпуляції, використовуючи три оператора: суперпозиції, примітивної рекурсії і мінімізації.
1. Оператор суперпозиції (підстановки).
Нехай f - m-місцева функція, g1, ... gm - n-місні операції на безлічі N. Оператор суперпозиції S ставить у відповідність операціям f і g1, ... gm n-місцеву функцію h.
1) Використовуючи оператор суперпозиції, можна отримати будь-яку константу.
S (S ... (O (x)) ...) = 0 + n, де число вкладень функцій проходження n.
2) Використовуючи оператор суперпозиції, можна виконати зрушення на константу n.
2. Оператор примітивної рекурсії
Оператор R кожної (n + 2) -Місцеві операції f і n-місній операції g ставить у відповідність (n + 1) -Місцеві операцію h = R (f, g), що задовольняє наступною схемою:
Для n = 0 схема примітивної рекурсії має вигляд:
, де а - константа,
Приклад: Обчислення факторіала з використанням оператора примітивної рекурсії буде виглядати наступним чином.
Схема примітивної рекурсії утворює процес побудови функції h, при якому на нульовому кроці використовується функція g, а на кожному наступному кроці значення функції f від аргументів, номера y попереднього кроку і значення функції h, обчисленого на попередньому кроці.
Функція називається примітивно-рекурсивної (ПРФ), якщо вона може бути отримана з найпростіших функцій за допомогою оператора суперпозиції або оператора примітивної рекурсії.
1) - примітивно-рекурсивна функція.
Схема примітивної рекурсії:
2) - примітивно-рекурсивна функція.
3. Оператор мінімізації (-оператор)
, де y - виділена змінна.
Роботу-оператора можна описати таким чином. Виділяється змінна y, потім фіксуються інші змінні. Значення у послідовно збільшується, починаючи з 0. Значним-оператора буде те значення у, при якому функція вперше звернулася в 0.
Якщо функція не вернулась в 0 або приймає негативне значення, то значення-оператора вважається невизначеним.
Зафіксуємо х = 1 і будемо міняти y.
Функція f (x1, x2, ..., xn) називається частково рекурсивної (ЧРФ), якщо вона може бути отримана з найпростіших функцій за допомогою кінцевого числа застосувань операцій суперпозиції, примітивної рекурсії і мінімізації.
f (x, y) = x-y - часткова, т. к. вона не визначена, якщо x Властивості усіченої різниці. Функція примітивно рекурсивна, т. К. За схемою примітивної рекурсії: Т. о. її можна отримати з найпростіших функцій О (х) і Im (x1, ... xn) за допомогою оператора найпростішої рекурсії R. За схемою примітивної рекурсії Т. о. функцію можна отримати за допомогою операції примітивної рекурсії з функцій і h (x, y, z) =. Отже, функція f (x, y) = x-y є частково-рекурсивної функцією. Усюди певна частково-рекурсивна функція є общерекурсівной (ОРФ). Для алгоритмічних проблем типовою є ситуація, коли потрібно знайти алгоритм для обчислення числової функції f (x1, ... xn). Числові функції, значення яких можна обчислити за допомогою деякого алгоритму, називаються обчислюваної функції. Це поняття інтуїтивно, т. К. Інтуїтивно поняття алгоритму. Функція f (x1, ... xn) ефективно обчислюваності, якщо існує алгоритм, за допомогою якого можна знайти f (k1, ... kn), якщо відомі k1, ... kn. Теза Черча. Будь-яка ефективно обчислювана функція є частково-рекурсивної функцією. В формулювання тези Черча входить поняття ефективної обчислюваності. Тому його не можна ні довести, ні спростувати в математичному сенсі. Часткова рекурсивность - це уточнення поняття обчислюваної функції. З його допомогою можна уточнювати або спростовувати вичіслімость. Будь-яка частково-рекурсивна функція є обчислюваною по Тьюрингу і навпаки.
Схожі статті