Изменения
→Вычислимые и частично рекурсивные функции
Любая [[примитивно рекурсивные функции|примитивно рекурсивная функция]] является общерекурсивной. Поэтому и для частично рекурсивных функций можно считать что у них в качестве аргумента и результата могут быть списки из натуральных чисел.
== Вычислимые и частично рекурсивные функции ==
{{Теорема
|statement= Множества вычислимых и частично рекурсивных функций совпадают.
|proof=
Программа вычисляющая частично рекурсивную функцию легко пишется на любом удобном для читателя языке программирования. Поэтому нам достаточно показать что любая вычислимая функция примитивно рекурсивная. Функции <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> - того элемента списка. Операции сравнения здесь реализованы также как и примитивно рекурсивных функциях.
В итоге F(args) = OUT(N(IN(args),T(IN(args))) - частично рекурсивная функция.
}}
