Изменения
→Примитивно рекурсивные функции
* Рассмотрим <tex> k </tex>-местную функцию <tex> f </tex> и <tex> k + 2 </tex>-местную функцию <tex> h </tex>. Тогда после преобразования у нас будет <tex> k+1 </tex> -местная функция <tex> g </tex>, которая определена следующим образом:
: <tex>g(x_1,\ldots,x_n,0)=f(x_1,\ldots,x_n)</tex>
: <tex>g(x_1,\ldots,x_n,y+1)=h(x_1,\ldots,x_n,y,hg(x_1,\ldots, x_n,y))</tex>
: Это правило называется правилом рекурсии.
{{Определение
|definition=
'''Примитивно рекурсивными''' называют функции, которые можно получить с помощью правил подстановки и рекурсии из константы нольконстантной функции <tex> \textbf 0 </tex>, функции <tex> fI(x) = x + 1, </tex> и набора функций <tex> f_P_{n,k}(x_1,\ldots,x_n) = x_k,</tex> где <tex> k \le n </tex>
}}
=== Арифметические операции на примитивно рекурсивных функциях ===
==== Сложения ====
<tex> sum(x,0) = P_{1,1}(x) </tex>
<tex> sum(x,y+1) = h(x,y,sum(x,y)) </tex> , где <tex> h(x,y,z)=I(P_{3,1}(x,y,z)) </tex>
==== Умножения ====
<tex> prod(x,0) = \textbf 0 </tex>
<tex> prod(x,y) = h(x,y,prod(x,y)) </tex>, где <tex> h(x,y,z)=sum(P_{3,1}(x,y,z),P_{3,3}(x,y,z))
