Теорема о рекурсии — различия между версиями
м |
Grechko (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
|id=th1 | |id=th1 | ||
|about=О рекурсии | |about=О рекурсии | ||
| − | |statement= | + | |statement= Пусть <tex>U</tex> - [[Диагональный_метод|универсальная функция]], <tex>h</tex> - всюду определенная [[Вычислимые_функции|вычислимая функция]]. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex> |
|proof= | |proof= | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
| − | |||
| − | |||
==Источники== | ==Источники== | ||
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999 | Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999 | ||
Версия 09:27, 29 декабря 2011
Теорема о рекурсии
Говоря неформально, теорема о рекурсии позволяет утверждать, что любая программа может использовать внутри себя свой исходный код (номер), который ей передали в качестве параметра.
| Теорема (О рекурсии): |
Пусть - универсальная функция, - всюду определенная вычислимая функция. Тогда найдется такое , что |
Источники
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
