Просмотр исходного текста страницы Формально об алгоритмах. Вычислительные модели/Задачи/Теорема о неподвижной точке

<latex>
Зафиксируем некоторую нумерацию алгоритмов. Доказать, что для любой полной вычислимой функции $f$ существует такое $n$, что алгоритмы с номерами $n$ и $f(n)$ на одном и том же входе либо дают одинаковый ответ, либо оба зацикливаются.
</latex>

[[Category:Решенные задачи]]