Изменения
Новая страница: «== Основные определения == Рассмотрим следующее правило преобразования функций: * Рассмо...»
== Основные определения ==
Рассмотрим следующее правило преобразования функций:
* Рассмотрим <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)
{{Определение
|definition=
'''Частично рекурсивными''' называют функции, которые можно получить с помощью правил минимизации, подстановки и рекурсии из константной функции <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>.
}}
Рассмотрим следующее правило преобразования функций:
* Рассмотрим <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)
{{Определение
|definition=
'''Частично рекурсивными''' называют функции, которые можно получить с помощью правил минимизации, подстановки и рекурсии из константной функции <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>.
}}
