Рекурсивные функции

Эта статья находится в разработке!

Все рассматриваемые здесь функции действуют из подмножества [math] \mathbb {N}^t [/math] в [math] \mathbb {N} [/math], где [math] t [/math] - любое целое неотрицательное число.

Примитивно рекурсивные функции

Основные определения

Рассмотрим следующие правила преобразования функций.

• Рассмотрим [math] k [/math]-местную функцию [math] f(x_1,\ldots,x_k) [/math] и [math] k [/math] [math]n [/math]-местных функций [math] g_i(x_1,x_2,\ldots,x_n) [/math]. Тогда после преобразования у нас появится [math] n [/math] - местная функция [math] F = f(g_1(x_1,\ldots,x_n),\ldots, g_k(x_1,\ldots,x_n)) [/math].

Это правило называется правилом подстановки

• Рассмотрим [math] k [/math]-местную функцию [math] f [/math] и [math] k + 2 [/math]-местную функцию [math] h [/math]. Тогда после преобразования у нас будет [math] k+1 [/math] -местная функция [math] g [/math], которая определена следующим образом:

[math]g(x_1,\ldots,x_n,0)=f(x_1,\ldots,x_n)[/math]

[math]g(x_1,\ldots,x_n,y+1)=h(x_1,\ldots,x_n,y,h(x_1,\ldots, x_n,y))[/math]

Это правило называется правилом рекурсии.

Определение:

Примитивно рекурсивными называют функции, которые можно получить с помощью правил подстановки и рекурсии из константы ноль, функции [math] f(x) = x + 1, [/math] и набора функций [math] f_{n,k}(x_1,\ldots,x_n) = x_k,[/math] где [math] k \le n [/math]