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

Проблема остановки (или проблема останова) — это одна из центральных проблем в теории алгоритмов, которая может неформально быть поставлена в виде:

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

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

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

Набросок доказательства

Рассмотрим множество <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
• [www.cprogramming.com/tutorial/computersciencetheory/halting.html Проблема зависания] (англ.)

Отрывок, характеризующий Проблема остановки

Княжна ошиблась ответом.
– Ну, как же не дура! – крикнул князь, оттолкнув тетрадь и быстро отвернувшись, но тотчас же встал, прошелся, дотронулся руками до волос княжны и снова сел.
Он придвинулся и продолжал толкование.
– Нельзя, княжна, нельзя, – сказал он, когда княжна, взяв и закрыв тетрадь с заданными уроками, уже готовилась уходить, – математика великое дело, моя сударыня. А чтобы ты была похожа на наших глупых барынь, я не хочу. Стерпится слюбится. – Он потрепал ее рукой по щеке. – Дурь из головы выскочит.
Она хотела выйти, он остановил ее жестом и достал с высокого стола новую неразрезанную книгу.
– Вот еще какой то Ключ таинства тебе твоя Элоиза посылает. Религиозная. А я ни в чью веру не вмешиваюсь… Просмотрел. Возьми. Ну, ступай, ступай!
Он потрепал ее по плечу и сам запер за нею дверь.
Княжна Марья возвратилась в свою комнату с грустным, испуганным выражением, которое редко покидало ее и делало ее некрасивое, болезненное лицо еще более некрасивым, села за свой письменный стол, уставленный миниатюрными портретами и заваленный тетрадями и книгами. Княжна была столь же беспорядочная, как отец ее порядочен. Она положила тетрадь геометрии и нетерпеливо распечатала письмо. Письмо было от ближайшего с детства друга княжны; друг этот была та самая Жюли Карагина, которая была на именинах у Ростовых:
Жюли писала:
«Chere et excellente amie, quelle chose terrible et effrayante que l'absence! J'ai beau me dire que la moitie de mon existence et de mon bonheur est en vous, que malgre la distance qui nous separe, nos coeurs sont unis par des liens indissolubles; le mien se revolte contre la destinee, et je ne puis, malgre les plaisirs et les distractions qui m'entourent, vaincre une certaine tristesse cachee que je ressens au fond du coeur depuis notre separation. Pourquoi ne sommes nous pas reunies, comme cet ete dans votre grand cabinet sur le canape bleu, le canape a confidences? Pourquoi ne puis je, comme il y a trois mois, puiser de nouvelles forces morales dans votre regard si doux, si calme et si penetrant, regard que j'aimais tant et que je crois voir devant moi, quand je vous ecris».
[Милый и бесценный друг, какая страшная и ужасная вещь разлука! Сколько ни твержу себе, что половина моего существования и моего счастия в вас, что, несмотря на расстояние, которое нас разлучает, сердца наши соединены неразрывными узами, мое сердце возмущается против судьбы, и, несмотря на удовольствия и рассеяния, которые меня окружают, я не могу подавить некоторую скрытую грусть, которую испытываю в глубине сердца со времени нашей разлуки. Отчего мы не вместе, как в прошлое лето, в вашем большом кабинете, на голубом диване, на диване «признаний»? Отчего я не могу, как три месяца тому назад, почерпать новые нравственные силы в вашем взгляде, кротком, спокойном и проницательном, который я так любила и который я вижу перед собой в ту минуту, как пишу вам?]
Прочтя до этого места, княжна Марья вздохнула и оглянулась в трюмо, которое стояло направо от нее. Зеркало отразило некрасивое слабое тело и худое лицо. Глаза, всегда грустные, теперь особенно безнадежно смотрели на себя в зеркало. «Она мне льстит», подумала княжна, отвернулась и продолжала читать. Жюли, однако, не льстила своему другу: действительно, и глаза княжны, большие, глубокие и лучистые (как будто лучи теплого света иногда снопами выходили из них), были так хороши, что очень часто, несмотря на некрасивость всего лица, глаза эти делались привлекательнее красоты. Но княжна никогда не видала хорошего выражения своих глаз, того выражения, которое они принимали в те минуты, когда она не думала о себе. Как и у всех людей, лицо ее принимало натянуто неестественное, дурное выражение, как скоро она смотрелась в зеркало. Она продолжала читать: 211
«Tout Moscou ne parle que guerre. L'un de mes deux freres est deja a l'etranger, l'autre est avec la garde, qui se met en Marieche vers la frontiere. Notre cher еmpereur a quitte Petersbourg et, a ce qu'on pretend, compte lui meme exposer sa precieuse existence aux chances de la guerre. Du veuille que le monstre corsicain, qui detruit le repos de l'Europe, soit terrasse par l'ange que le Tout Рuissant, dans Sa misericorde, nous a donnee pour souverain. Sans parler de mes freres, cette guerre m'a privee d'une relation des plus cheres a mon coeur. Je parle du jeune Nicolas Rostoff, qui avec son enthousiasme n'a pu supporter l'inaction et a quitte l'universite pour aller s'enroler dans l'armee. Eh bien, chere Marieie, je vous avouerai, que, malgre son extreme jeunesse, son depart pour l'armee a ete un grand chagrin pour moi. Le jeune homme, dont je vous parlais cet ete, a tant de noblesse, de veritable jeunesse qu'on rencontre si rarement dans le siecle оu nous vivons parmi nos villards de vingt ans. Il a surtout tant de franchise et de coeur. Il est tellement pur et poetique, que mes relations avec lui, quelque passageres qu'elles fussent, ont ete l'une des plus douees jouissances de mon pauvre coeur, qui a deja tant souffert. Je vous raconterai un jour nos adieux et tout ce qui s'est dit en partant. Tout cela est encore trop frais. Ah! chere amie, vous etes heureuse de ne pas connaitre ces jouissances et ces peines si poignantes. Vous etes heureuse, puisque les derienieres sont ordinairement les plus fortes! Je sais fort bien, que le comte Nicolas est trop jeune pour pouvoir jamais devenir pour moi quelque chose de plus qu'un ami, mais cette douee amitie, ces relations si poetiques et si pures ont ete un besoin pour mon coeur. Mais n'en parlons plus. La grande nouvelle du jour qui occupe tout Moscou est la mort du vieux comte Безухой et son heritage. Figurez vous que les trois princesses n'ont recu que tres peu de chose, le prince Basile rien, est que c'est M. Pierre qui a tout herite, et qui par dessus le Marieche a ete reconnu pour fils legitime, par consequent comte Безухой est possesseur de la plus belle fortune de la Russie. On pretend que le prince Basile a joue un tres vilain role dans toute cette histoire et qu'il est reparti tout penaud pour Petersbourg.