Изменения
→Основные определения
{{Определение
|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>.
}}
Заметим что частично рекурсивная функция может быть не определена для некоторых значений аргументов.
Программа вычисляющая частично рекурсивную функцию легко пишется на любом языке программирования. Поэтому нам достаточно показать что любая вычислимая функция примитивно рекурсивная. Функции <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> - — частично рекурсивная функция.
}}
Из этой теоремы и неразрешимости языка программ завершающихся при любом входе, следует алгоритмическая неразрешимость проврк,и частично рекурсивной функции на общерекурсивность.
