Изменения

Множество описаний одноместных примитивно рекурсивных функций разрешимо, значит все описания можно занумеровать(описания могут содержать и <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) Рекурсивные функции на википедии]