Частично рекурсивные функции — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Основные определения == Рассмотрим следующее правило преобразования функций: * Рассмо...»)
(нет различий)

Версия 02:20, 20 января 2013

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

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

  • Рассмотрим [math] k+1 [/math]-местную функцию [math] f(x_1,\ldots,x_k,y) [/math]. Тогда после преобразования у нас появится [math] k [/math] - местная функция [math] g(x_1,\ldots,x_k) = [/math] минимальное [math] y [/math] при котором [math] f(x_1,\ldots,x_k,y) =0 [/math].
Это правило называется правилом минимизации и часто для него используют обозначения [math] g(x_1,\ldots,x_k) = \mu y (f(x_1,\ldots,x_k,y) = 0) {{Определение |definition= '''Частично рекурсивными''' называют функции, которые можно получить с помощью правил минимизации, подстановки и рекурсии из константной функции \lt tex\gt \textbf 0 [/math], функции [math] I(x) = x + 1, [/math] и набора функций [math] P_{n,k}(x_1,\ldots,x_n) = x_k,[/math] где [math] k \le n [/math].

}}