Проблема остановки

---

Проблема остановки (англ. Halting problem) — это одна из проблем в теории алгоритмов^[1], которая может неформально быть поставлена в виде:

Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Другими словами, не существует общего алгоритма решения этой проблемы.^[2]

Проблема остановки занимает центральное место в теории вычислимости, поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путём.

Для многих других задач^{[каких?]} можно доказать их алгоритмическую неразрешимость, попытавшись свести их к проблеме остановки. Это делается по схеме "от противного": пусть есть некая задача, для которой требуется установить её неразрешимость. Тогда, предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует алгоритма решения проблемы остановки. А значит, предположение было неверным и исходная задача также неразрешима.

Рассмотрим множество ${\displaystyle S}$ алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество ${\displaystyle S}$ по алфавиту. При этом каждый алгоритм получит свой порядковый номер; более того существует алгоритм, который по номеру элемента ${\displaystyle S}$ восстанавливает его код в выбранном языке программирования. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел ${\displaystyle (N,X)}$, и:

---