54
правки
Изменения
Добавил имена авторов теорем
{{Теорема
|id=th1
|author=Клини|about=О о рекурсии/ ''Kleene's recursion theorem''
|statement= Пусть <tex>V(n, x)</tex> {{---}} вычислимая функция. Тогда найдётся такая вычислимая <tex>p</tex>, что <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex>.
|proof=
{{Теорема
|id=th2
|author=Роджерс|about=о неподвижной точке, Клини/ ''Rogers' fixed-point theorem''
|statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]], <tex>h</tex> {{---}} всюду определённая [[Вычислимые_функции|вычислимая функция]]. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>.
Другими словами: нельзя найти алгоритма, преобразующего про-
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999 - С. 176
* ''Kleene, Stephen'' '''On notation for ordinal numbers''' - The Journal of Symbolic Logic, 1938 - С. 150-155
*
