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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основные определения)
м (rollbackEdits.php mass rollback)
 
(не показано 40 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
== Основные определения ==
 
== Основные определения ==
Рассмотрим следующее правило преобразования функций:
 
 
* Рассмотрим <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=
 
|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>.  
+
'''Частично рекурсивными''' (англ. ''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 \leqslant n </tex>.  
 
 
 
}}
 
}}
Заметим что частично рекурсивная функция может быть неопределена для некоторых значений аргументов.
+
Заметим что частично рекурсивная функция может быть не определена для некоторых значений аргументов.
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Общерекурсивными''' называют всюду определенные частично рекурсивные функции.
+
'''Общерекурсивными''' (англ. ''general recursive'') называют всюду определенные частично рекурсивные функции.
 
}}
 
}}
 +
Любая [[примитивно рекурсивные функции|примитивно рекурсивная функция]] является общерекурсивной. Поэтому и для частично рекурсивных функций можно считать что у них в качестве аргумента и результата могут быть списки из натуральных чисел.
  
Любая [[примитивно рекурсивные функции|примитивно рекурсивная функция]] является общерекурсивной. Поэтому и для частично рекурсивных функций можно считать что у них в качестве аргумента и результата могут быть списки из натуральных чисел.
+
== Вычислимые и частично рекурсивные функции ==
=== Вычислимые и частично рекурсивные функции ===
+
{{Теорема
 +
|statement= Множества [[Вычислимые функции|вычислимых]] и частично рекурсивных функций совпадают.
 +
|proof=
 +
Программа вычисляющая частично рекурсивную функцию легко пишется на любом языке программирования. Поэтому нам достаточно показать что любая вычислимая функция примитивно рекурсивная. Функции <tex> IN </tex>, <tex> OUT </tex>, <tex> N </tex>, и как представляется состояние [[Машина Тьюринга|машины Тюринга]] описано в доказательстве [[Примитивно рекурсивные функции#Теорема о примитивной рекурсивности вычислимых функций|теоремы о примитивной рекурсивности вычислимых функций]].
 +
Функция <tex> \mathrm{T([L,R,S,C])}</tex> возвращает минимальное число шагов за которое программа вычисляющая нашу функцию попадет в состояние <tex> \mathrm{Accepted} </tex>. Покажем что она частично рекурсивная. <tex> \mathrm{T([L,R,S,C]) = \mu t (p_2(N([L,R,S,C],t)) = Accepted)} </tex>, где <tex> p_i </tex> — взятие <tex>i</tex>-того элемента списка. Операции сравнения здесь реализованы также как и примитивно рекурсивных функциях,но если равенство выполняется то функция проверки на равенство возвращает <tex> 0 </tex>, иначе <tex> 1 </tex>.
 +
В итоге <tex> \mathrm{F(args) = OUT(N(IN(args), T(IN(args)))} </tex> — частично рекурсивная функция.
 +
}}
 +
Из этой теоремы и неразрешимости языка программ завершающихся при любом входе, следует алгоритмическая неразрешимость проврк,и частично рекурсивной функции на общерекурсивность.
 +
 
 +
== Связь между общерекурсивными и примитивно рекурсивными функциями ==
 +
{{Теорема
 +
|statement= Существует общерекурсивная функция которая не является примитивно рекурсивной.
 +
|proof=
 +
Каждой примитивно рекурсивной функцией соответствует ее описание, не обязательно единственное. Оно состоит из последовательных определений функций через предыдущие заканчивая нашей функцией. При этом стоит заметить, что в описании не будет перекрестной рекурсии, так как по определению примитивно рекурсивной функции, она должна быть получена из базовых примитивов за конечное число шагов.
 +
 
 +
Множество описаний одноместных примитивно рекурсивных функций разрешимо, значит все описания можно занумеровать (описания могут содержать и <tex> n </tex> местные функции в качестве промежуточных). По описанию примитивно рекурсивной функции и значением аргумента ее можно вычислить передав функцию вместе с аргументом в соответствующий интерпретатор.
 +
Определим функцию <tex> U(n,x) </tex> равную значению функции полученной из <tex> n </tex>-того описания, в точке <tex> x </tex>. В силу всюду определенности примитивно рекурсивных функций <tex> U(n,x) </tex> {{---}} вычислимая всюду определенная функция, а значит по предыдущей теореме общерекурсивная.  <tex> d(n) = U(n,n)+1 </tex> тоже общерекурсивная функция, но она отличается от каждой одноместной примитивно рекурсивной функциии. }}
 +
 
 +
==См. также ==
 +
* [[Лямбда-исчисление]]
 +
* [[Примитивно рекурсивные функции]]
 +
 
 +
== Источники информации ==
 +
* Н. К. Верещагин, А. Шень. [http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 4-е изд., испр., М.: МЦНМО, 2012]
 +
* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8) Рекурсивные функции на википедии]
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Вычислительные формализмы]]

Текущая версия на 19:10, 4 сентября 2022

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

Определение:
Частично рекурсивными (англ. partial recursive) называют функции, которые можно получить с помощью правил минимизации, подстановки и рекурсии из константной функции [math] \textbf 0 [/math], функции [math] I(x) = x + 1, [/math] и набора функций [math] P_{n,k}(x_1,\ldots,x_n) = x_k,[/math] где [math] k \leqslant n [/math].

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


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

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

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

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

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

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

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

Связь между общерекурсивными и примитивно рекурсивными функциями

Теорема:
Существует общерекурсивная функция которая не является примитивно рекурсивной.
Доказательство:
[math]\triangleright[/math]

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

Множество описаний одноместных примитивно рекурсивных функций разрешимо, значит все описания можно занумеровать (описания могут содержать и [math] n [/math] местные функции в качестве промежуточных). По описанию примитивно рекурсивной функции и значением аргумента ее можно вычислить передав функцию вместе с аргументом в соответствующий интерпретатор.

Определим функцию [math] U(n,x) [/math] равную значению функции полученной из [math] n [/math]-того описания, в точке [math] x [/math]. В силу всюду определенности примитивно рекурсивных функций [math] U(n,x) [/math] — вычислимая всюду определенная функция, а значит по предыдущей теореме общерекурсивная. [math] d(n) = U(n,n)+1 [/math] тоже общерекурсивная функция, но она отличается от каждой одноместной примитивно рекурсивной функциии.
[math]\triangleleft[/math]

См. также

Источники информации