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

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

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

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

Определения

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

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

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