Изменения
→Основные определения
{{Определение
|definition=
'''Частично рекурсивными''' (англ. ''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 \le leqslant n </tex>.
}}
Заметим что частично рекурсивная функция может быть не определена для некоторых значений аргументов.
== Вычислимые и частично рекурсивные функции ==
{{Теорема
|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> - — частично рекурсивная функция.
}}
Из этой теоремы и неразрешимости языка программ завершающихся при любом входе, следует алгоритмическая неразрешимость проврк,и частично рекурсивной функции на общерекурсивность.
