Шанс есть! Наука удачи, случайности и вероятности

Откуда столь неожиданный вывод? Вернемся к Гильберту. Он утверждал, что если вы построили формальную систему аксиом, должна существовать механическая процедура для определения того, является ли то или иное математическое доказательство верным, и эти аксиомы должны обладать полнотой и внутренней непротиворечивостью. Внутренняя непротиворечивость системы аксиом означает, что вы не можете доказать противоположные утверждения. Полнота системы означает, что вы можете доказать истинность или ложность любого утверждения, существующего в ее рамках. Из этого следует, что механическая процедура, о которой мы говорили, должна гарантировать: истинность всех математических утверждений можно доказать или опровергнуть механическим путем.

Есть красочное объяснение того, как работает эта механическая процедура. Речь идет о так называемом алгоритме Британского музея[11]. В рамках мысленного эксперимента (неосуществимого на практике, т. к. он требует бесконечного времени) систему аксиом, выраженных формальным языком математики, прогоняют через все возможные доказательства, причем порядок их следования выстроен согласно их размерам и лексикографической структуре (просто для того, чтобы соблюдать какой-то порядок). Вы устанавливаете, какие из этих доказательств верны, т. е. какие из них отвечают определенным правилам и могут быть приняты как справедливые. В принципе, если набор аксиом обладает внутренней непротиворечивостью и полнотой, можно определить истинность/ложность любой соответствующей теоремы. От математиков больше не требуется изобретательность, талант или вдохновение для того, чтобы доказывать теоремы. Математика становится механической.

Конечно же, на самом деле математика совсем не такая. Курт Гёдель, австрийский логик, и Алан Тьюринг, отец компьютера, показали: невозможно получить и аксиоматическую математическую теорию (обладающую внутренней непротиворечивостью и полнотой), и механическую процедуру, призванную решать, каким является произвольное математическое утверждение – истинным или ложным, доказуемым или недоказуемым.

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

Чтобы показать, что эту так называемую проблему остановки (проблему останова) невозможно решить в принципе, запустим программу на машине Тьюринга, которая представляет собой математическую идеализацию цифрового компьютера, не ограниченную временем. (Программа должна быть самоподдерживающейся – все данные должны поступать из самой же программы.) Далее зададимся простым вопросом: будет ли программа работать вечно или же наступит момент, когда она скажет «я закончила» и остановит работу?

Тьюринг продемонстрировал: для того, чтобы заранее определить, остановится ли когда-нибудь та или иная конкретная программа, не существует никакого набора инструкций, которые можно ввести в компьютер, никакого алгоритма. Непосредственно отсюда как раз и вытекает гёделевская теорема о неполноте: если нет механической процедуры для разрешения проблемы остановки, то нет и набора соответствующих аксиом, обладающих полнотой. Если бы они существовали, они дали бы нам механическую процедуру перебора всех возможных доказательств того, остановятся ли программы (хотя это, разумеется, заняло бы долгое время).

Чтобы сделать свой вывод о случайности в математике, я просто взял результат Тьюринга и изменил его формулировку. Получился своего рода математический каламбур. Хотя проблема остановки нерешаема, можно рассмотреть вероятность того, остановится ли когда-нибудь случайно выбранная программа. Начнем с мысленного эксперимента, где используется обычный компьютер «общего назначения», который, если дать ему достаточно времени, способен проделать работу любого компьютера. Иными словами, это универсальная машина Тьюринга.