313
правок
Изменения
→Рекурсивные функции
Если <tex>\mathrm{f}: \mathbb{N}^{n+1} \rightarrow \mathbb{N}</tex>, то <tex>\mu \langle{}\mathrm{f}\rangle: \mathbb{N}^n \rightarrow \mathbb{N}</tex>, при этом <tex>\mu \langle{}\mathrm{f}\rangle (x_1,...x_n)</tex> — такое минимальное число <tex>y</tex>, что <tex>\mathrm{f}(x_1,...x_n,y) = 0</tex>. Если такого <tex>y</tex> нет, результат данного примитива неопределен.
</ol>
{{Определение|definition= Если некоторая функция <tex>\mathbb{N}^{n} \rightarrow \mathbb{N}</tex> может быть задана с помощью данных примитивов, то она называется '''рекурсивной'''. Если некоторую функцию можно собрать исключительно из первых 5 примитивов (то есть без использования операции минимизации), то такая функция называется примитивно-рекурсивной.}}
===Примитивно рекурсивные функции===
