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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основные определения)
(Основные определения)
Строка 7: Строка 7:
 
{{Определение
 
{{Определение
 
|definition=
 
|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> \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>.  
  
 
}}
 
}}
Строка 18: Строка 18:
  
 
Любая [[примитивно рекурсивные функции|примитивно рекурсивная функция]] является общерекурсивной. Поэтому и для частично рекурсивных функций можно считать что у них в качестве аргумента и результата могут быть списки из натуральных чисел.
 
Любая [[примитивно рекурсивные функции|примитивно рекурсивная функция]] является общерекурсивной. Поэтому и для частично рекурсивных функций можно считать что у них в качестве аргумента и результата могут быть списки из натуральных чисел.
 +
=== Вычислимые и частично рекурсивные функции ===

Версия 02:36, 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) [/math]


Определение:
Частично рекурсивными называют функции, которые можно получить с помощью правил минимизации, подстановки и рекурсии из константной функции [math] \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].

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


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


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

Вычислимые и частично рекурсивные функции