Изменения

Перейти к: навигация, поиск

Частично рекурсивные функции

365 байт добавлено, 16:33, 15 января 2017
Связь между общерекурсивными и примитивно рекурсивными функциями
|statement= Существует общерекурсивная функция которая не является примитивно рекурсивной.
|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> тоже общерекурсивная функция, но она отличается от каждой одноместной примитивно рекурсивной функциии. }}
== Ссылки ==
* Н. К. Верещагин, А. Шень. [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) Рекурсивные функции на википедии]
Анонимный участник

Навигация