Подразделы

Другие разделы

Дата и время

09/04/2025 22:41:04

Авторизация

Вычислительные основы

Реальные компьютеры vs. модели вычислений Детерминированный конечный автомат Машина Тьюринга Нормальный алгоритм Маркова Теория рекурсивных функций * Практическое использование

Теория рекурсивных функций *

Всякий алгоритм однозначно ставит в соответствие исходным данным (в случае если определен на них) определенный результат. Поэтому с каждым алгоритмом однозначно связана функция $y=f(x)$ , которую он вычисляет.

Теория рекурсивных функций, разработанная в 1930-х, исследует вопрос возможности построения алгоритмически вычислимых функций.

Множество исследуемых объектов (в данном случае функций) строится из конечного числа исходных объектов – базиса – с помощью простых операций, эффективная вычислимость которых достаточна очевидна.

Вычислимая функция – это такая функция, для которой существует алгоритм, вычисляющий ее значения.

Так как в этом определении алгоритм понимается в интуитивном смысле, то и понятие вычислимой функции является интуитивным.

Для простоты будем рассматривать только числовые функции, т.е. функции, аргументы и значения которых принадлежат множеству чисел $N={0, 1, 2, ...}$ .

Если значение функции $f$ определено на всей области определения, то говорят, что функция $f$ всюду определена, в противном случае – частично определена. Например, $f(x,y)=x+y$ является всюду определенной, а функция $f(x,y)=x-y$ – частично определенной.

Рекурсивным определением функции принято называть такое определение, при котором значения функции для данных аргументов определяются значениями функции для более простых аргументов (уже вычисленных) или значениями более простых функций. Одним из простых примеров рекурсивного определения являются, например, функция для вычисления числа Фибоначчи: $f(0)=1; f(1)=1; f(n+2)=f(n+1) + f(n)$ .

Простейшими и всюду определенными числовыми функциями являются:

нуль-функция $0(x)=0$ ;
функция следования $S(x)=x+1$ ;
функция проекции $I_n^m(x_1,...,x_n)=x_m$ .

Операции над функциями называют операторами. Отметим, что они обладают тем свойством, что, применяя их к функциям, вычислимым в интуитивном смысле, получаем функции, также вычислимые в интуитивном смысле.

Оператором суперпозиции $F_m^n$ называется подстановка в функцию от $m$ переменных $m$ функций каждая из которых зависит от $n$ одних и тех же переменных. Суперпозиция дает новую функцию уже от $n$ переменных.

$f=F_m^n(h,g_1,...,g_m)$ где $f(x_1,...,x_n)= h(g_1(x_1,...,x_n),...,g_m(x_1,...,x_n))$

Оператор примитивной рекурсии $R_n$ определяет $(n+1)$ -местную функцию f через $n$ -местную функцию $g$ и $(n+2)$ -местную функцию $h$ следующим образом:

$f=R_n(g,h)$ , где
$f(x_1,...,x_n,0)=g(x_1,...,x_n)$ ;
$f(x_1,...,x_n,y+1)=h(x_1,...,x_n,y,f(x_1,...,x_n,y))$

Существенным в операторе примитивной рекурсии является то, что независимо от числа переменных в $f$ рекурсия ведется только по одной переменной y и требуется понадобится $y+1$ вычисление, так как остальные $n$ переменных $x_1, ..., x_n$ зафиксированы и играют роль параметров.

В случае, когда n=0, определение $f$ принимает более простой вид:
$f(0)=C$ ;
$f(y+1)=h(y,f(y))$

Функция называется примитивно-рекурсивной, если она может быть получена из нуль-функции $0(x)$ , функции следования $S(x)$ и функции проекции $I_m^n$ с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

Сложение $p(x,y)=x+y$ примитивно-рекурсивно.

$p(x,0)=x=I_1^1(x)$ ;
$p(x,y+1)=p(x,y)+1=S(p(x,y))$

тогда $p(x,y)=R_1(I_1^1, h)$ , где $h(x,y,z)=S(z)$

Для данной функции $f(x,y)$ и фиксированного $x$ найдем наименьшее из тех значений $y$ , при которых функция $f(x,y)=0$ . Так как результат решения задачи зависит от $x$ , то наименьшее значение $y$ , при котором функция $f(x,y)=0$ есть функция от $x$ . Принято обозначение $phi(x)=mu \ y [f(x,y)=0]$ которое читается как: «наименьшее $y$ такое, что $f(x,y)=0$ ».

Аналогично определяется функция многих переменных: $phi(x_1,...,x_n)=mu \ y [f(x_1,...,x_n,y)=0]$ .

Переход от функции $f(x_1,...,x_n,y)$ к функции $phi(x_1,...,x_n)$ принято называть применением $mu$ -оператора.

Вычислим $f(x_1,...,x_n,y)$ . Если это значение равно 0, то $phi(x_1,...,x_n)=0$ Иначе рассматриваем значение $f(x_1,...,x_n,1)$ и так далее.

Если для всех $y$ $f(x_1,...,x_n,y)!=0$ , то значение $phi(x_1,...,x_n)$ считаем неопределенным.

С помощью $mu$ -оператора можно определить разность $m(x,y)=x-y$ : $m(x,y)=mu \ z[p(y,z)=x]$

Итак, из простейших функций с помощью операторов суперпозиции и примитивной рекурсии может быть получено огромное разнообразие функций. При этом все примитивно-рекурсивные функции всюду определены, так как операторы $F$ и $R$ это свойство сохраняют.

Функции, которые могут быть получены из простейших функций помощью конечного числа применений операций суперпозиции, примитивной рекурсии и $mu$ -оператора называются частично рекурсивными.

Частично-рекурсивная функция называется общерекурсивной, если она всюду определена. Не всякая общерекурсивная функция является примитивно-рекурсивной, хотя частично рекурсивные функции включают в себя примитивно-рекурсивные.

Для любой частично рекурсивной функции можно указать алгоритм вычисления ее значений, т. е. все частично рекурсивные функции суть вычислимые функции.

Можно проверить, что выполняется свойства детерминированности, результативности (если функция не определена, то процесс вычислений не останавливается) и универсальности.

Понятие частично-рекурсивной функции является исчерпывающей формализацией понятия вычислимой функции. Это обстоятельство выражено в виде тезиса Чёрча: всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивна.