Изменения

== Основные определения ==

Рассмотрим следующее правило преобразования функций:

* Рассмотрим <tex> k+1 </tex>-местную функцию <tex> f(x_1,\ldots,x_k,y) </tex>. Тогда после преобразования у нас появится <tex> k </tex> - местная функция <tex> g(x_1,\ldots,x_k) = </tex> минимальное <tex> y </tex> при котором <tex> f(x_1,\ldots,x_k,y) = 0 </tex>.

: Это правило называется правилом минимизации и часто для него используют обозначения <tex> g(x_1,\ldots,x_k) = \mu y (f(x_1,\ldots,x_k,y) = 0) </tex>

{{Определение

|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>.

}}

Заметим что частично рекурсивная функция может быть неопределена для некоторых значений аргументов.

'''Общерекурсивными''' (''general recursive'') называют всюду определенные частично рекурсивные функции.

}}

Любая [[примитивно рекурсивные функции|примитивно рекурсивная функция]] является общерекурсивной. Поэтому и для частично рекурсивных функций можно считать что у них в качестве аргумента и результата могут быть списки из натуральных чисел.