===Примитивно рекурсивные функции===
==== Основные определения ====
Рассмотрим следующие правила преобразования функций:
===== Подстановка =====
Рассмотрим <tex> k </tex>-местную функцию <tex> \mathrm{f}(x_1,\ldots,x_k) </tex> и <tex> k </tex> <tex>n </tex>-местных функций <tex> \mathrm{g_i}(x_1,x_2,\ldots,x_n) </tex>. Тогда после преобразования у нас появится <tex> n </tex>-местная функция <tex>\mathrm{F} </tex>, такая что:
<tex> \mathrm{F} = \mathrm{f}(\mathrm{g_1}(x_1,\ldots,x_n),\ldots, \mathrm{g_k}(x_1,\ldots,x_n)) </tex>.
===== Рекурсия =====
Рассмотрим <tex> k </tex>-местную функцию <tex> \mathrm{f} </tex> и <tex> (k + 2) </tex>-местную функцию <tex> \mathrm{h} </tex>. Тогда после преобразования у нас будет <tex> (k+1) </tex>-местная функция <tex> \mathrm{g} </tex>, которая определена следующим образом:
<tex>\mathrm{g}(x_1,\ldots,x_n,0)=\mathrm{f}(x_1,\ldots,x_n)</tex>
<tex>\mathrm{g}(x_1,\ldots,x_n,y+1)=\mathrm{h}(x_1,\ldots,x_n,y,\mathrm{g}(x_1,\ldots, x_n,y))</tex>
При этом будем говорить, что рекурсия запускается по аргументу <tex> y </tex>.
{{Определение
