Означает ли остановка problem, что программы не могут проверять другие программы?
Я беру теоретический урок CS, и мы только что обсудили проблему остановки. В моем понимании, причина, по которой проблема не может быть решена, заключается в том, что если есть программа Halt, которая сообщает нам, не останавливается ли программа, и вы пишете другую программу Proof, такую, что
function Proof (program, input)
if (Halt(program, input)) loop infinitely;
else return 1
Для меня суть проблемы в том, что условием if является бесконечный цикл программы, что является условием сбоя для Halt.
Это та часть, в которой я не уверен:
Скажем, у вас была программа, чтобы проверить, возвращает ли другая программа число 4 на определенном входе. Давайте назовем эту программу FourCheck. Тогда мы могли бы написать другую программу ProofFour, такую, что
ProofFour(program, input)
if(FourCheck(program, input) return 5;
else return 4;
В этом случае мы можем вызвать ProofFour (ProofFour, input). Если FourCheck () возвращает true, то ProofFour возвращает 5, что делает вывод FourCheck () неверным. Если FourCheck возвращает false, то ProofFour возвращает 4, снова делая вывод FourCheck () неверным.
Следовательно, было бы правильно предположить, что у вас по существу не может быть программы для проверки других программ, потому что вы всегда можете создать программу, аналогичную Proof () и ProofFour (), которая по существу инвертирует выходные данные вашей программы проверки.
Решение
ProofFour(program, input)
if(FourCheck(program, input)) return 5;
else return 4;
С вышеуказанной программой ваш звонок ProofFour(ProofFour,input) плохо сформирован: первый Prooffour все в порядке, так как он принимает программу и вход в качестве входных данных, но второй Prooffour должно иметь два аргумента. Это означает, что вы должны предоставить парный вход для второго Prooffour, как это: ProofFour(ProofFour,(someprog, input)) Когда вы используете эту четко определенную форму, трудно (если не невозможно) объяснить, почему невозможно создать FourCheck ().
Теперь я немного изменил это:
ProofFour(input)
if(FourCheck(ProofFour, input)) return 5;
else return 4;
Это четко определенная форма. ProofFour в программе — это просто указатель на текст программы. Теперь понятно, что Fourcheck не может проверить программу ProofFour.
Другие решения