Частично рекурсивные и рекурсивные функции. Функция Аккермана.

Функция называется частично рекурсивной, если она получается из простейших, путем конечного числа применения операций подстановки примитивной рекурсии и минимизации.

http://matinf.vsgao.com/simulator/rf.html - прога

Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция $f(n)$ числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения $f(n)$ на основе значений $f(n-1), f(n-2),\ldots$ , подобно рассуждению по индукции. Чтобы вычисление завершалось для любого $n$ , необходимо, чтобы для некоторых $n$ функция была определена нерекурсивно (например, для $n=0, 1$ ).

Пример рекурсивной функции, дающей n-ое число Фибоначчи:

$F = \begin{cases} F(0)=1; \\ F(1) = 1; \\ F(n) = F(n-1) + F(n-2),\quad n > 1. \end{cases}$

Руководствуясь этой записью, мы можем вычислить $F(n)$ для любого натурального n за конечное число шагов. Правда, по пути придется дополнительно вычислить значения $F(n-1),F(n-2),\ldots,F(2)$ .

Функция Аккермана — простой пример вычислимой функции, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается . Эта функция растёт очень быстро, например, число настолько велико, что количество цифр в записи количества цифр этого числа многократно превосходит количество атомов в наблюдаемой части вселенной.

Функция Аккермана определяется рекурсивно для неотрицательных целых чисел $m$ и $n$ следующим образом:

$A\left(m,n\right)=\begin{cases}n+1&m=0\\A\left(m-1,1\right)&m>0,n=0\\A\left(m-1,A\left(m,n-1\right)\right)&m>0,n>0\end{cases}$

Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение $m$ , или значение $m$ сохраняется, но уменьшается значение $n$ . Это означает, что каждый раз пара $\left(m,n\right)$ уменьшается с точки зрения лексикографического порядка, значит, значение $m$ в итоге достигнет нуля: для одного значение $m$ существует конечное число возможных значений $n$ (так как первый вызов с данным $m$ был произведён с каким-то определённым значением $n$ , а в дальнейшем, если значение $m$ сохраняется, значение $n$ может только уменьшаться), а количество возможных значений $m$ , в свою очередь, тоже конечно. Однако, при уменьшении $m$ значение, на которое увеличивается $n$ , неограничено и обычно очень велико.

Таблица значений


$n$ \ $m$	$0$	$1$	$2$	$3$	$4$	$5$	$m$
$0$	$1$	$2$	$3$	$5$	$13$	$65533$	$\operatorname{hyper}\left(2,m,3\right)-3$
$1$	$2$	$3$	$5$	$13$	$65533$	$\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}-3$	$\operatorname{hyper}\left(2,m,4\right)-3$
$2$	$3$	$4$	$7$	$29$	$2^{65536}-3$	$\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}-3$	$\operatorname{hyper}\left(2,m,5\right)-3$
$3$	$4$	$5$	$9$	$61$	$2^{2^{65536}}-3$	$A\left(4,\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}-3\right)$	$\operatorname{hyper}\left(2,m,6\right)-3$
$4$	$5$	$6$	$11$	$125$	$2^{2^{2^{65536}}}-3$	$A\left(4,A\left(5,3\right)\right)$	$\operatorname{hyper}\left(2,m,7\right)-3$
$5$	$6$	$7$	$13$	$253$	$2^{2^{2^{2^{65536}}}}-3$	$A\left(4,A\left(5,4\right)\right)$	$\operatorname{hyper}\left(2,m,8\right)-3$
$n$	$n+1$	$n+2$	$2n+3$	$2^{n+3}-3$	$\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{n+3}-3$	$\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underset{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}{\vdots}}-3$ (всего $n$ блоков $2^{2^{\cdot^{\cdot^{\cdot^2}}}}$ )	$\operatorname{hyper}\left(2,m,n+3\right)-3$

Обратная функция

Так как функция $f\left(n\right)=A\left(n,n\right)$ растёт очень быстро, обратная функция $\overset{-1}{f}\left(n\right)=\min\left\lbrace k\geq 1:A\left(k,k\right)\geq n\right\rbrace$ растёт очень медленно. Эта функция встречается при исследовании сложности некоторых алгоритмов. Так как для всех практически встречающихся чисел значение этой функции меньше пяти, при анализе асимптотики алгоритмов можно принять её за константу.