Изменения

# <tex>\mathrm{Z}: \mathrm{N } \rightarrow \mathrm{N}</tex>, <tex>\mathrm{Z}(x) = 0</tex># <tex>\mathrm{N}: \mathrm{N } \rightarrow \mathrm{N}</tex>, <tex>\mathrm{N}(x) = x'</tex># Проекция. <tex>\mathrm{U^n_i}: \mathrm{N^n } \rightarrow \mathrm{N}</tex>, <tex>\mathrm{U^n_i } (x_1, ... x_n) = x_i</tex># Подстановка. Если <tex>\mathrm{f}: \mathrm{N^n } \rightarrow \mathrm{N}</tex> и <tex>\mathrm{g_1}, ... \mathrm{g_n}: \mathrm{N^m } \rightarrow \mathrm{N}</tex>, то <tex>\mathrm{S}\langle{}\mathrm{f},\mathrm{g_1},...\mathrm{g_n}\rangle: \mathrm{N^m } \rightarrow \mathrm{N}</tex>. При этом <tex>\mathrm{S}\langle{}\mathrm{f},\mathrm{g_1},...\mathrm{g_n}\rangle (x_1,...x_m) = \mathrm{f}(\mathrm{g_1}(x_1,...x_m), ... \mathrm{g_n}(x_1,...x_m))</tex># Примитивная рекурсия. Если <tex>\mathrm{f}: \mathrm{N^n } \rightarrow \mathrm{N}</tex> и <tex>\mathrm{g}: \mathrm{N^{n+2}} \rightarrow \mathrm{N}</tex>, то <tex>\mathrm{R}\langle{}\mathrm{f},\mathrm{g}\rangle: \mathrm{N^{n+1}} \rightarrow \mathrm{N}</tex>, при этом <tex>\mathrm{R}\langle{}\mathrm{f},\mathrm{g}\rangle (x_1,...x_n,y) = \left\{\begin{array}{ll} \mathrm{f}(x_1,...x_n) & , y = 0\\ \mathrm{g}(x_1,...x_n,y-1,\mathrm{R}\langle{}\mathrm{f},\mathrm{g}\rangle(x_1,...x_n,y-1)) &, y > 0

# Минимизация. Если <tex>\mathrm{f}: \mathrm{N^{n+1}} \rightarrow \mathrm{N}</tex>, то <tex>\mu \langle{}\mathrm{f}\rangle: \mathrm{N^n } \rightarrow \mathrm{N}</tex>, при этом <tex>\mu \langle{}\mathrm{f}\rangle (x_1,...x_n)</tex> &mdash; такое минимальное число <tex>y</tex>, что <tex>\mathrm{f}(x_1,...x_n,y) = 0</tex>. Если такого <tex>y</tex> нет, результат данного примитива неопределен.

Если некоторая функция <tex>\mathrm{N^n } \rightarrow \mathrm{N}</tex> может быть задана с помощью данных примитивов, то она называется рекурсивной. Если некоторую функцию можно собрать исключительно из первых 5 примитивов (то есть без использования операции минимизации), то такая функция называется примитивно-рекурсивной.