Почему не может быть программа, которая проверяет другую программу

Question

Я пытаюсь найти логическое объяснение Turing Alan, почему не может быть программы, которая проверяет другие программы.

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

Спасибо за помощь.

Answer 1

«Проверяет другую программу» очень широкой. На самом деле некоторые особенности программ могу быть проверено, например, проверяют ли или нет чеки программы Java. Тем не менее, тип проверки программы Java также отклонит некоторые программы, которые никогда не будут создавать ошибку типа при запуске, например:

int foo() {
    if (true) return 5;
    else return null;
}

Этот метод никогда не будет возвращаться null, но тип проверки типа не видит этого. Но не смог бы просто сделать систему умного типа?

К сожалению, ответ нет. Рассмотрим следующую программу:

int bar() {
    if (infiniteComputation()) return 5;
    else return null;
}

Проверка типа не может проверить, если infiniteComputation когда-нибудь вернет ложь, из-за Задача проблемы.

Другая связанная теорема Теорема риса, который, вероятно, ближе к тому, что ваш вопрос был о проблемах остановки.

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

Answer 2

Вы ищете Задача проблемы.

Alan Turing оказался в 1936 году, что общий алгоритм для решения проблемы остановки для всех возможных программ-входов не может существовать. Мы говорим, что проблема остановки неразрешивается над Turging Machines.

Answer 3

Там есть Википедия запись на это ...

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

Это похоже на расчет цифр для Pi--, останавливается? Как вы можете сказать, что это бесконечно во время выполнения, а не страдает от какой-либо вычислительной проблемы? Мы знаем, что эта особая проблема бесконечна, но другие, которые похожи, не так доказаны.

Answer 4

Ответ Байрона должен указать вам на важной информации. Кроме того, вы можете иметь программу, которая проверяет определенную программу. То, что вы не можете иметь, это программа, которая проверяет произвольную программу для правильности.