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

'''Проблема остановки''' ({{lang-en|Halting problem}}) — одна из проблем в [[теория алгоритмов|теории алгоритмов]]<ref>''[[Верещагин, Николай Константинович|Н. К. Верещагин]], [[Шень, Александр Ханиевич|А. Шень]]'' [http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции] {{Wayback|url=http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf |date=20151112035312 }}</ref>, которая может неформально быть поставлена в виде: для данного описания процедуры и её начальных входных данных определить, завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки.

[[Тьюринг, Алан|Алан Тьюринг]] доказал в [[1936 год в науке|1936 году]], что проблема остановки [[неразрешимость|неразрешима]] на [[машина Тьюринга|машине Тьюринга]]. Другими словами, не существует общего алгоритма решения этой проблемы<ref>{{source|Q25864184|ref=Turing|ref-year=1937}} <!-- On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society --> (в этой публикации Тьюринг ввёл определение [[Машина Тьюринга|машины Тьюринга]], сформулировал проблему зависания и показывает, что она, также как и [[проблема разрешения]], неразрешима).</ref>.

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

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

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

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

== Доказательство ==
Рассмотрим множество <math>S</math> алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество <math>S</math> по алфавиту. При этом каждый алгоритм получит свой порядковый номер; более того существует алгоритм, который по номеру элемента <math>S</math> восстанавливает его код в выбранном языке программирования. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел <math>(N, X)</math>, и:
* останавливается и возвращает 1, если алгоритм с номером <math>N</math> не останавливается, получив на вход <math>X</math>
* не останавливается в противном случае (если алгоритм с номером <math>N</math> останавливается, получив на вход <math>X</math>).

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

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

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

== Примечания ==
{{примечания}}

== Ссылки ==
* [[c2:HaltingProblem]]
* [http://www.cprogramming.com/tutorial/computersciencetheory/halting.html Проблема зависания]{{ref-en}}

{{rq|style|tex|check}}
{{Внешние ссылки}}

[[Категория:Теория алгоритмов]]
[[Категория:Неразрешимые проблемы]]