Рекурсивная функция (теория вычислимости): различия между версиями

м
Удаление принудительных пробелов в формулах по ВП:РДБ.
м (оформление)
м (Удаление принудительных пробелов в формулах по ВП:РДБ.)
Укажем на ряд широко известных арифметических функций, являющихся примитивно рекурсивными.
 
* Функция ''Сложения'' двух натуральных чисел (<math>Sum(a,\;b)=a+b</math>) может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям <math>I_1^1</math> и <math>F\,\!</math>, вторая из которых получается подстановкой основной функции <math>I_3^3</math> в основную функцию <math>S</math>:
: <math>Sum(x,\;0)=I_1^1(x)</math>;
: <math>Sum(x,\;y+1)=F(x,\;y,\;Sum(x,\;y))</math>;