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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вычислимые и частично рекурсивные функции)
(Вычислимые и частично рекурсивные функции)
Строка 23: Строка 23:
 
|proof=
 
|proof=
 
Программа вычисляющая частично рекурсивную функцию легко пишется на любом удобном для читателя языке программирования. Поэтому нам достаточно показать что любая вычислимая функция примитивно рекурсивная. Функции <tex> IN </tex>, <tex> OUT </tex>, <tex> N </tex>, и как представляется состояние машины Тюринга описано в доказательстве [[Рекурсивные функции|теоремы о примитивной рекурсивности вычислимых функций]].  
 
Программа вычисляющая частично рекурсивную функцию легко пишется на любом удобном для читателя языке программирования. Поэтому нам достаточно показать что любая вычислимая функция примитивно рекурсивная. Функции <tex> IN </tex>, <tex> OUT </tex>, <tex> N </tex>, и как представляется состояние машины Тюринга описано в доказательстве [[Рекурсивные функции|теоремы о примитивной рекурсивности вычислимых функций]].  
Функция <tex> T([L,R,S,C]) возвращает минимальное число шагов за которое программа вычисляющая нашу функцию попадет в состояние <tex> Accepted </tex>. Покажем что она частично рекурсивная. Т([L,R,S,C] = /mu t (p_2(N([L,R,S,C],t)) = Accepted), где p_i - взятие <tex> i </tex> - того элемента списка. Операции сравнения здесь реализованы также как и примитивно рекурсивных функциях.  
+
Функция <tex> T([L,R,S,C]) </tex> возвращает минимальное число шагов за которое программа вычисляющая нашу функцию попадет в состояние <tex> Accepted </tex>. Покажем что она частично рекурсивная. Т([L,R,S,C] = /mu t (p_2(N([L,R,S,C],t)) = Accepted), где p_i - взятие <tex> i </tex> - того элемента списка. Операции сравнения здесь реализованы также как и примитивно рекурсивных функциях.  
 
В итоге F(args) = OUT(N(IN(args),T(IN(args))) - частично рекурсивная функция.
 
В итоге F(args) = OUT(N(IN(args),T(IN(args))) - частично рекурсивная функция.
 
}}
 
}}

Версия 03:14, 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].

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


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


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

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

Теорема:
Множества вычислимых и частично рекурсивных функций совпадают.
Доказательство:
[math]\triangleright[/math]

Программа вычисляющая частично рекурсивную функцию легко пишется на любом удобном для читателя языке программирования. Поэтому нам достаточно показать что любая вычислимая функция примитивно рекурсивная. Функции [math] IN [/math], [math] OUT [/math], [math] N [/math], и как представляется состояние машины Тюринга описано в доказательстве теоремы о примитивной рекурсивности вычислимых функций. Функция [math] T([L,R,S,C]) [/math] возвращает минимальное число шагов за которое программа вычисляющая нашу функцию попадет в состояние [math] Accepted [/math]. Покажем что она частично рекурсивная. Т([L,R,S,C] = /mu t (p_2(N([L,R,S,C],t)) = Accepted), где p_i - взятие [math] i [/math] - того элемента списка. Операции сравнения здесь реализованы также как и примитивно рекурсивных функциях.

В итоге F(args) = OUT(N(IN(args),T(IN(args))) - частично рекурсивная функция.
[math]\triangleleft[/math]