Новый ум короля: О компьютерах, мышлении и законах физики - Пенроуз Роджер. Страница 43

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

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

Как оказывается, алгоритм отыскания доказательства внутри произвольной формальной системы присутствует всегда, если только система допускает какое-нибудь доказательство. Действительно, мы прежде всего должны предполагать, что наша система формулируется на некотором языке символов, который можно выразить в терминах некоторого конечного «алфавита» символов. Как и ранее, давайте упорядочим наши строки символов лексикографически, что, как мы помним, означает расставление в алфавитном порядке строк каждой определенной длины, где все строчки единичной длины идут первыми, за ними следуют (также упорядоченные) строки из двух символов, потом — из трех, и так далее (см. прим. 72 подглавы «Теорема Геделя»).

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

Таким образом, если бы Гильберту удалось отыскать свою математическую систему — систему аксиом и правил вывода, достаточно мощную, чтобы позволить решать, путем формального доказательства, вопрос о справедливости или ложности любого математического утверждения, корректно сформулированного в рамках системы, — то тогда существовал бы общий алгоритмический метод выяснения истинности любого такого рассуждения. Почему это так? Потому что, если мы при помощи процедуры, описанной выше, находим искомое утверждение как последнюю строчку некоторого доказательства, то это утверждение автоматически считается доказанным. Если же, напротив, мы находим последнюю строчку, содержащую отрицание нашего утверждения, то мы тем самым доказываем его ложность. Если бы схема Гильберта была полной, то либо одна, либо другая возможность обязательно имела бы место (и если бы система была непротиворечивой, то обе возможности никогда бы не могли быть реализованы одновременно). То есть наша механическая процедура всегда бы прерывалась на некотором шаге и мы бы имели универсальный алгоритм для доказательства истинности или ложности всех утверждений системы. Это находилось бы в противоречии с результатами Тьюринга, изложенными во второй главе, согласно которым не существует общего алгоритма для доказательства математических утверждений. И, как следствие, мы доказали теорему Геделя о том, что ни одна система наподобие задуманной Гильбертом не может быть полной в обсуждаемом нами смысле.

В действительности теорема Геделя носит более частный характер, поскольку от формальной системы того типа, который рассматривал Гедель, требовалась адекватность по отношению к арифметическим утверждениям, а не математическим утверждениям вообще. Можем ли мы устроить так, чтобы все необходимые операции машины Тьюринга выполнялись только при помощи арифметики? Или, иными словами, могут ли все вычислимые функции натуральных чисел (т. е. рекурсивные, или алгоритмические функции — результаты действия машины Тьюринга) быть выражены в терминах обычной арифметики? На самом деле это так, хотя и не совсем. Нам понадобится одна дополнительная операция, которую мы добавим в систему стандартных правил арифметики и логики (включая кванторы E_к.с. и A_к.о.). Эта операция просто выбирает «наименьшее натуральное число такое, что K(х) имеет значение „истина“», где К() — заданная арифметически вычислимая функция исчисления высказываний, для которой предполагается существование такого числа, т. е. что

E_к.с.x[K(х)] является истинным. (Если бы такого числа не было, то наша операция повторялась бы «бесконечно» [81]), стараясь обнаружить несуществующее x.) В любом случае, предшествующие рассуждения показывают, что, исходя из результатов Тьюринга, программа Гильберта по сведению целых разделов математики к вычислениям в рамках некоторой формальной системы — невыполнима.

Как оказывается, эта процедура не может с очевидностью установить, что мы имеем утверждение Геделя (наподобие P_k(k), которое верно, но внутри системы недоказуемо. Однако, если вспомнить доказательство, приведенное в главе 2 и показывающее, «как „перехитрить“ алгоритм» (см. подглаву «Как превзойти алгоритм»), то мы увидим, что можно сделать нечто похожее и в этом случае. В том доказательстве мы смогли выяснить, что для любого алгоритма, определяющего момент остановки машины Тьюринга, можно придумать такое действие машины, которое не прекращается, хотя алгоритм — в отличие от нас — «увидеть» это не способен. (Вспомните, что мы требовали от алгоритма корректно информировать нас о моменте, когда машина Тьюринга действительно остановится, хотя мы допускаем, что он может не оповестить нас, если машина на самом деле не прекратит свое действие, продолжая работать вечно.) Таким образом, как и в ситуации с теоремой Геделя, у нас есть утверждение (безостановочное действие машины Тьюринга), истинность которого мы можем установить при помощи интуитивного понимания, хотя определенная алгоритмическая процедура нам такой возможности и не дает.

Рекурсивно нумеруемые множества

Существует способ для описания основных результатов, полученных Геделем и Тьюрингом, в графическом виде, на языке теории множеств. Это позволит нам избежать произвольности описания в терминах конкретного символизма или в рамках формальной системы и выделить наиболее существенное. Мы будем рассматривать только множества натуральных чисел (конечные или бесконечные), такие как {4,5,8}, {0,57,100003}, {6}, {0}, {1,2,3,4….,9999}, {1,2, 3,4…. }, {0,2,4,6,8…. } ит. п.; или даже все множество N = {0,1,2,3,4… }, равно как и пустое множество ø = {}. Нас будут интересовать только вопросы вычислимости, скажем: «Какие множества натуральных чисел могут быть сгенерированы с помощью алгоритма, а какие — нет?»