Из моего понимания доказательства того, что проблема остановки не вычислима, эта проблема не вычислима, потому что если у нас есть программа P (x), которая вычисляет, останавливается ли программа x или нет, мы получаем парадокс, когда передаем P в качестве входных данных для тот же P, имеющий: P (P), пытающийся решить, останавливается ли P или не использует сам P.
Поэтому мой вопрос: является ли проблема остановки вычисляемой программой P для всех других программ, используемых в качестве входных данных, кроме самого P? Другими словами: проблема остановки не вычислима только в этом особом случае, или доказательство носит более общий характер, и я что-то упускаю?
halting-problem
Алессио Марторана
источник
источник
Ответы:
Если - любая вычислимая функция, то g , определенный какf g
также вычислимо, для любого выбора .k,v
В принципе, если у вас есть программа которая вычисляет g ( n ) для всех n , кроме n = k , вы можете «исправить» этот случай (например, с помощью an ) и получить другую программу P, которая вычисляет g ( n ) для все п .P′ g(n) n n=k P g(n) n
if then elseСледовательно, если бы вы могли вычислить функцию остановки «за исключением одного случая», вы также можете вычислить функцию остановки (без исключений). Из этого вы можете получить противоречие, как обычно.
Вывод: нет, вы не можете решить проблему остановки «кроме одного случая» (ни «кроме конечного числа случаев»).
источник
Нет. Рассмотрим бесконечную последовательность программ , где P i - это «Переместите квадраты i вправо, затем квадраты i влево, затем сделайте в точности то, что сделал бы P ». Каждая из этих программ выдает точно такой же вывод, что и P, для каждого входа (включая цикл навсегда, если P цикл навсегда), но все они разные программы.P1,P2,… Pi i i P P P
И вы не можете обойти это, только требуя, чтобы работал с программами, которые функционально не эквивалентны самому себе, поскольку это свойство также неразрешимо. Возможно, проблема была бы разрешима, когда она ограничена этими экземплярами (хотя я подозреваю, что это не так), но набор экземпляров неразрешим, поэтому вы не можете выполнить ограничение.P
источник
Существуют алгоритмы, которые показывают, что определенные классы программ останавливаются или не останавливаются. Например,
Хотя нет алгоритма для определения того, останавливается ли произвольная программа, большая часть кода была разработана либо для остановки (как большинство подпрограмм), либо не для остановки (как бесконечный цикл для обработки событий), и возможно алгоритмически определить, что есть что. Другими словами, у вас может быть алгоритм, который отвечает либо «останавливается», «не останавливается», либо «я не знаю», и такой алгоритм может быть разработан для охвата достаточного количества программ, что было бы полезно.
источник
Доказательства от противоречия не должны быть исчерпывающими , достаточно одного контрпримера. Доказательство неразрешимости проблемы остановки дает вам один пример P, для которого свойство остановки не может быть решено. В этом доказательстве не говорится, что P - единственная такая программа, на самом деле могут существовать независимые доказательства, конструирующие совершенно разные классы P.
источник
Доказательство действительно более общее: проблема остановки является частным случаем теоремы Райс , которая утверждает
Вы можете получить некоторые результаты, ограничив пространство программ, с которыми вы хотите работать, хотя эти ограничения должны быть довольно радикальными. Например, если вам гарантировано, что программа, которую вам дают, либо останавливается в течение 100 шагов, либо работает вечно, решение о ее остановке становится легким.
источник
Пусть R - любое рекурсивно перечислимое, но нерекурсивное множество. Таких множеств бесконечно много. Пусть T машина Тьюринга, которая останавливается на входе k тогда и только тогда, когда k находится в R. Такой T существует для любого рекурсивно перечислимого множества. Невозможно написать программу, которая может решить проблему остановки для этого T. Это связано с тем, что любой алгоритм для определения того, останавливается ли T, даст алгоритм определения принадлежности к R, что невозможно, если R нерекурсивен. Поскольку существует бесконечно много таких R, каждый из которых дает разные машины Тьюринга, существует бесконечно много машин Тьюринга, на которых любая попытка остановить программу P потерпит неудачу.
источник