7.9. Машины с оракулом и физические законы

Можно, впрочем, задать и иной вопрос. Предположим, что новая теория квантовой гравитации действительно окажется невычислимой теорией - в том, в частности, смысле, что она позволит нам сконструировать физическое устройство, способное решить проблему остановки. Будет ли этого достаточно для разрешения всех проблем, порожденных нашими размышлениями о доказательстве Гёделя - Тьюринга в первой части книги? Как ни удивительно, ответ - нет\

Попробуем разобраться, почему способность решить проблему остановки ничем нам не поможет. В 1939 году Тьюринг предложил одну важную концепцию, имеющую к этому вопросу самое непосредственное отношение, - концепцию оракула. Идея такова: оракул есть нечто (предположительно, воображаемый объект, существующий лишь в голове самого Тьюринга и вовсе не обязательно реализуемый физически), что действительно может решить проблему остановки. Так, если дать оракулу пару натуральных чисел и , то он через некоторое конечное время выдаст нам ответ ДА или НЕТ, в зависимости от того, завершится в конце концов вычисление Cq(n) или нет (см. §2.5). В §2.5 мы доказываем вывод Тьюринга о том, что такой оракул, действующий исключительно вычислительными методами, создать невозможно, однако там ничего не говорится о том, что оракул невозможно построить физически. Чтобы прийти к такому выводу, мы должны твердо знать, что физические законы являются