Неразрешимость и проблема остановки

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

Definition

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

Scope

Эта тема охватывает аргумент диагонализации, устанавливающий неразрешимость проблемы остановки, различие между разрешимыми, распознаваемыми и ко-распознаваемыми проблемами, теорему Райса, показывающую, что все нетривиальные семантические свойства программ неразрешимы, а также каталог естественных неразрешимых проблем в логике, математике и информатике.

Core questions

• Почему ни один алгоритм не может определить, останавливается ли каждая программа?
• В чем разница между разрешимой и просто распознаваемой проблемой?
• Почему по существу все интересные свойства поведения программ неразрешимы?
• Как неразрешимость распространяется от проблемы остановки на другие проблемы?

Key theories

Неразрешимость проблемы остановки

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

Теорема Райса

Каждое нетривиальное свойство функции, вычисляемой программой — все, что справедливо для одних программ и неверно для других на основе поведения — неразрешимо, обобщая результат об остановке на все семантические свойства.

Clinical relevance

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

History

Тьюринг установил неразрешимость проблемы остановки и проблемы разрешимости для логики в 1936 году, используя диагональный аргумент, вдохновленный Кантором и Гёделем. Райс доказал свое широкое обобщение в 1953 году, и в последующие десятилетия многие естественные проблемы, включая десятую проблему Гильберта о диофантовых уравнениях, были показаны как неразрешимые.

Key figures

• Alan Turing
• Henry Gordon Rice
• Emil Post
• Alonzo Church

Seminal works

• turing1937
• sipser2013

Frequently asked questions

Почему мы не можем просто запустить программу, чтобы увидеть, остановится ли она?

Запуск программы покажет, что она остановилась, только если она действительно это сделает; если она будет работать бесконечно, никакое конечное ожидание этого не выявит. Проблема остановки требует метода, который всегда дает правильный ответ за конечное время для каждой программы и входа, и Тьюринг доказал, что такого метода не существует.

Делает ли неразрешимость анализ программ безнадежным?

Нет, но это объясняет, почему идеальный анализ невозможен. Инструменты справляются с этим, будучи консервативными, помечая все, что они не могут доказать как безопасное, обрабатывая ограниченные классы программ точно или решая многие практические случаи, допуская при этом, что они могут потерпеть неудачу на враждебных или патологических случаях.