Изменения
→Основные определения
{{Определение
|definition=
'''Частично рекурсивными''' (англ. ''partial recursive'') называют функции, которые можно получить с помощью правил [[Примитивно рекурсивные функции | минимизации, подстановки и рекурсии]] из константной функции <tex> \textbf 0 </tex>, функции <tex> I(x) = x + 1, </tex> и набора функций <tex> P_{n,k}(x_1,\ldots,x_n) = x_k,</tex> где <tex> k \le n </tex>.
}}
Заметим что частично рекурсивная функция может быть не определена для некоторых значений аргументов.
{{Определение
|definition=
'''Общерекурсивными''' (англ. ''general recursive'') называют всюду определенные частично рекурсивные функции.
}}
Любая [[примитивно рекурсивные функции|примитивно рекурсивная функция]] является общерекурсивной. Поэтому и для частично рекурсивных функций можно считать что у них в качестве аргумента и результата могут быть списки из натуральных чисел.
