Изменения

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

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

|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> тоже общерекурсивная функция, но она отличается от каждой одноместной примитивно рекурсивной функциии. }}