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

Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки.

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

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

В терминах функций проблему можно доступно описать следующим образом:

Для любой функции F(G, start_state), которая может определять, останавливается ли другая функция, всегда можно написать такую функцию G(start_state), при передаче которой в F результат выполнения будет противоположен тому, который предсказывает F.

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

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

• останавливается и возвращает 1, если алгоритм с номером ${\displaystyle N}$ не останавливается, получив на вход ${\displaystyle X}$
• не останавливается в противном случае (если алгоритм с номером ${\displaystyle N}$ останавливается, получив на вход ${\displaystyle X}$).

Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?

Теорема. Анализатора не существует.

Докажем это от противного. Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число ${\displaystyle N}$, передает пару аргументов ${\displaystyle (N,N)}$ Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не останавливается алгоритм с номером ${\displaystyle N}$, получив на вход число ${\displaystyle N}$. Пусть ${\displaystyle K}$ — это порядковый номер Диагонализатора в множестве ${\displaystyle S}$. Запустим Диагонализатор, передав ему это число ${\displaystyle K}$. Диагонализатор остановится в том и только том случае, если алгоритм с номером ${\displaystyle K}$ (то есть, он сам) не останавливается, получив на вход число ${\displaystyle K}$ (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатора не существует, что и требовалось доказать.

• Граф потока управления может быть использован для быстрой категоризации, когда программа не имеет циклов (и поэтому останавливается), имеет тривиальные циклы (и поэтому останавливается), имеет нетривиальные циклы (неразрешимо) или входит в бесконечный цикл.

• c2:HaltingProblem
• Проблема зависания (англ.)

Ссылки на внешние ресурсы
Тематические сайты	MathWorld
Словари и энциклопедии	Britannica (онлайн)
В библиографических каталогах	GND: 4247732-3

Математическая логика
Общее	Аксиома список Мощность множества Логика первого порядка Доказательство Логическая семантика Основания математики Теория информации Лемма Умозаключение Модель Множество Теорема Теория Теория типов
Теоремы (список) и парадоксы	Теоремы Гёделя о полноте и о неполноте Теорема Тарского о невыразимости истины Парадокс Банаха — Тарского  теорема, парадокс и диагональный аргумент Кантора Компактность Проблема остановки Теорема Линдстрема Теорема Лёвенгейма — Скулема Парадокс Рассела
Логики	Традиционная Классическая логика Истина Тавтология Пропозиция Вывод Эквиваленция Непротиворечивость Эквиконсистенция Аргумент Правильность[англ.] Общезначимость Силлогистика Логический квадрат Диаграмма Венна Логика высказываний Алгебра логики Булева функция Логическая операция Логика высказываний Пропозициональные формулы Таблица истинности Многозначная логика 3 Конечная ∞ Логика предикатов Первого порядка Список теорий первого порядка Второго порядка Монадическая Высшего порядка Свободная Квантор Предикат Исчисление одноместных предикатов
Теория множеств	Множество Наследственное Класс (Ур-)Элемент Пара Порядковое число Подмножество Равенство Объёмность[англ.] Мощность[англ.] Отношение Эквивалентность Разбиение Операции над множествами: Пересечение Объединение Разность Прямое произведение Множество всех подмножеств Нейтральные элементы[англ.] Типы множеств Счётное Несчётное Пустое Непустое Синглетон Конечное Бесконечное Транзитивное Ультрафильтр[англ.] Разрешимое Нечёткое Универсальное Универсум Конструктивный Гротендика фон Неймана Maps & Мощность Функция/Map Область определения Кодомен[англ.] Образ Инъекция/Сюръекция/Биекция Теорема Кантора — Бернштейна Изоморфизм Нумерация Гёделя Перечисление Большой кардинал[англ.] Недоступный кардинал[англ.] Иерархия алефов Операция Бинарная Теории множеств Цермело — Френкеля Аксиома выбора Континуум-гипотеза Общая теория множеств[англ.] Крипке-Платека[англ.] Морза-Келли[англ.] Наивная Новые основы[англ.] Тарского-Гротендика[англ.] фон Неймана — Бернайса — Гёделя Аккермана[англ.] Конструктивных множеств[англ.]
Формальные системы(список[англ.]), язык и синтаксис	Алфавит Арность Автоматы Схема аксиом Выражение Выражение в замкнутом виде[англ.] Отношение Грамматика Свободные/связанные переменные[англ.] Язык Метаязык Логическая операция ¬ ∨ ∧ → ↔[англ.] = Предикат Доказательство Квантор ∃ ! ∀ Предложение Сигнатура Символ[англ.] Логическая константа Переменная Терм Примеры аксиоматических систем (список[англ.]) арифметические[англ.]: Пеано вещественные числа Аксиоматика Тарского Булевой алгебры Аксиома Вольфрама геометрические: Евклидовы Начальные Гильберта Неевклидовы Тарского Principia Mathematica
Теория доказательств	Доказательство Умозаключение Правило вывода Исчисление секвенций Теорема Системы Полная теория Независимость
Теория вычислимости	Кодирование Чёрча Тезис Чёрча — Тьюринга Перечислимое множество Вычислимая функция Разрешимое множество Задача разрешимости Алгоритмическая разрешимость Неразрешимость P NP Равенство классов P и NP Колмогоровская сложность Лямбда-исчисление Рекурсивная функция Рекурсия Разрешимое множество Машина Тьюринга Теория типов
Связанное	Абстрактная логика[англ.] Теория категорий Конкретная/Абстрактная категория Категория множеств История логики История математической логики хронология[англ.] Логицизм Математический объект Философия математики
Портал «Математика» Категория «Математика»