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

м
откат правок 95.25.160.191 (обс) к версии 188.239.29.200
м (откат правок 95.25.160.191 (обс) к версии 188.239.29.200)
* ''Нулевая функция'' <math>O</math> — функция без аргументов, всегда возвращающая [[0 (число)|0]].
* ''Функция следования'' <math>S</math> одного переменного, сопоставляющая любому натуральному числу <math>x</math> непосредственно следующее за ним натуральное число <math>x+1</math>.
* Функции <math>I_nI_m^mn</math>, где <math>0<m\leqslant n</math>, от n переменных, сопоставляющие любому упорядоченному набору <math>x_1,\dots, x_n</math> натуральных чисел число <math>x_m</math> из этого набора.
 
Операторы подстановки и примитивной рекурсии определяются следующим образом: